A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem

Reza Zamani

RAIRO - Operations Research (2012)

  • Volume: 46, Issue: 1, page 23-39
  • ISSN: 0399-0559

Abstract

top
This paper presents a hybrid schedule generation scheme for solving the resource-constrained project scheduling problem. The scheme, which is called the Polarized Adaptive Scheduling Scheme (PASS), can operate in a spectrum between two poles, namely the parallel and serial schedule generation schemes. A polarizer parameter in the range between zero and one indicates how similarly the PASS behaves like each of its two poles. The presented hybrid is incorporated into a novel genetic algorithm that never degenerates, resulting in an effective self-adaptive procedure. The key point of this genetic algorithm is the embedding of the polarizer parameter as a gene in the genomes used. Through this embedding, the procedure learns via monitoring its own performance and incorporates this knowledge in conducting the search process. The computational experiments indicate that the procedure can produce optimal solutions for a large percentage of benchmark instances.

How to cite

top

Zamani, Reza. "A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem." RAIRO - Operations Research 46.1 (2012): 23-39. <http://eudml.org/doc/276399>.

@article{Zamani2012,
abstract = {This paper presents a hybrid schedule generation scheme for solving the resource-constrained project scheduling problem. The scheme, which is called the Polarized Adaptive Scheduling Scheme (PASS), can operate in a spectrum between two poles, namely the parallel and serial schedule generation schemes. A polarizer parameter in the range between zero and one indicates how similarly the PASS behaves like each of its two poles. The presented hybrid is incorporated into a novel genetic algorithm that never degenerates, resulting in an effective self-adaptive procedure. The key point of this genetic algorithm is the embedding of the polarizer parameter as a gene in the genomes used. Through this embedding, the procedure learns via monitoring its own performance and incorporates this knowledge in conducting the search process. The computational experiments indicate that the procedure can produce optimal solutions for a large percentage of benchmark instances.},
author = {Zamani, Reza},
journal = {RAIRO - Operations Research},
keywords = {Project-scheduling; resource-constrained; heuristics; project-scheduling},
language = {eng},
month = {5},
number = {1},
pages = {23-39},
publisher = {EDP Sciences},
title = {A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem},
url = {http://eudml.org/doc/276399},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Zamani, Reza
TI - A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem
JO - RAIRO - Operations Research
DA - 2012/5//
PB - EDP Sciences
VL - 46
IS - 1
SP - 23
EP - 39
AB - This paper presents a hybrid schedule generation scheme for solving the resource-constrained project scheduling problem. The scheme, which is called the Polarized Adaptive Scheduling Scheme (PASS), can operate in a spectrum between two poles, namely the parallel and serial schedule generation schemes. A polarizer parameter in the range between zero and one indicates how similarly the PASS behaves like each of its two poles. The presented hybrid is incorporated into a novel genetic algorithm that never degenerates, resulting in an effective self-adaptive procedure. The key point of this genetic algorithm is the embedding of the polarizer parameter as a gene in the genomes used. Through this embedding, the procedure learns via monitoring its own performance and incorporates this knowledge in conducting the search process. The computational experiments indicate that the procedure can produce optimal solutions for a large percentage of benchmark instances.
LA - eng
KW - Project-scheduling; resource-constrained; heuristics; project-scheduling
UR - http://eudml.org/doc/276399
ER -

References

top
  1. D.D. Bedworth and J.E. Bailey, Integrated production control systems-management, analysis, design. Wiley, New York (1982).  
  2. K. Bouleimen and H. Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur. J. Oper. Res.149 (2003) 268–281.  Zbl1040.90015
  3. P. Bruckeret al., A branch and bound algorithm for the resource-constrained project scheduling problem. Eur. J. Oper. Res.107 (1998) 272–288.  Zbl0970.90030
  4. I. Charon and O. Hudry, The noising method : a new method for combinatorial optimization. Oper. Res. Lett.14 (1993) 133–137.  Zbl0798.90118
  5. R.-M. Chen and S.-T. Lo, Using an enhanced ant colony system to solve resource-constrained project scheduling problem. Int. J. Comput. Sci. Netw. Secur.6 (2006) 75–84.  
  6. J.H. Cho and Y.D. Kim, A simulated annealing algorithm for resource constrained project scheduling problems. Oper. Res. Soc.48 (1997) 736–744.  Zbl0881.90069
  7. P. Chrétienne and F. Sourd, PERT scheduling with convex cost functions. Theor. Comput. Sci.292 (2003) 145–164.  Zbl1059.90066
  8. B. De Reyck and W. Herroelen, A branch-and-bound procedure for the resource-constrained project scheduling problem with generalised precedence relations. Eur. J. Oper. Res.111 (1998) 152–174.  Zbl0948.90077
  9. E. Demeulemeester and W. Herroelen, A branch-and-bound procedure for multiple resource-constrained project scheduling problem. Manage. Sci.38 (1992) 1803–1818.  Zbl0761.90059
  10. E. Demeulemeester and W. Herroelen, A new benchmark results for the resource-constrained project scheduling problem. Manage. Sci.43 (1997) 1485–1492.  Zbl0914.90160
  11. U. Dorndorf, E. Pesch and T. Phan-Huy, A branch-and-bound algorithm for the resource-constrained project scheduling problem. Math. Methods Oper. Res.52 (2000) 413–439.  Zbl1023.90024
  12. S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling. Nav. Res. Logist.45 (1998) 733–750.  Zbl0936.90024
  13. S. Hartmann, A self-adapting genetic algorithm for project scheduling under resource constraints. Nav. Res. Logist.49 (2002) 433–448.  Zbl1013.90062
  14. S. Hartmann and R. Kolisch, Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res.127 (2000) 394–407.  Zbl0985.90036
  15. W. Herroelen, B. De Reyck and E. Demeulemeester, Resource-constrained project scheduling : A survey of recent developments. Comput. Oper. Res.25 (1998) 279–302.  Zbl1040.90525
  16. P. Jedrzejowicz and E. Ratajczak-Ropel, Agent-based approach to solving the resource constrained project scheduling problem, in Adaptive and natural computing algorithms. Springer LNCS4431 (2007) 480–487.  
  17. J. Kelley, The critical-path method : resource planning and scheduling, in Industrial scheduling, edited by J.F. Muth and G.L. Thompson. Prentice-Hall, New Jersey (1963) 347–365.  
  18. R. Kolisch, Project scheduling under resource constraints – efficient heuristics for several problem classes. Heidelberg Physica (1995).  
  19. R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited : Theory and computation. Eur. J. Oper. Res90 (1996) 320–333.  Zbl0916.90151
  20. R. Kolisch, Efficient priority rules for the resource-constrained project scheduling problem. J. Oper. Manage.14 (1996) 179–192.  
  21. R. Kolisch and A. Drexl, Adaptive search for solving hard project scheduling problems. Nav. Res. Logist.43 (1996) 23–40.  Zbl0870.90069
  22. R. Kolisch and S. Hartmann, Experimental investigation of heuristics for resource-constrained project scheduling : An update. Eur. J. Oper. Res.174 (2006) 23–37.  Zbl1116.90047
  23. R. Kolisch and A. Sprecher, PSPLIB – A project scheduling library. Eur. J. Oper. Res.96 (1996) 205–216.  Zbl0947.90587
  24. K. Li, and R. Willis, An iterative scheduling technique for resource-constrained project. scheduling. Eur. J. Oper. Res.56 (1992) 370–379.  Zbl0825.90536
  25. J.J.M. Mendes, J.F. Goncalves and M.G.C. Resende, A random key based genetic algorithm for the resource constrained project scheduling problem. Comput. Oper. Res.36 (2009) 92–109.  Zbl1163.90500
  26. A. Mingozzi, et al., An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Manage. Sci.44 (1998) 714–729.  Zbl1004.90036
  27. R.H. Möhringet al.Solving project scheduling problems by minimum cut computations. Manage. Sci.49 (2003) 330–350.  Zbl1232.90213
  28. M. Mori and C. Tseng, A genetic algorithm for multi-mode resource constrained project scheduling problem. Eur. J. Oper. Res.100 (1997) 134–141.  Zbl0947.90589
  29. T. Nazarethet al., The multiple resource constrained project scheduling problem : A breadth-first approach. Eur. J. Oper. Res.112 (1999) 347–366.  Zbl0938.90031
  30. J. Orlinet al., Very large scale neighborhood search. Int. Trans. Oper. Res.7 (2000) 301–317.  
  31. L. Özdamar and G. Ulusoy, A survey on the resource-constrained project scheduling problem. IIE Trans.27 (1995) 574–586.  
  32. M. Palpant, C. Artigues and P. Michelon, LSSPER : Solving the resource-constrained project scheduling problem with large neighbourhood search. Ann. Oper. Res.131 (2004) 237–257.  Zbl1066.90037
  33. D. Panagiotakopoulos, A CPM time-cost computational algorithm for arbitrary activity cost functions. INFOR15 (1977) 183–195.  Zbl0363.90055
  34. A. Sprecher, Scheduling resource-constrained projects competitively at modest memory requirement. Manage. Sci.46 (2000) 710–723.  Zbl1231.90217
  35. P. Tormos and A. Lova, A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res.102 (2001) 65–81.  Zbl1024.90045
  36. L.-Y. Tseng and S.-C. Chen, A hybrid metaheuristic for the resource-constrained project scheduling problem. Eur. J. Oper. Res.175 (2006) 707–721.  Zbl1142.90411
  37. V. Valls, F. Ballestin, and S. Quintanilla, A population-based approach to the resource-constrained project scheduling problem. Ann. Oper. Res.131 (2004) 305–324.  Zbl1066.90044
  38. V. Valls, F. Ballestin and S. Quintanilla, Justification and RCPSP : A technique that pays. Eur. Oper. Res.165 (2005) 375–386.  Zbl1066.90045
  39. R. Zamani, An effective near-optimal state-space search method : an application to a scheduling problem. Artif. Intell. Rev.22 (2004) 41–69.  Zbl1082.68104
  40. R. Zamani, An accelerating two-layer anchor search with application to the resource-constrained project scheduling problem. IEEE Trans. Evol. Comput.14 (2010) 975–984.  
  41. R. Zamani and S.K. Lau, Embedding learning capability in lagrangean relaxation : An application to the travelling salesman problem. Eur. J. Oper. Res.201 (2010) 82–88.  Zbl1177.90402

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.