Non-dominated Sorting Genetic Algorithm-II to Solve Multi Objective Resource-constrained Project Scheduling Problem with Time-cost Trade-off

Document Type : Research Paper

Authors

Abstract

   Scheduling plays an important role in project management. However, in addition to providing suitable scheduling, constraints during project implementation should also be noted. This paper proposes bi-objective resource-constrained project scheduling model with the objectives of minimizing project completion time, as well as minimizing the leveling cost of the used resources, in accordance with the employer demands and the contractor developed. To better study this model performance, a real case study related to the topic, were selected. Since the proposed research problem has been proven to be NP-hard as well as large-scale case study, after analyzing the landscape, genetic algorithm to solve problem were offered. Finally, the results of solving real-world algorithms were compared with the results. Results show that the model and algorithm can be used in other similar projects as well.

Keywords

Main Subjects


ARTIGUES, C., LEUS, R. and NOBIBON, F. T. (2013). “Robust optimization for resource-constrained project scheduling with uncertain activity durations”, Flexible Services and Manufacturing Journal, Vol. 25, No. 1, PP. 175-205.
2. Węglarz, J., J. Józefowska, M. M. and Waligóra, G. (2011). "Project scheduling with finite or infinite number of activity processing modes–A survey", European Journal of Operational Research, Vol. 208, No. 3, PP. 177-205.
3. Herroelen, W. and LEUS, R. (2005). "Project scheduling under uncertainty: Survey and research potentials", European Journal of Operational Research, Vol. 165, No. 2, PP. 289-306.
4. Rummel, J. L., Walter, Z., Dewan, R. and Seidmann, A. (2005). "Activity consolidation to improve responsiveness", European Journal of Operational Research, Vol. 161, No.3, PP. 683-703.
5. Koné, O., Artigues, C., Lopez, P. and Mongeau, M. (2011). "Event-based MILP models for resource-constrained project scheduling problems", Computers & Operations Research, Vol. 38, No. 1, PP. 3-13.
6. Hebert, J. E. and DECKRO, R. F. (2011). "Combining contemporary and traditional project management tools to resolve a project scheduling problem", Computers & Operations Research, Vol. 38, No. 1, PP. 21-32.
7. Liu, S. S. and Wang, C. J. (2012). "Optimizing linear project scheduling with multi-skilled crews", Automation in Construction, Vol. 24, No. 1, PP. 16-23.
8. Quintanilla, S., Pérez, Á., Lino, P. and Valls, V. (2012). "Time and work generalised precedence relationships in project scheduling with pre-emption: An application to the management of Service Centres", European Journal of Operational Research, Vol. 219, No. 1, PP. 59-72.
9. Kyriakidis, T. S., Kopanos, G. M. and Georgiadis, M. C. (2012). "MILP formulations for single-and multi-mode resource-constrained project scheduling problems", Computers & Chemical Engineering, Vol. 36, No. 1, PP. 369-385.
10. Tavana, M., Abtahi, A. R.  and Khalili-damghani, K. (2014). "A new multi-objective multi-mode model for solving preemptive time–cost–quality trade-off project scheduling problems", Expert Systems with Applications, Vol. 41, No. 4, PP. 1830-1846.
11. Afshar Najafi, B., Karimi, H., Rahimi, A. and Khalili, S. (2015). "Project scheduling with limited resources using an efficient differential evolution algorithm", Journal of King Saud University-Engineering Sciences, Vol. 27, No. 2, PP. 176-184.
12. Tian, W. and Demeulemeester, E. (2014). "Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment", Annals of Operations Research, Vol. 213, No. 1, PP. 271-291.
13. Kim, J., Kang, C. and Hwang, I. (2012). "A practical approach to project scheduling: Considering the potential quality loss cost in the time–cost tradeoff problem", International Journal of Project Management, Vol. 32, No. 2, PP. 264-272.
14. Bianco, L. and Caramia, M. (2013). "A new formulation for the project scheduling problem under limited resources," Flexible Services and Manufacturing Journal, Vol. 25, No. 1-2, PP. 6-24.
15. Szmerekovsky, J. G. and Venkateshan, P. (2012). "An integer programming formulation for the project scheduling problem with irregular time–cost tradeoffs", Computers & Operations Research, Vol. 39, No. 7, PP. 1402-1410.
16. Shi, Q. and Blomquist, T. (2012). "A new approach for project scheduling using fuzzy dependency structure matrix", International Journal of Project Management, Vol. 30, No. 4, PP. 503-510.
17. Correia, I., Lourenço, L. L. and Saldanha-da-gama, F. (2012). "Project scheduling with flexible resources: Formulation and inequalities", OR Spectrum, Vol. 34, No. 3, PP. 635-663.
18. Koné, O., Artigues, C., Lopez, P. and Mongeau, M. (2013). "Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources", Flexible Services and Manufacturing Journal, Vol. 25, No. 1-2, PP. 25-47.
19. Rahimi, A., Karimi, H. and Afshar-nadjafi, B. (2013). "Using meta-heuristics for project scheduling under mode identity constraints", Applied Soft Computing, Vol. 13, No, 4. PP. 2124-2135.
20. Kopanos, G. M., Kyriakidis, T. S. and Georgiadis, M. C. (2014). "New continuous-time and discrete-time mathematical formulations for resource-constrained project scheduling problems", Computers & Chemical Engineering, Vol. 68, No. 1, PP. 96-106.
21. Yang, S. and Fu, L. (2014). "Critical chain and evidence reasoning applied to multi-project resource schedule in automobile R&D process", International Journal of Project Management, Vol. 32, No. 1, PP. 166-177.
22. Wang, W. X., Wang, X., Ge, X. L. and Deng, L. (2014). "Multi-objective optimization model for multi-project scheduling on critical chain", Advances in Engineering Software, Vol. 68, No. 1, PP. 33-39.
23. Singh, A. (2014). "Resource constrained multi-project scheduling with priority rules & analytic hierarchy process", Procedia Engineering, Vol. 69, No. 1, PP. 725-734.
24. Tang, Y., Liu, R. and Sun, Q. (2014). "Schedule control model for linear projects based on linear scheduling method and constraint programming", Automation in Construction, Vol. 37, No. 1, PP. 22-37.
25. Messelis, T. and De Causmaecker, P. (2014). "An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 233, No. 3, PP. 511-528.
26. Van Peteghem, 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, No. 1, PP. 62-72.
27. Luna, F., González-álvarez, D. L., Chicano, F. and Vega-rodríguez, M. A. (2014). "The software project scheduling problem: A scalability analysis of multi-objective metaheuristics", Applied Soft Computing, Vol. 15, No. 1, PP. 136-148.
28. Cheng, M. Y., Tran, D. H.  and WU, Y. W. (2014). "Using a fuzzy clustering chaotic-based differential evolution with serial method to solve resource-constrained project scheduling problems", Automation in Construction, Vol. 37, No. 1, PP. 88–97.
29. Ghasemi, B., Sadeghi, A., Roghani, M., Researchers, Y., Club, E. and Branch, S. T. (2015). "The solution of multi-objective multimode Resource-Constrained Project Scheduling Problem (RCPSP) with partial precedence relations by Multi-Objective Bees Algorithm", SILVAE GENETICA. Vol. 57, No. 1, PP.0037-5349.
30. Paraskevopoulos, D. C., Tarantilis, C. D. and Ioannou, G. (2016). "An adaptive memory programming framework for the resource-constrained project scheduling problem", International Journal of Production Research, Vol. 54, No. 16, PP. 4938-4956.
31. Geiger, M. J. (2017). "A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem", European Journal of Operational Research, Vol. 256, No. 3, PP. 729-741.
32. Leyman, P. and Vanhoucke, M. (2017). "Capital-and resource-constrained project scheduling with net present value optimization", European Journal of Operational Research, Vol. 256, No. 3, PP. 757-776.
33. Gholipour, Y. and Shahbazi, M. M. (2011). "Resource-constrained scheduling of construction projects using the harmony serach algorithm", Journal of Industrial Engineering, University of Tehran, Special Issue, Vol. 45, No. 5, PP. 51-60.
34. Rafiee Majd, Z., Julai, F. and Bagherinejad, G. (2012). "Solving the MRCPSP/Max with the objective of minimizing tardiness costs and maximizing earliness rewards of activities with a two-stage genetic algorithm", Journal of Industrial Engineering, University of Tehran, Vol. 47, No. 1, PP. 1-13.
35. Kastor, A. and Sirakoulis, K. (2009). "The effectiveness of resource levelling tools for resource constraint project scheduling problem", International Journal of Project Management, Vol. 27, No. 5, PP. 493-500.
36. Chen, W, Shi Y. J, Teng, H. F. Lan, X, P and Hu, L. C. (2010). "An efficient hybrid algorithm for resource-constrained project scheduling", Information Sciences, Vol. 180, No.6, PP. 1031-1039.
37. Fallah-mehdipour, E., Haddad, O. B., Tabari, M. M. R. and Mariño, M. A. (2012). "Extraction of decision alternatives in construction management projects: Application and adaptation of NSGA-II and MOPSO", Expert Systems with Applications, Vol. 39,No. 3 ,PP. 2803-2794.
38. Deb, K., Anand, A.  and Joshi, D. (2002). “A computationally efficient evolutionary algorithm for real-parameter optimization”, Evolutionary Computation, Vol. 10, No. 4, PP. 371-395.