An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 4, p. 595-614
Le texte intégral des articles récents est réservé aux abonnés de la revue. Consulter l'article sur le site de la revue
Many real-world scheduling problems can be modeled as Multi-mode Resource Constrained Project Scheduling Problems (MRCPSP). However, the MRCPSP is a strong NP-hard problem and very difficult to be solved. The purpose of this research is to investigate a more efficient alternative based on ant algorithm to solve MRCPSP. To enhance the generality along with efficiency of the algorithm, the rule pool is designed to manage numerous priority rules for MRCPSP. Each ant is provided with an independent thread and endowed with the learning ability to dynamically select the excellent priority rules. In addition, all the ants in the ant algorithm have the prejudgment ability to avoid infeasible routes based on the branch and bound method. The algorithm is tested on the well-known benchmark instances in PSPLIB. The computational results validate the effectiveness of the proposed algorithm.
DOI : https://doi.org/10.1051/ro/2014025
Classification:  68M20,  90C59
@article{RO_2014__48_4_595_0,
     author = {Wuliang, Peng and Min, Huang and Yongping, Hao},
     title = {An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     pages = {595-614},
     doi = {10.1051/ro/2014025},
     mrnumber = {3264395},
     language = {en},
     url = {http://http://www.numdam.org/item/RO_2014__48_4_595_0}
}
Wuliang, Peng; Min, Huang; Yongping, Hao. An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 4, pp. 595-614. doi : 10.1051/ro/2014025. http://www.numdam.org/item/RO_2014__48_4_595_0/

[1] H. Abdallah, H.M. Emara, H.T. Dorrah and A. Bahgat, Using Ant Colony Optimization algorithm for solving project management problems. Exp. Syst. Appl. 36 (1999) 10004-10015.

[2] J. Alcaraz, C. Maroto and R. Ruiz, Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. J. Oper. Res. Soc. 54 (2003) 614-626. | Zbl 1095.90541

[3] J. Bautista and J. Pereira, Ant colonies for the RCPS problem. Lect. Notes in Comput. Sci. 2504 (2002) 257-268. | Zbl 1028.90517

[4] F.F. Boctor, Heuristics for scheduling projects with resource restrictions and several resource-duration modes. Int. J. Prod. Res. 31 (1993) 2547-2558. | Zbl 0916.90143

[5] F.F. Boctor, A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes. Eur. J. Oper. Res. 90 (1996) 349-361. | Zbl 0916.90143

[6] K. Bouleimen and H. Lecocq, A new efficient simulated annealing algorithm for the resource constrained project scheduling problem. Eur. J. Oper. Res. 149 (2003) 268-281. | MR 1993132 | Zbl 1040.90015

[7] J. Buddhakulsomsiri and D.S. Kim, Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur. J. Oper. Res. 178 (2007) 374-390. | Zbl 1107.90015

[8] M. Daniel, M. Martin and S. Hartmut, Ant colony optimization for resource-constrained project scheduling. IEEE Trans. Evol. Comput. 6 (2002) 333-346.

[9] E. Demeulemeester and W. Herroelen, Project scheduling: A research handbook. Kluwer Academic Publishers (2002). | Zbl 1059.90068

[10] M. Dorigo, V. Maniezzo and A. Colorni, Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern 26 (1996) 29-41.

[11] A. Drexl and J. Grünewald, Nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 25 (1993) 74-81.

[12] S.E. Elmaghraby, Activity networks: project planning and control by network models. Wiley, New York (1997). | Zbl 0385.90076

[13] S. Hartmann, Project scheduling with multiple modes: a genetic algorithm. Annal. Oper. Res. 102 (2001) 111-135. | MR 1854421 | Zbl 1024.90039

[14] S. Hartmann and A. Drexl, Project scheduling with multiple modes: a comparison of exact algorithms. Networks 32 (1998) 283-297. | MR 1660047 | Zbl 1002.90025

[15] S. Hartmann and R. Kolish, Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127 (2000) 394-407. | Zbl 0985.90036

[16] B. Jarboui, N. Damak and P. Siarry, A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Appl. Math. Comput. 195 (2008) 299-308. | MR 2379216 | Zbl 1180.90125

[17] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisitedtheory and computation. Eur. J. Oper. Res. 90 (1996) 320-333. | Zbl 0916.90151

[18] R. Kolisch and A. Drexl, Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 29 (1997) 987-999.

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

[20] A. Lova, P. Tormos, M. Cervantes and F. Barber, An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. Int. J. Prod. Econ.s 117 (2009) 302-316.

[21] D. Merkle and M. Middendorf, An ant algorithm with a new pheromone evaluation rule for total tardiness problems. Lect. Notes Comput. Sci. 1803 (2000) 287-296.

[22] L. Ozdamar, A genetic algorithm approach to a general category project scheduling problem. IEEE Trans. Syst. Man Cybern. 29 (1999) 44-59.

[23] V.V. Peteghem and M. Vanhoucke, A genetic algorithm for the preemptive and non-preemtive multi-mode resource-constrained project scheduling problem. Eur. J. Oper. Res. 201 (2009) 409-418. | MR 2552443 | Zbl 1175.90205

[24] V.V. Peteghem and M. Vanhoucke, An artificial immune system for the multi-mode resource-constrained project scheduling problem. Evol. Comput. Comb. Optim. 5482 (2009) 85-96.

[25] M. Ranjbar, B. De Reyck, B. and F. Kianfar, A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. Eur. J. Oper. Res. 193 (2008) 35-48. | Zbl 1152.90464

[26] R. Slowinski, B. Soniewicki and J. Weglarz, DSS for multiobjective project scheduling subject to multiple-category resource constraints. Eur. J. Oper. Res. 79 (1994) 220-229. | Zbl 0815.90099

[27] A. Sprecher, S. Hartmann and A. Drexl, An exact algorithm for the project scheduling with multiple modes. OR Spektrum 19 (1997) 195-203. | MR 1464665 | Zbl 0885.90059

[28] A. Sprecher and A. Drexl, Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. Eur. J. Oper. Res. 107 (1998) 431-450. | Zbl 0943.90042

[29] L.Y. Tseng and S.C. Chen, A hybrid meta-heuristic for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 175 (2006) 707-721. | Zbl 1142.90411

[30] C. Wang, et al., An efficient hybrid algorithm for resource-constrained project scheduling. Inform. Sci. 180 (2010) 1031-1039.

[31] H. Zhang, H. Li and C.M. Tam, Particle swarm optimization for resource-constrained project scheduling. Int. J. Project Manag. 24 (2006) 83-92.

[32] G. Zhu, J. Bard and G. Tu, A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem. J. Comput. 18 (2006) 377-390. | Zbl 1241.90168