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.

Keywords: 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://archive.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://archive.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://archive.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, Volume 48 (2014) no. 4, pp. 595-614. doi : 10.1051/ro/2014025. http://archive.numdam.org/articles/10.1051/ro/2014025/

[1] Using Ant Colony Optimization algorithm for solving project management problems. Exp. Syst. Appl. 36 (1999) 10004-10015.

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

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

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

,[5] 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] A new efficient simulated annealing algorithm for the resource constrained project scheduling problem. Eur. J. Oper. Res. 149 (2003) 268-281. | MR | Zbl

and ,[7] 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

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

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

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

, and ,[11] Nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 25 (1993) 74-81.

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

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

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

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

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

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

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

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

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

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

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

,[23] 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

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

and ,[25] 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] DSS for multiobjective project scheduling subject to multiple-category resource constraints. Eur. J. Oper. Res. 79 (1994) 220-229. | Zbl

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

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

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

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

, et al.,[31] Particle swarm optimization for resource-constrained project scheduling. Int. J. Project Manag. 24 (2006) 83-92.

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

, and ,*Cited by Sources: *