Dual-objective Preemptive Multi-mode Resource-Constrained Project Scheduling Problem Optimization Model

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Faculty of Technology and Engineering, University of Guilan, Iran

2 Department of Chemical Engineering, Faculty of Technology and Engineering, University of Guilan, Iran

3 Department of Industrial Engineering, Kooshyar Higher Educational Institute, Rasht, Iran

Abstract

The Multi-Mode Resource Constrains Project Scheduling Problem (MRCPSP) tries to find the best sequence of activities in a manner that involves more than one type of operating mode and in the presence of resource constraints, project’s precedence constraints must be satisfied. In each execution mode, the amount of resources and execution time are specified and different. In The Preemptive multi-mode Resource Constraints Project Scheduling Problem (P-MRCPSP), each operating mode activity can be interrupted and restarted at any time without any extra cost. In this paper, minimizing the completion time along with maximizing the current net value of the project in the P-MRCPSP are considered. After solving the problem by using Epsilon limits method, according to NP-hard problem and multi-objective model, multi-objective particle swarm optimization (MOPSO) has been developed to achieve optimum scheduling. In order to evaluate the proposed method’s efficiency, results have been compared to non-dominance genetic algorithm sorting (NSGAII) based on designed indicators. The Taguchi method has been used in experimental design, to adjust these two algorithms’ parameters. The results of the model solution show the strength of MOPSO algorithm.

Keywords


1. Russell, A. H. (1970). “Cash flows in networks”, Management Sci., Vol. 16, No. 5, PP. 357- 373.
2. Grinold, R. C. (1972). “The payment scheduling problem”, Naval Research Logistics Quarterly, Vol. 19, No. 1, PP. 123- 136.
3. Amin-Tahmasbi, H., Tavakkoli-Moghaddam, R. & Iranmansh, H. (2009). “Project planning in presence of resource constraint with immune algorithm”, 5th Int project management Conf., Tehran.
4. Khalili-Damghani, K., Tavakkoli-Moghaddam, R. & Tabari, M. (2011). “Solve of resource-constrained project scheduling problem using modified ant colony algorithm”, J. of Industrial Engineering, Vol. 45, No. 1, PP. 59- 69.
5. Talbot, F. B. (1982). “Resource-constrained project scheduling with time-resource trade-offs: The nonpreemptive case”, Management Sci., Vol. 28, No. 10, PP. 1197– 1210.
6. Al-Fawzan, M. A. & Haouari, M. (2005). “A bi-objective model for robust resource-constrained project scheduling”, Int.J.of Production Economics, Vol. 96, No. 2, PP. 175-187.
7. Peteghem, V. & Vanhoucke, M. (2010). “A genetic algorithm for the preemptive and on reemptive multi-mode resource constrained project-scheduling problem”, European Journal of Operational Research, Vol. 201, No. 2, PP. 409– 418.
8. Seifi, M. & Tavakkoli-Moghaddam, R. (2008). “A new bi-objective model for a multimode resource-constrained project scheduling problem with discounted cash flows and four payments model”, International Journal of Engineering, Transactions A: Basics, Vol. 21, No. 4, PP. 347– 360.
9. Chen, Z. J. & Chyu, C. C. (2010). “A dual-population memetic algorithm for minimizing total cost of multi-mode resource-constrained project scheduling”, Industrial Engineering and Management Systems, Vol. 9, No. 2, PP. 70- 79.
10. Coelho, J. & Vanhoucke, M. (2011). “Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers Original”, European Journal of Operational Research, Vol. 213, No. 1, PP. 73- 82.
11. Azimi, F., Aboutalebi, R. & Najafi, A. A. (2011). “Using multi-objective particle swarm optimization for bi-objective multi-mode resource-constrained project scheduling problem”, World Academy of Science, Engineering and Technology, International Journal of Mechanical, Aerospace, Industrial, Mechatronic and Manufacturing Engineering, Vol. 5, No. 6, PP. 1015- 1019.
12. Wang, L. & Fang, Ch. (2012). “An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem”, Computers & Operations Research, Vol, 39. No. 2, PP. 449- 460.
13. Li, H. & Zhang, H. (2013). “Ant colony optimization-based multi-mode scheduling under renewable and nonrenewable resource constraints”, Automation in Construction, Vol. 35, PP. 431- 438.
14. Hao, X., Lin, 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.
15. Roghanian, E. (2014). “A Bi-objective pre-emption multi-mode resource constrained project scheduling problem with due dates in the activities”, Journal of Optimization in Industrial Engineering, Vol 7, No. 15, PP. 15- 25
16. Cheng, J., Fowler, J., Kempf, K. & Mason, S. (2015). “Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting”, Computers & Operations Research, Vol. 53, PP. 275- 287.
17. Shou, Y., Li, Y. & Lai, Ch. (2015). “Hybrid particle swarm optimization for preemptive resource-constrained project scheduling”, Neurocomputing, Vol. 148, PP. 122- 128.
18. Moukrim, A., Quilliot, A. & Toussaint, H. (2015). “An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal Interval Order Enumeration”, European Journal of Operational Research, Vol. 244, No. 2, PP. 360- 368.
19. Farshidi, S. & Ziarati, K. (2016). “A bi- population genetic algorithm with two novel greedy mode selection methods for MRCPSP”, ACSIJ Advances in Computer Science: An International Journal, Vol. 5, No. 22, PP. 66- 77.
20. Asta, Sh. Karapetyan, D. Kheiri, A. Özcan, E. & Parkes, A. J. (2016). “Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem”,
Information Sciences, Vol. 373, PP. 476- 498.
21. Elloumi, S., Fortemps, Ph. & Loukilc, T. (2017). “Multi-objective algorithms to multi-mode resource-constrained projects under mode change disruption”, Computers & Industrial Engineering, Vol. 106, PP. 161– 173.
22. Ballestín, F. & Blanco, R. (2011). “Theoretical and practical fundamentals for multi-objective optimization in resource-constrained project scheduling problems”, Computers & Operations Research, Vol. 38, No. 1, PP. 51– 62.
23. Buddhakulsomsiri, J. & Kim, D. S. (2006). “Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting”, European Journal of Operational Research, Vol. 175, No. 1, PP. 279- 295.
24. Liu, B., Wang, L. & Jin, Y. H. (2008). “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”, Computers & Operations Research, Vol. 35, No. 9, PP. 2791- 2806.
25. Chen, R. M., Wu, C. L., Wang, C. M. and Lo, S. T. (2010). “Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB”, Expert systems with applications, Vol. 37, No. 3, PP. 1899- 1910.
26. Tavakkoli-Moghaddam, R., Azarkish, M. & Sadeghnejad-Barkousaraie, A. (2011). “Solving a multi-objective job shop-scheduling problem with sequence-dependent setup times by a Pareto archive PSO combined with genetic operators and VNS”, The International Journal of Advanced Manufacturing Technology, Vol. 53, No. 5- 8, PP. 733- 750.
27. Amiri, M., Abtahi, A. R. & Khalili-Damghani, K. (2013). “Solving a generalised precedence multi-objective multi-mode time-cost-quality trade-off project-scheduling problem using a modified NSGA-II algorithm”, International Journal of Services and Operations Management, Vol. 14, No. 3, PP. 355- 372.
28. Coello Coello, C. A., Van Veldhuizen, D. A. & Lamont, G. B. (2002). Evaluationary algorithm for solving multi-objective problems, Kluwer Academic Pub. Co., New York.