Abstract
The multi-mode resource constrained project scheduling problem (MRCPSP) is an NP-hard optimisation problem involving scheduling tasks under resource and precedence constraints, while there are several modes for executing each task. In this paper, we propose a novel matheuristic based on relax-and-solve (R &S) algorithm to solve MRCPSP. In addition, a mathematical programming model, which is the generalisation of the multi-dimensional knapsack problem is developed. That model conducts the mode selection process for the purpose of generating an initial feasible solution. We evaluate the performance of the proposed algorithm by solving benchmark instances that are widely used in the literature. The results demonstrate that the proposed R &S algorithm outperforms the state-of-the-art methods for solving the MRCPSP.
Similar content being viewed by others
References
Absi, N., & van den Heuvel, W. (2019). Worst case analysis of relax and fix heuristics for lot-sizing problems. European Journal of Operational Research, 279(2), 449–458. https://doi.org/10.1016/j.ejor.2019.06.010
Afshar, M. R., Shahhosseini, V., & Sebt, M. H. (2022). A genetic algorithm with a new local search method for solving the multimode resource-constrained project scheduling problem. International Journal of Construction Management, 22(3), 357–365. https://doi.org/10.1080/15623599.2019.1623992
Ahmadian, M. M., & Salehipour, A. (2022). Heuristics for flights arrival scheduling at airports. International Transactions in Operational Research, 29(4), 2316–2345. https://doi.org/10.1111/itor.12901
Ahmadian, M. M., Salehipour, A., & Cheng, T. C. E. (2021). A meta-heuristic to solve the just-in-time job-shop scheduling problem. European Journal of Operational Research, 288(1), 14–29.
Alcaraz, J., Maroto, C., & Ruiz, R. (2003). Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of the Operational Research Society, 54(6), 614–626. https://doi.org/10.1057/palgrave.jors.2601563
Ahmadian, M. M., Salehipour, A., & Kovalyov, M. (2020). An efficient relax-and-solve heuristic for open-shop scheduling problem to minimize total weighted earliness-tardiness.
Asta, S., 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, 373, 476–498. https://doi.org/10.1016/j.ins.2016.09.010
Ayodele, M., McCall, J., & Regnier-Coudert, O. (2016). BPGA-EDA for the multi-mode resource constrained project scheduling problem. In 2016 IEEE congress on evolutionary computation (CEC) (pp. 3417–3424). https://doi.org/10.1109/CEC.2016.7744222
Blazewicz, J., Lenstra, J. K., & Kan, A. H. G. R. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1), 11–24. https://doi.org/10.1016/0166-218X(83)90012-4
Boctor, F. F. (1993). Heuristics for scheduling projects with resource restrictions and several resource-duration modes. International Journal of Production Research, 31(11), 2547–2558. https://doi.org/10.1080/00207549308956882
Boctor, F. F. (1996a). A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes. European Journal of Operational Research, 90(2), 349–361. https://doi.org/10.1016/0377-2217(95)00359-2
Boctor, F. F. (1996b). Resource-constrained project scheduling by simulated annealing. International Journal of Production Research, 34(8), 2335–2351. https://doi.org/10.1080/00207549608905028
Bouleimen, K., & Lecocq, H. (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149(2), 268–281. https://doi.org/10.1016/S0377-2217(02)00761-0
Chakrabortty, R. K., Abbasi, A., & Ryan, M. J. (2020). Multi-mode resource-constrained project scheduling using modified variable neighborhood search heuristic. International Transactions in Operational Research, 27(1), 138–167. https://doi.org/10.1111/itor.12644
Cheng, J., Fowler, J., Kempf, K., & Mason, S. (2015). Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting. Computers & Operations Research, 53, 275–287. https://doi.org/10.1016/j.cor.2014.04.018
Coelho, J., & Vanhoucke, M. (2011). Multi-mode resource-constrained project scheduling using RCPSP and sat solvers. European Journal of Operational Research, 213(1), 73–82. https://doi.org/10.1016/j.ejor.2011.03.019
CPLEX, I.I. (2017). version 12.8.0. IBM Corp.
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2), 243–278. https://doi.org/10.1016/j.tcs.2005.05.020
Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In MHS’95. Proceedings of the sixth international symposium on micro machine and human science (pp. 39–43).
Escudero, L. F., & Romero, C. P. (2017). On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 25(3), 601–622. https://doi.org/10.1007/s11750-017-0461-4
Etminaniesfahani, A., Gu, H., & Salehipour, A. (2022a). An efficient relax-and-solve algorithm for the resource-constrained project scheduling problem, 271–277. https://doi.org/10.5220/0010772400003117
Etminaniesfahani, A., Gu, H., Naeni, L., & Salehipour, A. (2022b). A forward–backward relax-and-solve algorithm for the resource-constrained project scheduling problem. SN Computer Science, 4, 104–114. https://doi.org/10.1007/s42979-022-01487-1
Fernandes, G. A., & de Souza, S. R. (2021). A matheuristic approach to the multi-mode resource constrained project scheduling problem. Computers & Industrial Engineering, 162, 107592. https://doi.org/10.1016/j.cie.2021.107592
Fleszar, K., & Hindi, K. S. (2004). Solving the resource-constrained project scheduling problem by a variable neighbourhood search. European Journal of Operational Research, 155(2), 402–413. https://doi.org/10.1016/S0377-2217(02)00884-6
Fréville, A. (2004). The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research, 155(1), 1–21. https://doi.org/10.1016/S0377-2217(03)00274-1
Hartmann, S. (2001). Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, 102(1), 111–135. https://doi.org/10.1023/A:1010902015091
Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207, 1–14. https://doi.org/10.1016/j.ejor.2009.11.005
Hartmann, S., & Briskorn, D. (2022). An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 297(1), 1–14.
Helber, S., & Sahling, F. (2010). A fix-and-optimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123(2), 247–256.
Herroelen, W., Demeulemeester, E., & Reyck, B. (1997). A classification scheme for project scheduling problems. Katholieke Universiteit Leuven, Open Access publications from Katholieke Universiteit Leuven (pp. 1–26).
Holland, J. H. (1992). Genetic algorithms. Scientific American
Jarboui, B., Damak, N., Siarry, P., & Rebai, A. (2008). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, 195(1), 299–308. https://doi.org/10.1016/j.amc.2007.04.096
Jozefowska, J., Mika, M., Rozycki, R., Waligora, G., & Weglarz, J. (2001). Simulated annealing for multimode resource-constrained project scheduling. Annals of Operations Research - Annals OR, 102, 137–155. https://doi.org/10.1023/A:1010954031930
Kelareva, E., Brand, S., Kilby, P., Thiebaux, S., & Wallace, M. (2012). CP and MIP methods for ship scheduling with time-varying draft. In ICAPS 2012—Proceedings of the 22nd international conference on automated planning and scheduling.
Kheiri, A., Özcan, E., & Parkes, A. J. (2012). HYSST: Hyper-heuristic search strategies and timetabling
Kolisch, R., & Drexl, A. (1997). Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Transactions, 29(11), 987–999. https://doi.org/10.1080/07408179708966417
Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1), 23–37. https://doi.org/10.1016/j.ejor.2005.01.065
Kolisch, R., & Sprecher, A. (1997). Psplib-a project scheduling problem library: Or software-orsep operations research software exchange program. European Journal of Operational Research, 96(1), 205–216. https://doi.org/10.1016/S0377-2217(96)00170-1
Kreter, S., Schutt, A., & Stuckey, P. (2017). Using constraint programming for solving RCPSP/max-cal. Constraints. https://doi.org/10.1007/s10601-016-9266-6
Larranaga, P., & Lozano, J. (2002). Estimation of distribution algorithms: A new tool for evolutionary computation. Springer. https://doi.org/10.1007/978-1-4615-1539-5
Li, Y., Li, H., & Yang, T. (2011). Solving MRCPSP by constraint programming. In 2011 International conference of information technology. Computer Engineering and Management Sciences (Vol. 1, pp. 312–315). https://doi.org/10.1109/ICM.2011.251
Li, H., & Zhang, H. (2013). Ant colony optimization-based multi-mode scheduling under renewable and nonrenewable resource constraints. Automation in Construction, 35, 431–438. https://doi.org/10.1016/j.autcon.2013.05.030
Liess, O., & Michelon, P. (2008). A constraint programming approach for the resource-constrained project scheduling problem. Annals of Operations Research, 157(1), 25–36.
Lova, A., Tormos, M., & Barber, F. (2006). Multi-mode resource constrained project scheduling: Scheduling schemes, priority rules and mode selection rules. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, 10, 69–86. https://doi.org/10.4114/ia.v10i30.947
Lova, A., Tormos, P., Cervantes, M., & Barber, F. (2009). An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics, 117(2), 302–316. https://doi.org/10.1016/j.ijpe.2008.11.002
Maleck, C., Nieke, G., Bock, K., Pabst, D., & Stehli, M. (2018). A comparison of an CP and MIP approach for scheduling jobs in production areas with time constraints and uncertainties. In 2018 Winter simulation conference (WSC) (pp. 3526–3537). https://doi.org/10.1109/WSC.2018.8632404
Mori, M., & Tseng, C. C. (1997). A genetic algorithm for multi-mode resource constrained project scheduling problem. European Journal of Operational Research, 100(1), 134–141. https://doi.org/10.1016/S0377-2217(96)00180-4
Muritiba, A. E. F., Rodrigues, C. D., & da Costa, F. A. (2018). A path-relinking algorithm for the multi-mode resource-constrained project scheduling problem. Computers & Operations Research, 92, 145–154. https://doi.org/10.1016/j.cor.2018.01.001
Nonobe, K., & Ibaraki, T. (2002). Formulation and Tabu search algorithm for the resource constrained project scheduling problem. In Essays and surveys in metaheuristics.
Ozcan, E., & Kheiri, A. (2012). A hyper-heuristic based on random gradient, greedy and dominance (pp. 557–563). https://doi.org/10.1007/978-1-4471-2155-8-71
Ozdamar, L. (1999). A genetic algorithm approach to a general category project scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 29, 44–59. https://doi.org/10.1109/5326.740669
Peteghem, V. V., & Vanhoucke, M. (2010). A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 201(2), 409–418. https://doi.org/10.1016/j.ejor.2009.03.034
Pritsker, A., Waiters, L. J., & Wolfe, P. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16, 93–108.
Ranjbar, M., De Reyck, B., & Kianfar, F. (2009). A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. European Journal of Operational Research, 193(1), 35–48. https://doi.org/10.1016/j.ejor.2007.10.042
Salehipour, A. (2017). A heuristic algorithm for the aircraft landing problem. In 22nd International congress on modelling and simulation. Modelling and simulation society of Australia and New Zealand Inc. (MSSANZ)
Salehipour, A., Ahmadian, M., & Oron, D. (2018). Efficient and simple heuristics for the aircraft landing problem. In Matheuristic 2018 international conference.
Schutt, A., Feydy, T., Stuckey, P.J., & Wallace, M.G. (2015). A satisfiability solving approach (pp. 135–160). Springer. https://doi.org/10.1007/978-3-319-05443-8_7
Schutt, A., Feydy, T., Stuckey, P., & Wallace, M. (2011). Explaining the cumulative propagator. Constraints, 16, 250–282. https://doi.org/10.1007/s10601-010-9103-2
Schnell, A., & Hartl, R. F. (2017). On the generalization of constraint programming and Boolean satisfiability solving techniques to schedule a resource-constrained project consisting of multi-mode jobs. Operations Research Perspectives, 4, 1–11. https://doi.org/10.1016/j.orp.2017.01.002
Slowinski, R. (1980). Two approaches to problems of resource allocation among project activities—A comparative study. Journal of the Operational Research Society, 31(8), 711–723. https://doi.org/10.1057/jors.1980.134
Slowinski, R., Soniewicki, B., & Weglarz, J. (1994). Dss for multiobjective project scheduling. European Journal of Operational Research, 79(2), 220–229. https://doi.org/10.1016/0377-2217(94)90353-0
Speranza, M. G., & Vercellis, C. (1993). Hierarchical models for multi-project planning and scheduling. European Journal of Operational Research, 64(2), 312–325. https://doi.org/10.1016/0377-2217(93)90185-P
Sprecher, A., & Drexl, A. (1998). Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. European Journal of Operational Research, 107(2), 431–450. https://doi.org/10.1016/S0377-2217(97)00348-2
Sprecher, A., Hartmann, S., & Drexl, A. (1997). An exact algorithm for project scheduling with multiple modes. Operations-Research-Spektrum, 19, 195–203.
Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210.
Tormos, P., & Lova, A. (2001). A competitive heuristic solution technique for resource-constrained project scheduling. Annals of Operations Research, 102(1), 65–81.
Van Peteghem, V., & 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, 235(1), 62–72. https://doi.org/10.1016/j.ejor.2013.10.012
Vanhoucke, M., & Coelho, J. (2018). A tool to test and validate algorithms for the resource-constrained project scheduling problem. Computers & Industrial Engineering, 118, 251–265. https://doi.org/10.1016/j.cie.2018.02.001
Zaman, F., Elsayed, S., Sarker, R., & Essam, D. (2020). Hybrid evolutionary algorithm for large-scale project scheduling problems. Computers & Industrial Engineering, 146, 106567. https://doi.org/10.1016/j.cie.2020.106567
Zamani, R. (2019). An effective mirror-based genetic algorithm for scheduling multi-mode resource constrained projects. Computers & Industrial Engineering, 127, 914–924.
Zhang, H., Tam, C., & Li, H. (2006). Multimode project scheduling based on particle swarm optimization. Computer-Aided Civil and Infrastructure Engineering, 21(2), 93–103. https://doi.org/10.1111/j.1467-8667.2005.00420.x
Zhang, L., Luo, Y., & Zhang, Y. (2015). Hybrid particle swarm and differential evolution algorithm for solving multimode resource-constrained project scheduling problem. Journal of Control Science and Engineering. https://doi.org/10.1155/2015/923791
Zhu, G., Bard, J. F., & Yu, G. (2006). A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS Journal on Computing, 18(3), 377–390. https://doi.org/10.1287/ijoc.1040.0121
Acknowledgements
Alireza Etminaniesfahani is the recipient of the UTS International Research Scholarship (IRS) and UTS President’s Scholarship (UTSP).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Etminaniesfahani, A., Gu, H., Naeni, L.M. et al. An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem. Ann Oper Res 338, 41–68 (2024). https://doi.org/10.1007/s10479-023-05775-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-023-05775-8