A new any-order schedule generation scheme for resource-constrained project scheduling
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.

DOI : 10.1051/ro/2009017
Classification : 90B35
Keywords: project scheduling, schedule generation scheme, activity insertion
Mots clés : ordonnancement de projet, schéma de génération de solutions, insertion d'activités
@article{RO_2009__43_3_297_0,
     author = {Briand, Cyril},
     title = {A new any-order schedule generation scheme for resource-constrained project scheduling},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {297--308},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     doi = {10.1051/ro/2009017},
     mrnumber = {2567990},
     zbl = {1170.90007},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2009017/}
}
TY  - JOUR
AU  - Briand, Cyril
TI  - A new any-order schedule generation scheme for resource-constrained project scheduling
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 297
EP  - 308
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2009017/
DO  - 10.1051/ro/2009017
LA  - en
ID  - RO_2009__43_3_297_0
ER  - 
%0 Journal Article
%A Briand, Cyril
%T A new any-order schedule generation scheme for resource-constrained project scheduling
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 297-308
%V 43
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2009017/
%R 10.1051/ro/2009017
%G en
%F RO_2009__43_3_297_0
Briand, Cyril. A new any-order schedule generation scheme for resource-constrained project scheduling. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 3, pp. 297-308. doi : 10.1051/ro/2009017. http://www.numdam.org/articles/10.1051/ro/2009017/

[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

Cité par Sources :