New representation to reduce the search space for the resource-constrained project scheduling problem

Khaled Moumene; Jacques A. Ferland

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 2, page 215-228
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Moumene, Khaled, and Ferland, Jacques A.. "New representation to reduce the search space for the resource-constrained project scheduling problem." RAIRO - Operations Research 42.2 (2008): 215-228. <http://eudml.org/doc/250390>.

@article{Moumene2008,
abstract = { 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. },
author = {Moumene, Khaled, Ferland, Jacques A.},
journal = {RAIRO - Operations Research},
keywords = {Project scheduling; Resource-constrained project scheduling; Activity list representation; Activity set list representation; Heuristics and metaheuristics.; project scheduling; resource-constrained project scheduling; activity list representation; activity set list representation; heuristics and metaheuristics},
language = {eng},
month = {5},
number = {2},
pages = {215-228},
publisher = {EDP Sciences},
title = {New representation to reduce the search space for the resource-constrained project scheduling problem},
url = {http://eudml.org/doc/250390},
volume = {42},
year = {2008},
}

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
DA - 2008/5//
PB - EDP Sciences
VL - 42
IS - 2
SP - 215
EP - 228
AB - 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.
LA - eng
KW - Project scheduling; Resource-constrained project scheduling; Activity list representation; Activity set list representation; Heuristics and metaheuristics.; project scheduling; resource-constrained project scheduling; activity list representation; activity set list representation; heuristics and metaheuristics
UR - http://eudml.org/doc/250390
ER -

References

top
  1. J. Alcaraz and C. Maroto, A Robust Genetic Algorithm for Resource Allocation in Project Scheduling, Ann. Oper. Res.102 (2001) 83–109.  
  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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  9. E.W. Davis, G.E. Heidorn, An algorithm for optimal project scheduling under multiple resource constraints, Manage. Sci.27 (1971) B803–B816.  
  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.  
  12. E. Demeulemeester, W. Herroelen, A branch-and-bound procedure for multiple resource-constrained project scheduling problem, Manage. Sci.38 (1992) 1803–1818.  
  13. S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling, Nav. Res. Logist.456 (1998) 733–750.  
  14. W. Herroelen, B. Reyck, E. Demeulemeester, Resource-constrained project scheduling : A survey of recent developments, Computers and Operations Research4 (1998) 279–302.  
  15. R. Klein, Bidirectional planning : improving priority rule-based heuristics for scheduling resource-constrained projects, Eur. J. Oper. Res.127 (2000) 619–638.  
  16. U. Kohlmorgen, H. Schmeck, K. Haase, Experiences with fine-grained parallel genetic algorithms, Ann. Oper. Res.90 (1999) 203–219.  
  17. R. Kolisch, A. Drexel, Adaptative search for solving hard project scheduling problem, Nav. Res. Logist.43 (1996) 23–40.  
  18. R. Kolisch, Serial and Parallel resource-constrained project scheduling methods revisited: Theory and computation, Eur. J. Oper. Res.90 (1996) 320–333.  
  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.  
  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.  
  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.  
  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.  
  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.  
  27. J.P. Stinson, E.W. Davis, B.M. Khumawala, Multiple resource-constrained scheduling using branch-and-bound, AIIE Transactions10 (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.  
  29. A. Thesen, Heuristic scheduling of activities under resource and precedence restrictions, Manage. Sci.23 (1976) 412–422.  

NotesEmbed ?

top

You must be logged in to post comments.