An efficient meta-heuristic algorithm for project scheduling with multiple modes

مهندسی عمران فردوسی

Article 8, Volume 27, Issue 1, March 2016, Pages 101-114   

Document Type: پژوهشی

DOI: 10.22067/civil.v27i1.26216

Authors

Mohammad Hassan Sebt^* ; Mohammad Reza Afshar; Yagub Alipouri

Amirkabir University of Technology

Abstract

In this paper, a Fully Informed Particle Swarm (FIPS) algorithm is proposed for solving the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. In the proposed FIPS, A random key and the related mode list (ML) representation scheme are used as encoding schemes and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. In particular, a new fitness function which reduces the average deviation from optimality and CPU-time is presented. Comparing the results of the proposed FIPS with other approaches using the well-known benchmark sets in PSPLIB validate the effectiveness of the proposed algorithm to solve the MRCPSP.

Keywords

Multi-mode Resource Constrained Project Scheduling Problem; Precedence constraints; Resource constraints; Fully informed particle swarm (FIPS) algorithm; Random key representation

Supplementary Files

8-8sebt.eng.pdf

References

Chen, P. and Weng, H., "A two-phase GA model for resource-constrained project scheduling", Automation in Construction, Vol. 28, pp. 485-498, (2009).

2. Zhang, H., "Ant Colony Optimization for Multimode Resource-Constrained Project Scheduling", American Society of Civil Engineers, Vol. 28, pp. 150-159, (2012).

3. Sprecher, A. and Drexl, A., "Solving multi-mode resource-constrained project scheduling problems by a simple, general and powerful sequencing algorithm", European Journal of Operational Research, Vol. 107, pp. 431–450, (1998).

4. Glover, F. and Greenberg H.J., "New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence", European Journal of Operational Research, Vol. 39, pp. 119-130, (1989).

5. Jo´ zefowska, J. Mika, M. Rozycki, R. Waligora, G. and Weglarz, J., "Simulated annealing for multi-mode resource-constrained project scheduling", Annals of Operations Research, Vol. 102, pp. 137–155, (2001).

6. Zhang, H. Tom, C.M. and Li, H., "Multimode Project Scheduling Based on Particle Swarm Optimization", Computer-Aided Civil and Infrastructure Engineering, Vol. 21, pp. 93– 103, (2006).

7. Lova, A. Tormos, P. Cervantes, M. and Barber, F., "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes", International Journal of Production Economics, Vol. 117 (2), pp. 302– 316, (2009).

8. Peteghme, V.V. and Vanhoucke, M., "An artificial immune system for the multi-mode resource-constrained project scheduling problem", in: EvoCOP, Springer, Berlin, Tubingen, Germany, pp. 100-107, (2009).

9. Peteghem, V.V. and Vanhoucke, M., "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 201, pp. 409–418, (2010).

10. Elloumi, S. and Fortemps, P., "A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 205, pp. 31–41, (2010).

11. Wang, L. and Fang, C. "An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem", Information Sciences, Vol. 181, pp. 4804–4822, (2011).

12. Wang, L. and Fang, C., "An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem", Computers and Operations Research, Vol. 39, pp. 449–460, (2012).

13. Lee, K. and El-Sharkawi, M., "Modern heuristic optimization techniques", Hoboken, New Jersey, John Wiley and Sons, pp. 50-157, (2008).

14. Damak, N. Jarboui, B. Siarry, P. and Loukil, T., "Differential evolution for solving multi-mode resource constrained project scheduling problems", Computers and Operations Research, Vol. 36, pp. 2653-2659, (2009).

15. Mendes, R. Kennedy, J. and Neves, J., "The Fully Informed Particle Swarm: Simpler, Maybe Better", IEEE Transactions on Evolutionary Compution, Vol. 14, pp. 204-210, (2004).

16. Sprecher, A. Hartmann, S. and Drexl, A., "An exact algorithm for project scheduling with multiple modes", OR Spektrum: Organ der Deutschen Gesellschaft fur Operations Research, Vol. 19(3), pp. 195-203, (1997).

17. Kolisch, R., "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation", European Journal of Operational Research, Vol. 43, pp. 23–40, (1996).

18. Tormos, P. and Lova, A., "A competitive heuristic solution technique for resource-constrained project scheduling", Annals of Operations Research, Vol. 102, pp. 65–81, (2001).

19. Ranjbar, M. Reyck, B. and De Kianfar, F., "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling", European Journal of Operational Research, Vol. 193(1), pp. 35–48, (2009).

20. Alcaraz, J. Maroto, C. and Ruiz, R., "Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms", Journal of the Operational Research Society, Vol. 54, pp. 614–626, (2003).