A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 23-39.

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.

DOI : 10.1051/ro/2012006
Classification : 90B35
Mots-clés : project-scheduling, resource-constrained, heuristics 
@article{RO_2012__46_1_23_0,
     author = {Zamani, Reza},
     title = {A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {23--39},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ro/2012006},
     mrnumber = {2934891},
     zbl = {1241.90060},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2012006/}
}
TY  - JOUR
AU  - Zamani, Reza
TI  - A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2012
SP  - 23
EP  - 39
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2012006/
DO  - 10.1051/ro/2012006
LA  - en
ID  - RO_2012__46_1_23_0
ER  - 
%0 Journal Article
%A Zamani, Reza
%T A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2012
%P 23-39
%V 46
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2012006/
%R 10.1051/ro/2012006
%G en
%F RO_2012__46_1_23_0
Zamani, Reza. A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 23-39. doi : 10.1051/ro/2012006. http://archive.numdam.org/articles/10.1051/ro/2012006/

[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. | MR | Zbl

[3] P. Brucker et al., A branch and bound algorithm for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 107 (1998) 272-288. | Zbl

[4] I. Charon and O. Hudry, The noising method : a new method for combinatorial optimization. Oper. Res. Lett. 14 (1993) 133-137. | MR | Zbl

[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. | Zbl

[7] P. Chrétienne and F. Sourd, PERT scheduling with convex cost functions. Theor. Comput. Sci. 292 (2003) 145-164. | MR | Zbl

[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. | Zbl

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

[10] E. Demeulemeester and W. Herroelen, A new benchmark results for the resource-constrained project scheduling problem. Manage. Sci. 43 (1997) 1485-1492. | Zbl

[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. | MR | Zbl

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

[13] S. Hartmann, A self-adapting genetic algorithm for project scheduling under resource constraints. Nav. Res. Logist. 49 (2002) 433-448. | MR | Zbl

[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. | Zbl

[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. | MR | Zbl

[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 LNCS 4431 (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. Res 90 (1996) 320-333. | Zbl

[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. | Zbl

[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. | Zbl

[23] R. Kolisch and A. Sprecher, PSPLIB - A project scheduling library. Eur. J. Oper. Res. 96 (1996) 205-216. | Zbl

[24] K. Li, and R. Willis, An iterative scheduling technique for resource-constrained project. scheduling. Eur. J. Oper. Res. 56 (1992) 370-379. | Zbl

[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. | MR | Zbl

[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. | Zbl

[27] R.H. Möhring et al. Solving project scheduling problems by minimum cut computations. Manage. Sci. 49 (2003) 330-350. | Zbl

[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. | Zbl

[29] T. Nazareth et al., The multiple resource constrained project scheduling problem : A breadth-first approach. Eur. J. Oper. Res. 112 (1999) 347-366. | Zbl

[30] J. Orlin et al., Very large scale neighborhood search. Int. Trans. Oper. Res. 7 (2000) 301-317. | MR

[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. | MR | Zbl

[33] D. Panagiotakopoulos, A CPM time-cost computational algorithm for arbitrary activity cost functions. INFOR 15 (1977) 183-195. | Zbl

[34] A. Sprecher, Scheduling resource-constrained projects competitively at modest memory requirement. Manage. Sci. 46 (2000) 710-723. | Zbl

[35] P. Tormos and A. Lova, A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res. 102 (2001) 65-81. | MR | Zbl

[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. | Zbl

[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. | MR | Zbl

[38] V. Valls, F. Ballestin and S. Quintanilla, Justification and RCPSP : A technique that pays. Eur. Oper. Res. 165 (2005) 375-386. | Zbl

[39] R. Zamani, An effective near-optimal state-space search method : an application to a scheduling problem. Artif. Intell. Rev. 22 (2004) 41-69. | Zbl

[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. | MR | Zbl

Cité par Sources :