A new any-order schedule generation scheme for resource-constrained project scheduling

Briand, Cyril

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 3, pp. 297-308.

Dans cet article, un nouveau schéma de génération de solution est proposé pour les problèmes d'ordonnancement de projet sous contraintes de ressources. Considérant un problème d'ordonnancement et une règle de priorité donnée, un schéma de génération de solution détermine une solution faisable en insérant une par une chaque activité du projet, en fonction de leur priorité et des relations de précédence, dans un ordonnancement partiel. Le schéma de génération décrit dans cet article diffère des schémas classiques par le fait qu'il autorise l'insertion des activités dans n'importe quel ordre, indépendamment de leurs relations de précédence. De plus, lors de l'insertion d'une activité, le schéma autorise aussi de retarder des activités déjà ordonnancées, ce qui constitue une deuxième originalité. L'article montre que cette stratégie conduit souvent à de meilleurs résultats que ceux obtenus avec les schémas classiques, tout en conservant un temps de calcul polynomial. De plus, on montre que certaines règles de priorité, peu efficaces avec les schémas classiques, deviennent très compétitives avec ce nouveau schéma.

In this paper, a new schedule generation scheme for resource-constrained project scheduling problems is proposed. Given a project scheduling problem and a priority rule, a schedule generation scheme determines a single feasible solution by inserting one by one each activity, according to their priority, inside a partial schedule. The paper proposes a generation scheme that differs from the classic ones in the fact that it allows to consider the activities in any order, whether their predecessors have already been scheduled or not. Moreover, activity insertion is performed so that delaying some already scheduled activities is allowed. The paper shows that this strategy remains polynomial and often gives better results than more classic ones. Moreover, it is also interesting in the fact that some priority rules, which are quite poor when used with classic schedule generation schemes, become very competitive with the proposed schedule generation scheme.

[1] C. Artigues and F. Roubellat, A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple mode. Eur. J. Oper. Res. (2000) 127 297-316. | Zbl

[2] C. Artigues, P. Michelon and S. Reusser, Insertion Techniques for static and dynamic resource-constrained project scheduling. Eur. J. Oper. Res. 149 (2003) 249-267. | MR | Zbl

[3] M. Bartusch, R.H. Möhring and F.J. Radermacher, Scheduling project networks with resource constraints and time windows. Ann. Oper. Res. 16 (1988) 201-240. | MR | Zbl

[4] P. Brucker, A. Drexl, R.H. Möhring, K. Neumann and E. Pesh, Resource-constrained project scheduling: Notation, classification, models and methods. Eur. J. Oper. Res. 112 (1999) 3-41. | Zbl

[5] J. Blazewicz, J. Lenstra and A. Rinnooy Kan, Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math. 5 (1983) 11-24. | MR | Zbl

[6] P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch-and-bound algorithm for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 107 (1998) 272-288. | Zbl

[7] E.L. Demeulemeester and W.S. Herroelen, New Benchmark Results for the Resource-Constrained Project Scheduling Problem. Manage. Sci. (1997) 1485-1492. | Zbl

[8] S. Hartmann and R. Kolisch, Experimental evaluation of the state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127 (2000) 394-407. | Zbl

[9] R. Kolisch and S. Hartmann, Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update. Eur. J. Oper. Res. 174 (2006) 23-37. | Zbl