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.
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] and , 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] , and , Insertion Techniques for static and dynamic resource-constrained project scheduling. Eur. J. Oper. Res. 149 (2003) 249-267. | MR | Zbl
[3] , and , Scheduling project networks with resource constraints and time windows. Ann. Oper. Res. 16 (1988) 201-240. | MR | Zbl
[4] , , , and , Resource-constrained project scheduling: Notation, classification, models and methods. Eur. J. Oper. Res. 112 (1999) 3-41. | Zbl
[5] , and , Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math. 5 (1983) 11-24. | MR | Zbl
[6] , , and , A branch-and-bound algorithm for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 107 (1998) 272-288. | Zbl
[7] and , New Benchmark Results for the Resource-Constrained Project Scheduling Problem. Manage. Sci. (1997) 1485-1492. | Zbl
[8] and , 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] and , Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update. Eur. J. Oper. Res. 174 (2006) 23-37. | Zbl
Cité par Sources :
