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.  
  3. P. Bruckeret al., A branch and bound algorithm for the resource-constrained project scheduling problem. Eur. J. Oper. Res.107 (1998) 272–288.  
  4. I. Charon and O. Hudry, The noising method : a new method for combinatorial optimization. Oper. Res. Lett.14 (1993) 133–137.  
  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.  
  7. P. Chrétienne and F. Sourd, PERT scheduling with convex cost functions. Theor. Comput. Sci.292 (2003) 145–164.  
  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.  
  9. E. Demeulemeester and W. Herroelen, A branch-and-bound procedure for multiple resource-constrained project scheduling problem. Manage. Sci.38 (1992) 1803–1818.  
  10. E. Demeulemeester and W. Herroelen, A new benchmark results for the resource-constrained project scheduling problem. Manage. Sci.43 (1997) 1485–1492.  
  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.  
  12. S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling. Nav. Res. Logist.45 (1998) 733–750.  
  13. S. Hartmann, A self-adapting genetic algorithm for project scheduling under resource constraints. Nav. Res. Logist.49 (2002) 433–448.  
  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.  
  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.  
  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.  
  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.  
  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.  
  23. R. Kolisch and A. Sprecher, PSPLIB – A project scheduling library. Eur. J. Oper. Res.96 (1996) 205–216.  
  24. K. Li, and R. Willis, An iterative scheduling technique for resource-constrained project. scheduling. Eur. J. Oper. Res.56 (1992) 370–379.  
  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.  
  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.  
  27. R.H. Möhringet al.Solving project scheduling problems by minimum cut computations. Manage. Sci.49 (2003) 330–350.  
  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.  
  29. T. Nazarethet al., The multiple resource constrained project scheduling problem : A breadth-first approach. Eur. J. Oper. Res.112 (1999) 347–366.  
  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.  
  33. D. Panagiotakopoulos, A CPM time-cost computational algorithm for arbitrary activity cost functions. INFOR15 (1977) 183–195.  
  34. A. Sprecher, Scheduling resource-constrained projects competitively at modest memory requirement. Manage. Sci.46 (2000) 710–723.  
  35. P. Tormos and A. Lova, A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res.102 (2001) 65–81.  
  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.  
  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.  
  38. V. Valls, F. Ballestin and S. Quintanilla, Justification and RCPSP : A technique that pays. Eur. Oper. Res.165 (2005) 375–386.  
  39. R. Zamani, An effective near-optimal state-space search method : an application to a scheduling problem. Artif. Intell. Rev.22 (2004) 41–69.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.