A Twofold Constructive Genetic Algorithm for Resource-Constrained Multi-Project Scheduling Problem (RCMPSP)

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Yazd University, Yazd, Iran

2 Department of Industrial Engineering, Yazd University, Yazd, Iran.

10.22070/jqepo.2021.14832.1198

Abstract

Resource-constrained multi-project scheduling problem (RCMPSP) arises in many project-based organizations, including construction and civil engineering companies. Numerous heuristic and meta-heuristic approaches have been proposed for a project scheduling problem with limited resources. In this paper, a twofold constructive genetic algorithm is proposed for the resource-constraint multiple projects scheduling problem, which benefits from a number of priority and several auxiliary rules which are fed into a serial schedule generation scheme (SGS), where auxiliary rules are used to break the tie situations where several activities have equal priority values. Numerical standard problems in different sizes are retrieved from the multi-project scheduling problem LIBRARY (MPSPLIB) website, and the numerical results are analyzed in different scenarios. Then, the genetic algorithm is used to improve the results where its parameters are tuned via Taguchi design of experiments (DOE). The results of this study showed that the performance of the proposed approach has significantly improved the solution of several problem instances and registered in the MPSPLIB.

Keywords

References

Ahmeti, A., & Musliu, N. (2021). Hybridizing Constraint Programming and Meta-Heuristics for Multi-Mode Resource-Constrained Multiple Projects Scheduling Problem. Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling-PATAT, 188–206.
Alam, T., Qamar, S., Dixit, A., & Benaida, M. (2020). Genetic Algorithm: Reviews, Implementations, and Applications. International Journal of Engineering Pedagogy, 10(6), 57–77.
Berthaut, F., Pellerin, R., Hajji, A., & Perrier, N. (2018). A path relinking-based scatter search for the resource-constrained project scheduling problem. International Journal of Project Organisation and Management, 10(1), 1–36.
Blazewicz, J., Lenstra, J. K., & Kan, A. R. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete applied mathematics, 5(1), 11–24.
Browning, T. R., & Yassine, A. A. (2010). Resource-constrained multi-project scheduling: Priority rule performance revisited. International Journal of Production Economics, 126(2), 212–228.
Chen, H., Ding, G., Zhang, J., & Qin, S. (2019). Research on priority rules for the stochastic resource constrained multi-project scheduling problem with new project arrival. Computers & Industrial Engineering, 137, 106060.
Demeulemeester, E. L., & Herroelen, W. S. (2006). Project scheduling: a research handbook. Springer Science & Business Media.
ElFiky, H., Owida, A., & Galal, N. M. (2020). Resource Constrained Multi-Project Scheduling Using Priority Rules: Application in the Deep-Water Construction Industry. Proceedings of the International Conference on Industrial Engineering and Operations Management, 353–363.
Gholizadeh-Tayyar, S., Okongwu, U., & Lamothe, J. (2021). A Heuristic-Based Genetic Algorithm for Scheduling of Multiple Projects Subjected to Resource Constraints and Environmental Responsibility Commitments. Process Integration and Optimization for Sustainability, 1–22.
González, G., Calderón, C., González, D., & Trujillo, J. (2017). Priority Rules Performance Analysis as a GA Initial Population for RCMPSP. Proceedings of International Conference on Industrial Engineering and Operations Management, 1201–1211.
Hassanat, A., Almohammadi, K., Alkafaween, E., Abunawas, E., Hammouri, A., & Prasath, V. B. (2019). Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach. Information, 10(12), 390–425.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.
Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80, 8091–8126.
Khalilzadeh, M., Hosseini, S., & Ghaeli, R. (2020). A genetic algorithm-based method for solving multi-mode resource-constrained project scheduling problem in uncertain environment. Journal of Project Management, 5(2), 79–86.
Kim, J. L., & Ellis Jr, R. D. (2010). Comparing schedule generation schemes in resource-constrained project scheduling using elitist genetic algorithm. Journal of construction engineering and management, 136(2), 160–169.
Klein, R. (2000). Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects. European Journal of Operational Research, 127(3), 619–638.
Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. In Project scheduling (pp. 147–178). Springer, Boston, MA.
Linyi, D., & Yan, L. (2007). A particle swarm optimization for resource-constrained multi-project scheduling problem. Proceedings of International Conference on Computational Intelligence and Security (CIS 2007), 1010–1014.
Nabipoor Afruzi, E., & Aghaie, A. (2019). A Hybridized Metaheuristic Algorithm to Solve the Robust Resource Constrained Multi-Project Scheduling Problem. AUT Journal of Modeling and Simulation, 51(1), 15–32.
Pellerin, R., Perrier, N., & Berthaut, F. (2020). A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 280(2), 395–416.
Peng, W., Mu, J., Chen, L., & Lin, J. (2021a). A novel non-dominated sorting genetic algorithm for solving the triple objective project scheduling problem. Memetic Computing, 13(2), 271–284.
Peng, W., Zhang, J., & Chen, L. (2021b). A bi-objective hierarchical program scheduling problem and its solution based on NSGA-III. Annals of Operations Research, Article in press.
Rahman, H. F., Chakrabortty, R. K., & Ryan, M. J. (2020). Memetic algorithm for solving resource constrained project scheduling problems. Automation in Construction, 111, 103052.
Sánchez, M. G., Gil, A. F., & Castro, C. (2019). Integrating a SMT solver based local search in ant colony optimization for solving RCMPSP. Proceedings of IEEE Latin American Conference on Computational Intelligence (LA-CCI), 1–6.
Sonmez, R., & Uysal, F. (2015). Backward-forward hybrid genetic algorithm for resource-constrained multiproject scheduling problem. Journal of Computing in Civil Engineering, 29(5), 04014072-1–04014072-9.
Tian, J., Dong, X., & Han, S. (2018). Optimizing for a Resource-constrained Multi-project Scheduling Problem with Planned Resource Unavailability. Proceedings of  3rd International Conference on Modelling, Simulation and Applied Mathematics (MSAM 2018), 243–248.
Uysal, F., Sonmez, R., & Isleyen, S. K. (2021). A graphical processing unit‐based parallel hybrid genetic algorithm for resource‐constrained multi‐project scheduling problem. Concurrency and Computation: Practice and Experience, Article in press.
Van Eynde, R., & Vanhoucke, M. (2020). Resource-constrained multi-project scheduling: benchmark datasets and decoupled scheduling. Journal of Scheduling, 23(3), 301–325.
Vázquez, E. P., Calvo, M. P., & Ordóñez, P. M. (2015). Learning process on priority rules to solve the RCMPSP. Journal of Intelligent Manufacturing, 26(1), 123–138.
Villafáñez, F., Poza, D., López-Paredes, A., Pajares, J., & del Olmo, R. (2019). A generic heuristic for multi-project scheduling problems with global and local resource constraints (RCMPSP). Soft Computing, 23(10), 3465–3479.
Villafáñez, F., Poza, D., López-Paredes, A., Pajares, J., & Acebes, F. (2020). Portfolio scheduling: an integrative approach of limited resources and project prioritization. Journal of Project Management, 5(2), 103–116.
Zhang, Y., & Cui, N. (2021). Project scheduling and material ordering problem with storage space constraints. Automation in Construction, 129, 103796.
Journal of Quality Engineering and Production Optimization
Volume 6, Issue 1
May 2021
Pages 1-14

Files

Share

How to cite

Statistics