Abstract

This paper proposes a new mathematical model for the preemptive multi-objective multi-mode resource-constrained project scheduling problem (P-MOMRCPSP) that focuses on two objectives: minimizing the makespan and maximizing the net present value (NPV). The model allows multiple execution modes for each project activity and permits activities to be preempted at any appropriate time and resumed later. This problem is classified as NP-hard, necessitating the use of the Simulated Annealing (SA) algorithm to achieve either a global optimal solution or a satisfactory one. The SA algorithm offers significantly shorter computation times compared to exact methods, making it well-suited for solving large-scale problems. Finally, the model is validated through a numerical example.

References

• Aarts, E.H.L., & Korst, J.H.M. 1989. Simulated annealing and boltzmann machines: A stochastic approach to combinatorial optimization and neural computing, Wiley, Chichester.
• Abbasi, B., Shadrokh, S., & Arkat, J. 2006. Bi-objective resource constrained project scheduling with robustness and makespan criteria, Applied Mathematics and Computation. 180, 146–152.
• 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.
• Al-Fawzan, M., & Haouari, M. 2005. A bi-objective model for robust resource-constrained project scheduling. International Journal of Production Economics, 96(2), 175-187.
• Barrios, A., Ballestin, F., & Valls, V. 2011. A double genetic algorithm for the MRCPSP/max. Computers and Operations Research, 38(1), 33-43.
• Bianco, L., Caramia, M., & DellOlmo, P. 1999. Solving a preemptive project scheduling problem with coloring techniques. In Weglarz, 193, 135– 146.
• Boctor, F. 1996. An adaptation of the simulated annealing for solving resource-constrained project scheduling problems. International Journal of Production Research, 34, 2335–2351.
• 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.
• Bredael, d., & Vanhoucke, M. 2024. A genetic algorithm with resource buffers for the resource-constrained multi-project scheduling problem. European Journal of Operational Research, 315, 19–34.
• Brucker, P., & Knust, S. 2001. Resource-constrained project scheduling and timetabling. Lecture Notes in Computer Science, 2079, 277-293.
• Calhoun, K. M., Deckro, R. F., Moore, J. T., Chrissis, J. W., & Hove, J. C. V. 2002. Planning and replanning in project and production scheduling. Omega – The international Journal of Management Science, 30(3), 155-170.
• 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.
• Davis, K. R., Stam, A., & Grzybowski, R. A. 1992. Resource constrained project scheduling with multiple objectives: A decision support approach. Computers and Operations Research, 19(7), 657-669.
• Debels, D., & Vanhoucke, M. 2006. Pre-emptive resource constrained project scheduling with setup times. Faculteit Economie En Bedrijfskunde, 1-24.
• Demeulemeester, E. L., & Herroelen, W. S. 1996. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem. European Journal of Operational Research, 90(2), 334-348.
• Ding, H., Zhuang, C., & Liu, J. 2023. Extensions of the resource-constrained project scheduling problem. Automation in Construction, 153, Article 104958.
• Drexl, A., Nissen, R., Patterson, J. H., & Salewski, F. 2000. Progen/px - an instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions. European Journal of Operational Research. 125(1), 59-72.
• Elloumi, S., & Fortemps, P. 2010. A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 205(1), 31–41
• Elloumi, S., Fortemps, P., & Loukil, T. 2017. Multi-objective algorithms to multi-mode resource-constrained projects under mode change disruption. Computers and Industrial Engineering, 106, 161–173.
• Franck, B., Neumann, K., & Schwindt, C. 2001. Project scheduling with calendars. Or Spektrum, 23, 325- 334.
• Hartmann, S. 2001. Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, 102(1–4), 111–135.
• He, Z., Wang, N., Jia, T., & Xu, Y. 2009. Simulated annealing and tabu search for multimode project payment scheduling, European Journal of Operational Research, 198, 688–696.
• Heilmann, R. 2001. Resource-constrained project scheduling: a heuristic for the multi-mode case. Or Spektrum, 23(3), 335-357.
• Heilmann, R. 2003. A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 144(2), 348-365.
• 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.
• Jozefowska, J., Mika, M., Rozycki, R., Waligora, G., & Weglarz, J. 2001. Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102(1–4), 137–155.
• Kolisch, R., & Drexl, A. 1997. Local search for non-preemptive multi-mode resource constrained project scheduling. IIE Transactions, 25(5), 74–81.
• Lova, A., Tormos, P., & 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(30), 69–86.
• 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.
• Mika, M., Waligo´ra, G., & Weglarz, J. 2005. Simulated annealing and tabu search for multi-mode resource constrained project scheduling with positive discounted cash flows and different payment models. European Journal of Operational Research. 164, 639–668.
• 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.
• Muritiba, A. E. F., Rodrigues, C. D., & Costa, F. A. D. 2018. A path-relinking algorithm for the multi-mode resource-constrained project scheduling problem. Computers and Operations Research. 92, 145-154.
• Nonobe, K., & Ibaraki, T. 2002. Formulation and tabu search algorithm for the resource constrained project scheduling problem. In C. C. Ribeiro and P. Hansen, editors, Essays and Surveys in Metaheuristics, pages 557–588. Kluwer Academic Publishers.
• Nudtasomboon, N., & Randhawa, S. U. 1997. Resource constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs. Computers and Industrial Engineering, 32(1), 227-242.
• 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(1), 44-59.
• Pesch, E. 1999. Lower bounds in different problem classes of project schedules with resource constraints. In Weglarz , 53–76.
• 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.
• Peteghem, V. V., & Vanhoucke, M. 2011. Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem. Journal of Heuristics, 17(6), 705–728.
• Peteghem, V. 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.
• Rahimi, A., Karimi, H., & Afshar-Nadjafi, B. 2013. Using meta-heuristics for project scheduling under mode identity constraints, Applied Soft Computing. 13(4), 2124–2135.
• Reyck, B., & Herroelen, W. S. 1999. The multi-mode resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 119(2), 538-556.
• Sabzehparvar, M., & Seyed Hosseini, S. M. 2008. A mathematical model for the multi-mode resource constrained project scheduling problem with mode dependent time lags. Journal of Supercomputing, 44(3), 257-273.
• Salewski, F., Schirmer, A., & Drexl, A. 1997. Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application. European Journal of Operational Research, 102(1), 88-110.
• Schultmann, F., & Rentz, O. 2001. Environment-oriented project scheduling for the dismantling of buildings. Or Spectrum, 23(1), 51-78.
• Słowinski, R. 1981. Multi-objective network scheduling with efficient use of renewable and nonrenewable resources. European Journal of Operational Research. 7(3), 265–273.
• Słowinski, R., Soniewicki, B., & Weglarz, J. 1994. DSS for multi-objective project scheduling. European Journal of Operational Research, 79, 220–229.
• Tirkolaee, E.B., Goli, A., Hematian, M., Sangaiah, A.K., & Han, T. 2019. Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms, Computing, 101(6), 547–570.
• Varma, V. A., Uzsoy, R., Pekny, J., & Blau, G. 2007. Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry. Journal of Heuristics, 13(5), 403-433.
• Voß, S., & Witt, A. 2007. Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application. International Journal of Production Economics, Vol. 105(2), 445-458.
• Voskresenskii, A., Kovalchuk, M., Filatova, A., Nasonov, D., & Lutsenko, A. 2023. Hybrid Algorithm for Multi-Contractor, Multi-Resource Project Scheduling in the Industrial Field. Procedia Computer Science, 229, 28-38.
• Wang, L., & Fang, C. 2012. An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem. Information Sciences, 39(5), 890–901.
• Wang, L., & Zheng, X. 2018. A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm and Evolutionary Computation, 38, 54–63.
• Zare, Z., Naddaf, A., & Salehi, M.R., 2012. Proposing a Model on Preemptive Multi-Mode Resource-constrained Project Scheduling Problem. International Journal of Business and Social Science, 3(4), 126-130.
• Zare, Z., Naddaf, A., Ashrafzadeh, M., & Salehi, M.R. 2012. Preemption in multi-mode Resource-constrained project scheduling problem. Interdisciplinary Journal of Contemporary Research in Business, 3(9), 636-642.
• Zhang, H. 2012. Ant colony optimization for multimode resource-constrained project scheduling. Journal of Management in Engineering, 28(2), 150–159.
• Zhang, H., Tam, C. M., & Li, H. 2010. Multimode project scheduling based on particle swarm optimization. Computer-Aided Civil and Infrastructure Engineering, 21(2), 93–103.
• 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.
• Zoraghi, N., Shahsavar, A., Abbasi, B., & Peteghem, V. V. 2017. Multi-mode resource-constrained project scheduling problem with material ordering under bonus-penalty policies. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 25(1), 1–31.