Skip to main content
Springer Nature Link
Log in

An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem

  • Original Research
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Liess, O., & Michelon, P. (2008). A constraint programming approach for the resource-constrained project scheduling problem. Annals of Operations Research, 157(1), 25–36.

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Pritsker, A., Waiters, L. J., & Wolfe, P. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16, 93–108.

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Sprecher, A., Hartmann, S., & Drexl, A. (1997). An exact algorithm for project scheduling with multiple modes. Operations-Research-Spektrum, 19, 195–203.

    Article  Google Scholar 

  • Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210.

    Article  Google Scholar 

  • Tormos, P., & Lova, A. (2001). A competitive heuristic solution technique for resource-constrained project scheduling. Annals of Operations Research, 102(1), 65–81.

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Zamani, R. (2019). An effective mirror-based genetic algorithm for scheduling multi-mode resource constrained projects. Computers & Industrial Engineering, 127, 914–924.

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

Download references

Acknowledgements

Alireza Etminaniesfahani is the recipient of the UTS International Research Scholarship (IRS) and UTS President’s Scholarship (UTSP).

Author information

Authors and Affiliations

  1. School of Mathematical and Physical Sciences, University of Technology Sydney, Broadway, Sydney, NSW, 2007, Australia

    Alireza Etminaniesfahani & Hanyu Gu

  2. School of the Built Environment, University of Technology Sydney, Broadway, Sydney, NSW, 2007, Australia

    Leila Moslemi Naeni

  3. The University of Sydney Business School, Darlington, NSW, 2006, Australia

    Amir Salehipour

Authors
  1. Alireza Etminaniesfahani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hanyu Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Leila Moslemi Naeni
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Amir Salehipour
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alireza Etminaniesfahani.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-023-05775-8

Keywords

Search

Navigation