An Efficient Genetic Agorithm for Solving the Multi-Mode Resource-Constrained Project Scheduling Problem Based on Random Key Representation

Sebt, Mohammad Hassan; Afshar, Mohammad Reza; Alipouri, Yagub

doi:10.22034/2015.3.06

An Efficient Genetic Agorithm for Solving the Multi-Mode Resource-Constrained Project Scheduling Problem Based on Random Key Representation

Document Type : Research Paper

Authors

Amirkabir University of Technology, Tehran, Iran

10.22034/2015.3.06

Abstract

In this paper, a new genetic algorithm (GA) is presented 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. 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 this paper, a simple, efficient fitness function is proposed which has better performance compared to the other fitness functions in the literature. Defining a new mutation operator for ML is the other contribution of the current study. Comparing the results of the proposed GA with other approaches using the well-known benchmark sets in PSPLIB validates the effectiveness of the proposed algorithm to solve the MRCPSP.

Keywords

Main Subjects

operations planning,scheduling & control

References

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

Anderson E. and Ferris M. (1994). Genetic algorithm for combinatorial optimization: assembly line balancing problem. Operations Research Society of America journal on computing, Vol. 6, pp. 161–173.

Beşikci U. Bilge Ü. and Ulusoy, G. (2015). Multi-mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research, Vol. 240 (1), pp. 22-31.

Chaleshtari A.S. and Shadokh S. (2014). A branch and cut algorithm for resource-constrained project scheduling problem subject to nonrenewable resource with pre-scheduled procurement Arabian Journal of Science Engineering, Vol. 39, pp. 8359- 8369.

Cheng, J. Fowler, J. Kempf, K. and Mason, S. (2015). Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting. Computers & Operations Research, Vol. 53, pp. 275-287.

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

Drexl A. and Grünewald J. (1993). Nonpreemptive multi-mode resource-constrained project scheduling. IIE Transactions, Vol. 25, pp. 74–81.

Elloumi S. and Fortemps P. (2010). 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.

Eschelman L., Caruana R. and Schaffer D. (1989). Biases in the Crossover Landscape. Proc. third international conference on genetic algorithms, Morgan Kaufman Publishing, February, pp. 21-29.

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

Guangqiang Li, G. Zhao F. Guo C. and Teng H. (2006). Parallel Hybrid PSO-GA Algorithm and Its Application to Layout Design. ICNC 2006, Part I, LNCS 4221, pp. 749–758.

Haoa X. Linb L. Gen M. (2014). An Effective Multi-objective EDA for Robust Resource Constrained Project Scheduling with Uncertain Durations. Procedia Computer Science, Vol. 36, pp. 571-578.

Hartmann S. (2001). Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, Vol. 102, pp. 111–135.

Hartmann S. and Briskorn D. (2009). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, Vol. 207, pp. 1-14.

Hartmann S. and Drexl A. (1998). Project scheduling with multiple modes: A comparison of exact algorithms. Networks, Vol. 32, pp. 283–297.

Hartmann S. and Sprecher A. (1996). A note on `Hierarchical models for multi-project planning and scheduling. European Journal of Operational Research, Vol. 94, pp. 377-383.

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

Juang C.F. (2004). A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design. IEEE TRANSACTIONS ON SYSTEMS, Vol. 34 (2), pp. 997-1006.

Kao Y.T. and Zahara E. 2008. “A hybrid genetic algorithm and particle swarm optimization for multimodal functions. Applied Soft Computing, Vol. 8, pp. 849–857.

Kolisch R. and Drexl A. (1997). Local search for non-preemptive multi-mode resource constrained project scheduling. IIE Transactions, Vol. 29, pp. 987–999.

Lee K. and El-Sharkawi M. (2008). Modern heuristic optimization techniques.

Lova, A., Tormos P. and Barber F. (2006). Multi-mode resource constrained project scheduling: Scheduling schemes, priority rules and mode selection rules. Inteligencia Artificial, Vol. 30, pp. 69–86.

Lova A., Tormos P. Cervantes M. and Barber F. (2009). 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.

Marco A. and Stützle T. (2008). Convergence behavior of the fully informed particle swarm optimization algorithm. Proceedings of the 10th annual conference on Genetic and evolutionary computation, January, pp.71-78.

Mendes J., Gonçalves J. and Resende M. (2009). A random key based genetic algorithm for the resource constrained project scheduling problem. Computers and Operations Research, Vol. 36, pp. 92–109.

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

Montgomery D.C. (2005). Design and analysis of experiments. Arizona, John Wiley & Sons Press.
Mori M. and Tseng C. (1997). A genetic algorithm for multi-mode resource constrained project scheduling problem. European Journal of Operational Research, Vol. 100, pp. 134–141.

Özdamar L. 1999. A genetic algorithm approach to a general category project scheduling problem. IEEE Transactions on Systems, Vol. 29, pp. 44–59.

Patterson J.H., Słowinski R. Talbot F. and Weglarz J. (1989). An algorithm for a general class of precedence and resource constrained scheduling problems. Advances in Project Scheduling, pp. 3–28.

Peteghem V.V. and Vanhoucke M. (2009). An artificial immune system for the multi-mode resource-constrained project scheduling problem. In: EvoCOP, Springer.

Peteghem V.V. and Vanhoucke M. (2010). 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.

Peteghem V.V. and Vanhoucke M. (2014). An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research, Vol. 235 (1), pp. 62–72.

Qi J.J. Liu, Y.J. Lei H.T. and Guo B. (2014). Solving the multi-mode resource availability cost problem in project scheduling based on modified particle swarm optimization. Arabian Journal of Science Engineering, Vol. 39, pp. 5279- 5288.

Ranjbar M. Reyck B. and Kianfar F. (2009). “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.

Slowinski R. (1980). Two approaches to problems of resource allocation among project activities – A comparative study. Journal of Operational Research Society, Vol. 8, pp. 711–723.

Slowinski R. Soniewicki B. and Weglarz J. (1994). DSS for multi-objective project scheduling. European Journal of Operational Research, Vol. 79, pp. 220–229.

Spears W. and De Jong K. (1991). On the virtues of parameterized uniform crossover. In: Proceedings of the fourth international conference on genetic algorithms, February, pp. 230–236.

Speranza M.G. and Vercellis C. (1993). Hierarchical models for multi-project planning and scheduling. European Journal of Operational Research, Vol. 64, pp. 312-325.

Sprecher A. (1994). Resource-constrained project scheduling: exact methods for the multi-mode case. Lecture Notes in Economics and Mathematical Systems.

Sprecher A. and Drexl A. (1998). 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.

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

Talbot F.B . 198 Management Science, Vol. 28, pp. 1197–1210.

Tseng L.Y. and Chen S.C. (2009). Two-phase genetic local search algorithm for the multi-mode resource-constrained project scheduling problem. IEEE Transactions on Evolutionary Computation, Vol. 13 (4), pp. 848–57.

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

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

Wauters T. Verbeeck K. Berghe G. and De Causmaecker P.(2009). A multi-agent learning approach for the multi-mode resource-constrained project scheduling problem. In: Proceedings of the 8th International Conference on Autonomous Agents and Multi agent Systems, June, pp. 1-8.

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

Zhu G., Bard J. and Tu G. (2006). A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. Journal on Computing, Vol. 18 (3), pp. 377–39.