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.  Zbl1024.90036
  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.  Zbl1074.90563
  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.  Zbl0516.68037
  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.  Zbl0930.90041
  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.  Zbl1040.90015
  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.  Zbl0937.90030
  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.  Zbl0881.90069
  9. E.W. Davis, G.E. Heidorn, An algorithm for optimal project scheduling under multiple resource constraints, Manage. Sci.27 (1971) B803–B816.  Zbl0224.90030
  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.  Zbl0914.90160
  12. E. Demeulemeester, W. Herroelen, A branch-and-bound procedure for multiple resource-constrained project scheduling problem, Manage. Sci.38 (1992) 1803–1818.  Zbl0761.90059
  13. S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling, Nav. Res. Logist.456 (1998) 733–750.  Zbl0936.90024
  14. W. Herroelen, B. Reyck, E. Demeulemeester, Resource-constrained project scheduling : A survey of recent developments, Computers and Operations Research4 (1998) 279–302.  Zbl1040.90525
  15. R. Klein, Bidirectional planning : improving priority rule-based heuristics for scheduling resource-constrained projects, Eur. J. Oper. Res.127 (2000) 619–638.  Zbl0979.90073
  16. U. Kohlmorgen, H. Schmeck, K. Haase, Experiences with fine-grained parallel genetic algorithms, Ann. Oper. Res.90 (1999) 203–219.  Zbl0937.90092
  17. R. Kolisch, A. Drexel, Adaptative search for solving hard project scheduling problem, Nav. Res. Logist.43 (1996) 23–40.  Zbl0870.90069
  18. R. Kolisch, Serial and Parallel resource-constrained project scheduling methods revisited: Theory and computation, Eur. J. Oper. Res.90 (1996) 320–333.  Zbl0916.90151
  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.  Zbl0870.90069
  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.  Zbl0870.90070
  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.  Zbl1004.90036
  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.  Zbl0927.90054
  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.  Zbl0395.90036
  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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.