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.

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 : 10.1051/ro/2014025
Classification : 68M20, 90C59
Mots-clés : operations research, mathematical programming 
@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},
     pages = {595--614},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     doi = {10.1051/ro/2014025},
     mrnumber = {3264395},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014025/}
}
TY  - JOUR
AU  - Wuliang, Peng
AU  - Min, Huang
AU  - Yongping, Hao
TI  - An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2014
SP  - 595
EP  - 614
VL  - 48
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014025/
DO  - 10.1051/ro/2014025
LA  - en
ID  - RO_2014__48_4_595_0
ER  - 
%0 Journal Article
%A Wuliang, Peng
%A Min, Huang
%A Yongping, Hao
%T An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2014
%P 595-614
%V 48
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014025/
%R 10.1051/ro/2014025
%G en
%F 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/articles/10.1051/ro/2014025/

[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

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

[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

[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

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

[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

[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

[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

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

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

[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

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

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

[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

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

[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

[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

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

[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

[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

[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

Cité par Sources :