New representation to reduce the search space for the resource-constrained project scheduling problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 215-228.

This paper describes a new representation for the solutions of the resource-constrained project scheduling problem (RCPSP) denoted Activity Set List. The most efficient heuristics for the problem use the activity list representation and the serial SGS method to construct the corresponding solution (schedule). The activity list may induce a search space of representations much larger then the space of schedules because the same schedule can correspond to many different activity list representations. We indicate how the activity set list representation can significantly reduce the search space, and how to move more efficiently through it. Furthermore, this new representation never excludes the optimal solution and it has many interesting properties. An evaluation of the search space reduction induced by this representation is made for the most used library of instances in the literature. The activity set list representation may be used to construct a new category of more efficient solution procedures for the problem.

DOI : 10.1051/ro:2008010
Classification : 90B35
Mots-clés : project scheduling, resource-constrained project scheduling, activity list representation, activity set list representation, heuristics and metaheuristics 
@article{RO_2008__42_2_215_0,
     author = {Moumene, Khaled and Ferland, Jacques A.},
     title = {New representation to reduce the search space for the resource-constrained project scheduling problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {215--228},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ro:2008010},
     mrnumber = {2431400},
     zbl = {1154.90476},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2008010/}
}
TY  - JOUR
AU  - Moumene, Khaled
AU  - Ferland, Jacques A.
TI  - New representation to reduce the search space for the resource-constrained project scheduling problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 215
EP  - 228
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2008010/
DO  - 10.1051/ro:2008010
LA  - en
ID  - RO_2008__42_2_215_0
ER  - 
%0 Journal Article
%A Moumene, Khaled
%A Ferland, Jacques A.
%T New representation to reduce the search space for the resource-constrained project scheduling problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 215-228
%V 42
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2008010/
%R 10.1051/ro:2008010
%G en
%F RO_2008__42_2_215_0
Moumene, Khaled; Ferland, Jacques A. New representation to reduce the search space for the resource-constrained project scheduling problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 215-228. doi : 10.1051/ro:2008010. http://www.numdam.org/articles/10.1051/ro:2008010/

[1] J. Alcaraz and C. Maroto, A Robust Genetic Algorithm for Resource Allocation in Project Scheduling, Ann. Oper. Res. 102 (2001) 83-109. | MR | Zbl

[2] T. Baar, P. Brucker and S. Knust, Tabu-search algorithms for the resource-constrained project scheduling problem, Metaheuristics : Advances and Trends in Local Search Paradigms for Optimisation, Kluwer (1997) 1-18. | MR | Zbl

[3] J. Blazewicz, J.K. Lenstra, A.H.G. and Rinnooy Kan, Scheduling projects to resource constraints : Classification and complexity, Disc. Appl. Math. 5 (1983) 11-24. | MR | Zbl

[4] F.F. Boctor, Some effcient multi-heuristic procedures for resource-constrained project scheduling, Eur. J. Oper. Res. 49 (1990) 3-13.

[5] F.F. Boctor, Resource-constrained project scheduling by simulated annealing, Int. J. Prod. Res. 34 (1996) 2335-2351. | Zbl

[6] M. Bouleimen, H. Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple version, Eur. J. Oper. Res. 149 (2003) 268-281. | MR | Zbl

[7] P. Brucker, A. Drexl, R. Mohring, K. Neumann, Resource-constrained project scheduling : Notation, classification, models and methods, Eur. J. Oper. Res. 112 (1999) 3-41. | Zbl

[8] J.-H. Cho, Y.-D. Kim, A simulated annealing algorithm for resource-constrained project scheduling problems, J. Oper. Res. Soc. 48 (1997) 735-744. | Zbl

[9] E.W. Davis, G.E. Heidorn, An algorithm for optimal project scheduling under multiple resource constraints, Manage. Sci. 27 (1971) B803-B816. | Zbl

[10] E.W. Davis, J.H. Patterson, A comparison of heuristic and optimal solutions in resource-constrained project scheduling, Manage. Sci. 21 (1975) 944-955.

[11] E. Demeulemeester, W. Harroelen, New benchmarking results for the resource constrained project scheduling problem, Manage. Sci. 43 (1995) 1485-1492. | Zbl

[12] E. Demeulemeester, W. Herroelen, A branch-and-bound procedure for multiple resource-constrained project scheduling problem, Manage. Sci. 38 (1992) 1803-1818. | Zbl

[13] S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling, Nav. Res. Logist. 456 (1998) 733-750. | MR | Zbl

[14] W. Herroelen, B. Reyck, E. Demeulemeester, Resource-constrained project scheduling : A survey of recent developments, Computers and Operations Research 4 (1998) 279-302. | MR | Zbl

[15] R. Klein, Bidirectional planning : improving priority rule-based heuristics for scheduling resource-constrained projects, Eur. J. Oper. Res. 127 (2000) 619-638. | Zbl

[16] U. Kohlmorgen, H. Schmeck, K. Haase, Experiences with fine-grained parallel genetic algorithms, Ann. Oper. Res. 90 (1999) 203-219. | MR | Zbl

[17] R. Kolisch, A. Drexel, Adaptative search for solving hard project scheduling problem, Nav. Res. Logist. 43 (1996) 23-40. | Zbl

[18] R. Kolisch, Serial and Parallel resource-constrained project scheduling methods revisited: Theory and computation, Eur. J. Oper. Res. 90 (1996) 320-333. | Zbl

[19] R. Kolisch, Efficient priority rules for the resource-constrained project scheduling problem, J. Oper. Manage. 14 (1996) 179-192.

[20] R. Kolisch, A. Drexl, Adaptative search for solving hard project scheduling problems, Nav. Res. Logist. 43 (1996) 23-40. | Zbl

[21] R. Kolisch, S. Hartmann, Heuristic algorithms for solving resource-constrained project scheduling problem : Classification and computation analysis, in : Project Scheduling : Recent Models, Algorithms and Applications, edited by J. Weglarz, Kluwer Academic Publisher, Boston 1999, 147-178.

[22] Kolisch R., Sprecher A., Drexel A., Characterization and generation of general class of resource-constrained project scheduling problems, Manage. Sci. 41 (1995) 1693-1703. | Zbl

[23] A. Mingozi, V. Maniezzo, S. Ricciardelli, L. Bianco, An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation, Manage. Sci. 44 (1998) 714-729. | Zbl

[24] J.H. Patterson, R. Sowinski, F.B. Talbot, J. Weglarz, An algorithm for a general class of precedence and resource constrained scheduling problems, in : Advances in project scheduling, edited by R. Sowinski, J. Weglarz, Elsevier, Amsterdam 1989, 3-28. | MR

[25] E. Pinson, C. Prins, F. Rullier, Using tabu search for solving the resource-constrained project scheduling problem, in: Proceedings of the 4th International Workshop on Project Management and Scheduling, Leuven, Belgium 1994, 102-106.

[26] A. Sprecher, R. Kolisch, A. Drexel, Semi-Active, active and non-delay schedules for resource-constrained project scheduling problem, Eur. J. Oper. Res. 80 (1995) 94-102. | Zbl

[27] J.P. Stinson, E.W. Davis, B.M. Khumawala, Multiple resource-constrained scheduling using branch-and-bound, AIIE Transactions 10 (1978) 252-259.

[28] B. Talbot, J.H. Patterson, An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problem, Manage. Sci. 24 (1978) 1163-1174. | Zbl

[29] A. Thesen, Heuristic scheduling of activities under resource and precedence restrictions, Manage. Sci. 23 (1976) 412-422.

Cité par Sources :