An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem

Peng Wuliang; Huang Min; Hao Yongping

RAIRO - Operations Research - Recherche Opérationnelle (2014)

  • Volume: 48, Issue: 4, page 595-614
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Wuliang, Peng, Min, Huang, and Yongping, Hao. "An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem." RAIRO - Operations Research - Recherche Opérationnelle 48.4 (2014): 595-614. <http://eudml.org/doc/275032>.

@article{Wuliang2014,
abstract = {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.},
author = {Wuliang, Peng, Min, Huang, Yongping, Hao},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {operations research; mathematical programming},
language = {eng},
number = {4},
pages = {595-614},
publisher = {EDP-Sciences},
title = {An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem},
url = {http://eudml.org/doc/275032},
volume = {48},
year = {2014},
}

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
PB - EDP-Sciences
VL - 48
IS - 4
SP - 595
EP - 614
AB - 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.
LA - eng
KW - operations research; mathematical programming
UR - http://eudml.org/doc/275032
ER -

References

top
  1. [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. [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. Zbl1095.90541
  3. [3] J. Bautista and J. Pereira, Ant colonies for the RCPS problem. Lect. Notes in Comput. Sci.2504 (2002) 257–268. Zbl1028.90517
  4. [4] F.F. Boctor, Heuristics for scheduling projects with resource restrictions and several resource-duration modes. Int. J. Prod. Res.31 (1993) 2547–2558. Zbl0916.90143
  5. [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. Zbl0916.90143
  6. [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. Zbl1040.90015MR1993132
  7. [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. Zbl1107.90015
  8. [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. [9] E. Demeulemeester and W. Herroelen, Project scheduling: A research handbook. Kluwer Academic Publishers (2002). Zbl1059.90068
  10. [10] M. Dorigo, V. Maniezzo and A. Colorni, Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern26 (1996) 29–41. 
  11. [11] A. Drexl and J. Grünewald, Nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans.25 (1993) 74–81. 
  12. [12] S.E. Elmaghraby, Activity networks: project planning and control by network models. Wiley, New York (1997). Zbl0385.90076
  13. [13] S. Hartmann, Project scheduling with multiple modes: a genetic algorithm. Annal. Oper. Res.102 (2001) 111–135. Zbl1024.90039MR1854421
  14. [14] S. Hartmann and A. Drexl, Project scheduling with multiple modes: a comparison of exact algorithms. Networks32 (1998) 283–297. Zbl1002.90025MR1660047
  15. [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. Zbl0985.90036
  16. [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. Zbl1180.90125MR2379216
  17. [17] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisitedtheory and computation. Eur. J. Oper. Res.90 (1996) 320–333. Zbl0916.90151
  18. [18] R. Kolisch and A. Drexl, Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans.29 (1997) 987–999. 
  19. [19] R. Kolisch and A. Sprecher, PSPLIB-A project scheduling problem library. Eur. J. Oper. Res.96 (1997) 205–216. Zbl0947.90587
  20. [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.s117 (2009) 302–316. 
  21. [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. [22] L. Ozdamar, A genetic algorithm approach to a general category project scheduling problem. IEEE Trans. Syst. Man Cybern.29 (1999) 44–59. 
  23. [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. Zbl1175.90205MR2552443
  24. [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. [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. Zbl1152.90464
  26. [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. Zbl0815.90099
  27. [27] A. Sprecher, S. Hartmann and A. Drexl, An exact algorithm for the project scheduling with multiple modes. OR Spektrum19 (1997) 195–203. Zbl0885.90059MR1464665
  28. [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. Zbl0943.90042
  29. [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. Zbl1142.90411
  30. [30] C. Wang, et al., An efficient hybrid algorithm for resource-constrained project scheduling. Inform. Sci.180 (2010) 1031–1039. 
  31. [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. [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. Zbl1241.90168

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.