A branch-and-bound algorithm for the proactive resource-constrained project scheduling problem with a robustness maximization objective. (English) Zbl 07877708
Summary: This paper presents a branch-and-bound (B&B) algorithm for the proactive scheduling problem, which incorporates a degree of anticipated variability in practical projects. First, the resource-constrained proactive scheduling model is formulated. Second, solving the resource-unconstrained version of the problem with an adapted Fulkerson algorithm provides an upper bound solution. Then, the subproblems of the model are derived by introducing additional precedence relationships to resolve the resource conflict in the upper bound solution. Third, we solve the resource-constrained proactive scheduling problem with the proposed B&B algorithm. The resource conflicts found in the upper bound solution are resolved by adding additional precedence relationships. According to the problem analysis, two dominance rules are proposed for additional node fathoming with the aim of improving the algorithm. Fourth, a genetic algorithm is designed to provide an effective heuristic method for solving the research problem. Finally, we conduct an extensive computational experiment on \(6,000\) randomly generated instances. The obtained results show that the B&B algorithm has advantages over CPLEX and the genetic algorithm. In addition, the impacts of the dominance rules and the three key parameters on the computational time and project robustness are analysed.
MSC:
| 90Bxx | Operations research and management science |
Keywords:
project scheduling; optimization model; branch-and-bound algorithm; robustness; resource constraintReferences:
| [1] | Agarwal, A.; Colak, S.; Erenguc, S., A neurogenetic approach for the resource-constrained project scheduling problem, Comput. Oper. Res., 38, 44-50, 2011 · Zbl 1231.90170 |
| [2] | Al-Fawzan, M. A.; Haouari, M., A bi-objective model for robust resource-constrained project scheduling, Int. J. Prod. Econ., 96, 2, 175-187, 2005 |
| [3] | Artigues, C.; Michelon, P.; Reusser, S., Insertion techniques for static and dynamic resource-constrained project scheduling, Eur. J. Oper. Res., 149, 249-267, 2003 · Zbl 1040.90013 |
| [4] | Bianco, L.; Caramia, M., An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations, Eur. J. Oper. Res., 219, 73-85, 2012 · Zbl 1244.90088 |
| [5] | Bouleimen, K.; Lecocq, H., A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, Eur. J. Oper. Res., 149, 268-281, 2003 · Zbl 1040.90015 |
| [6] | Bruni, M. E.; Di Puglia Pugliese, L.; Beraldi, P.; Guerriero, F., An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations, Omega., 71, 66-84, 2016 |
| [7] | Chtourou, H.; Haouari, M., A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling, Comput. Ind. Eng., 55, 1, 183-194, 2008 |
| [8] | Chu, X. H.; Li, S. X.; Gao, F.; Cui, C.; Pferffer, F.; Cui, J. S., A data-driven meta-learning recommendation model for multi-mode resource-constrained project scheduling problem, Comput. Oper. Res., 157, Article 106290 pp., 2023 · Zbl 1542.90091 |
| [9] | Coelho, J., Vanhoucke, M., 2018. An exact composite lower bound strategy for the resource-constrained project scheduling problem. Comput. Oper. Res. 93, 135-150. https://doi.org/ 10.1016/j.cor.2018.01.017. · Zbl 1391.90250 |
| [10] | Dai, H.; Cheng, W.; Guo, P., An improved tabu search for multi-skill resource-constrained project scheduling problems under step-deterioration, Arab. J. Sci. Eng., 43, 3279-3290, 2018 |
| [11] | Debels, D.; De Reyck, B.; Leus, R.; Vanhoucke, M., A hybrid scatter search/electromagnetism meta-heuristic for project scheduling, Eur. J. Oper. Res., 169, 638-653, 2006 · Zbl 1079.90051 |
| [12] | Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Manage. Sci., 38, 12, 1803-1818, 1992 · Zbl 0761.90059 |
| [13] | Demeulemeester, E.; Herroelen, W., Robust project scheduling, Foundations and Trends in Technology, Information and Operations Management., 3, 3-4, 201-376, 2011 |
| [14] | Fang, C.; Wang, L., An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem, Comput. Oper. Res., 39, 890-901, 2012 · Zbl 1251.90140 |
| [15] | Fleszar, K.; Hindi, K. S., Solving the resource-constrained project scheduling problem by a variable neighbourhood search, Eur. J. Oper. Res., 155, 402-413, 2004 · Zbl 1045.90028 |
| [16] | Fulkerson, D. R., A network flow computation for project cost curve, Manage. Sci., 7, 2, 167-178, 1961 · Zbl 0995.90519 |
| [17] | Golab, A.; Gooya, E. S.; Al Falou, A.; Cabon, M., Review of conventional metaheuristic techniques for resource-constrained project scheduling problem, J. Proj. Manag., 7, 95-110, 2022 |
| [18] | Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Nav. Res. Logist., 45, 733-750, 1998 · Zbl 0936.90024 |
| [19] | Hartmann, S.; Briskorn, D., A survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res., 207, 1-14, 2010 · Zbl 1205.90123 |
| [20] | Hartmann, S.; Briskorn, D., An updated survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res., 297, 1, 1-14, 2022 · Zbl 1487.90294 |
| [21] | Hartmann, S.; Kolisch, R., Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem, Eur. J. Oper. Res., 127, 394-407, 2000 · Zbl 0985.90036 |
| [22] | Hazır, O.; Haouari, M.; Erel, E., Robust scheduling and robustness measures for the discrete time/cost trade-off problem, Eur. J. Oper. Res., 207, 2, 633-643, 2010 · Zbl 1205.90124 |
| [23] | Hazır, O.; Erel, E.; Günalay, Y., Robust optimization models for the discrete time/cost trade-off problem, Int. J. Prod. Econ., 130, 1, 87-95, 2011 |
| [24] | Hazır, O.; Ulusoy, G., A classification and review of approaches and methods for modeling uncertainty in projects, Int. J. Prod. Econ., 223, Article 107522 pp., 2020 |
| [25] | He, J. G.; Chen, X. D.; Chen, X., A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling, Comput. Oper. Res., 71, 71-81, 2016 · Zbl 1349.90353 |
| [26] | Heilmann, R., A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags, Eur. J. Oper. Res., 144, 348-365, 2003 · Zbl 1012.90513 |
| [27] | Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: a survey of recent developments, Comput. Oper. Res., 25, 279-302, 1998 · Zbl 1040.90525 |
| [28] | Herroelen, W.; Leus, R., The construction of stable project baseline schedules, Eur. J. Oper. Res., 156, 3, 550-565, 2004 · Zbl 1056.90066 |
| [29] | Herroelen, W.; Leus, R., Project scheduling under uncertainty: survey and research potentials, Eur. J. Oper. Res., 165, 2, 289-306, 2005 · Zbl 1066.90050 |
| [30] | Huang, R. P.; Qu, S. J.; Liu, Z. M., Two-stage distributionally robust optimization model for warehousing-transportation problem under uncertain environment, J. Ind. Manag. Optim., 19, 9, 6344-6363, 2023 · Zbl 1524.90051 |
| [31] | Icmeli, O.; Erenguc, SS., A branch and bound procedure for the resource constrained project scheduling problem with discounted cash flows, Manage. Sci., 42, 10, 1395-1408, 1996 · Zbl 0880.90074 |
| [32] | Ji, Y.; Li, H. H.; Zhang, H. J., Risk-averse two-stage stochastic minimum cost consensus models with asymmetric adjustment cost, Group Decis. Negot., 31, 261-291, 2022 |
| [33] | Kamburowski, J.; Michael, D. J.; Stallmann, M., Minimizing the complexity of an activity network, Networks, 36, 1, 47-52, 2000 · Zbl 0969.90017 |
| [34] | Khoshjahan, Y.; Najafi, A. A.; Afshar-Nadjafi, B., Resource constrained project scheduling problem with discounted earliness-tardiness penalties: mathematical modeling and solving procedure, Comput. Ind. Eng., 66, 2, 293-300, 2013 |
| [35] | Kolisch, R.; Sprecher, A., PSPLIB - a project scheduling problem library, Eur. J. Oper. Res., 96, 1, 205-216, 1997 · Zbl 0947.90587 |
| [36] | Lamas, P.; Demeulemeester, E., A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations, J. Sched., 19, 4, 409-428, 2016 · Zbl 1347.90045 |
| [37] | Lambrechts, O.; Demeulemeester, E.; Herroelen, W., Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities, J. Sched., 11, 121-136, 2008 · Zbl 1168.90453 |
| [38] | Lambrechts, O.; Demeulemeester, E.; Herroelen, W., A tabu search procedure for developing robust predictive project schedules, Int. J. Prod. Econ., 111, 493-508, 2008 |
| [39] | Lambrechts, O.; Demeulemeester, E.; Herroelen, W., Time slack-based techniques for robust project scheduling subject to resource uncertainty, Ann. Oper. Res., 186, 443-464, 2011 · Zbl 1225.90062 |
| [40] | Leus, R.; Herroelen, W., The complexity of generating robust resource-constrained baseline schedules, 2002, Katholieke Universiteit Leuven, Ph.D. Thesis |
| [41] | Leus, R.; Herroelen, W., Stability and resource allocation in project planning, IIE Trans., 36, 7, 667-682, 2004 |
| [42] | Leyman, P.; Vanhoucke, M., A new scheduling technique for the resource-constrained project scheduling problem with discounted cash flows, Int. J. Prod. Res., 53, 9, 2771-2786, 2015 |
| [43] | Liang, Y. Y.; Cui, N. F.; Hu, X. J.; Demeulemeester, E., The integration of resource allocation and time buffering for bi-objective robust project scheduling, Int. J. Prod. Res., 58, 13, 3839-3854, 2020 |
| [44] | Liu, Y.; Jin, S.; Zhou, J.; Hu, Q., A branch-and-bound algorithm for the unit-capacity resource constrained project scheduling problem with transfer times, Comput. Oper. Res., 151, Article 106097 pp., 2023 · Zbl 1542.90105 |
| [45] | Liu, H. R.; Qu, S. J.; Li, R. J.; Razaa, H., Bi-objective robust project scheduling with resource constraints and flexible activity execution lists, Comput. Ind. Eng., 156, Article 107288 pp., 2021 |
| [46] | Ma, Z. Q.; Demeulemeester, E.; He, Z. W.; Wang, N. M., A computational experiment to explore better robustness measures for project scheduling under two types of uncertain environments, Comput. Ind. Eng., 131, 382-390, 2019 |
| [47] | Ma, Y.; He, Z. W.; Wang, N. M.; Demeulemeester, E., Tabu search for proactive project scheduling problem with flexible resources, Comput. Oper. Res., 153, Article 106185 pp., 2023 · Zbl 1542.90106 |
| [48] | Megow, N.; Möhring, R. H.; Schulz, J., Decision support and optimization in shutdown and turnaround scheduling, INFORMS J. Comput., 23, 2, 189-204, 2011 · Zbl 1243.90110 |
| [49] | Mendes, J. J.M.; Gonçalves, J. F.; Resende, M. G.C., A random key based genetic algorithm for the resource constrained project scheduling problem, Comput. Oper. Res., 36, 92-109, 2009 · Zbl 1163.90500 |
| [50] | Mobini, M.; Mobini, Z.; Rabbani, M., An artificial immune algorithm for the project scheduling problem under resource constraints, Appl. Soft Comput., 11, 1975-1982, 2011 |
| [51] | Moradi, H.; Shadrokh, S., A robust scheduling for the multi-mode project scheduling problem with a given deadline under uncertainty of activity duration, Int. J. Prod. Res., 57, 10, 3138-3167, 2019 |
| [52] | Palpant, M.; Artigues, C.; Michelon, P., LSSPER: solving the resource-constrained project scheduling problem with large neighbourhood search, Ann. Oper. Res., 131, 237-257, 2004 · Zbl 1066.90037 |
| [53] | Pellerin, R.; Perrier, N.; Berthaut, F., A survey of hybrid metaheuristics for the resource-constrained project scheduling problem, Eur. J. Oper. Res., 206, 562-568, 2020 |
| [54] | Qu, S. J.; Shu, L. L.; Yao, J. Y., Optimal pricing and service level in supply chain considering misreport behavior and fairness concern, Comput. Ind. Eng., 174, Article 108759 pp., 2022 |
| [55] | Rahmani, N.; Zeighamib, V.; Akbaric, R., A study on the performance of differential search algorithm for single mode resource constrained project scheduling problem, Decis. Sci. Lett., 4, 537-550, 2015 |
| [56] | Rodrigues, S. B.; Yamashita, D. S., An exact algorithm for minimizing resource availability costs in project scheduling, Eur. J. Oper. Res., 206, 562-568, 2010 · Zbl 1188.90108 |
| [57] | Sayah, D., Continueous-time formulations for multi-mode project scheduling, Comput. Oper. Res., 152, Article 106147 pp., 2023 · Zbl 1542.90117 |
| [58] | Schnell, A.; Hartl, R. F., On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations, Or Spectrum., 38, 283-303, 2016 · Zbl 1339.90151 |
| [59] | Shi, Y. L.; Su, H. F.; Pang, N. S., Resource flow network generation algorithm in robust project scheduling, J. Oper. Res. Soc., 72, 6, 1294-1308, 2021 |
| [60] | Tian, W.; Zhao, Y.; Demeulemeester, E., Generating a robust baseline schedule for the robust discrete time/resource trade-off problem under work content uncertainty, Comput. Oper. Res., 143, Article 105795 pp., 2022 · Zbl 1511.90219 |
| [61] | Tseng, L. Y.; Chen, S. C., A hybrid metaheuristic for the resource-constrained project scheduling problem, Eur. J. Oper. Res., 175, 707-721, 2006 · Zbl 1142.90411 |
| [62] | Van de Vonder, S.; Demeulemeester, E.; Herroelen, W.; Leus, R., The use of buffers in project management: the trade-off between stability and makespan, Int. J. Prod. Econ., 97, 2, 227-240, 2005 |
| [63] | Van de Vonder, S.; Demeulemeester, E.; Herroelen, W.; Leus, R., The trade-off between stability and makespan in resource-constrained project scheduling, Int. J. Prod. Res., 44, 2, 215-236, 2006 |
| [64] | Van de Vonder, S.; Demeulemeester, E.; Herroelen, W., Proactive heuristic procedures for robust project scheduling: an experimental analysis, Eur. J. Oper. Res., 189, 3, 723-733, 2008 · Zbl 1146.90430 |
| [65] | Vanhoucke, M.; Demeulemeester, E.; Herroelen, W., On maximizing the net present value of a project under renewable resource constraints, Manage. Sci., 47, 8, 1113-1121, 2001 · Zbl 1232.90215 |
| [66] | Vanhoucke, M.; Demeulemeester, E.; Herroelen, W., An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem, Ann. Oper. Res., 102, 1, 179-196, 2001 · Zbl 0990.90512 |
| [67] | Watermeyer, K.; Zimmermann, J., A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints, Or Spectrum., 42, 427-460, 2020 · Zbl 1446.90087 |
| [68] | Wei, JP., Qu, SJ., Wang, QH., Luan, DQ., Zhao, XH., 2022. The novel data-driven robust maximum expert mixed integer consensus models under multirole’s opinions uncertainty by considering noncooperators. IEEE Trans. Comput. Soc. Syst. https://doi.org/10.1109/TCSS.2022.3192897. |
| [69] | Zamani, M. R., A high-performance exact method for the resource-constrained project scheduling problem, Comput. Oper. Res., 28, 1387-1401, 2001 · Zbl 0992.90032 |
| [70] | Zamani, R., A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem, Eur. J. Oper. Res., 229, 552-559, 2013 · Zbl 1317.90339 |
| [71] | Zheng, X. L.; Wang, L., A multi-agent optimization algorithm for resource constrained project scheduling problem, Expert Syst. Appl., 42, 6039-6049, 2015 |
| [72] | Zhu, G.; Bard, J. F.; Yu, G., A branch-and-cut procedure for the multi-mode resource-constrained project-scheduling problem, INFORMS J. Comput., 18, 3, 377-390, 2006 · Zbl 1241.90168 |
| [73] | Zhu, X.; Ruiz, R.; Li, S.; Li, X., An effective heuristic for project scheduling with resource availability cost, Eur. J. Oper. Res., 257, 3, 746-762, 2017 · Zbl 1394.90322 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
