Exact and heuristic methods for Anchor-Robust and Adjustable-Robust RCPSP. (English) Zbl 07889404
Summary: The concept of anchored solutions is proposed as a new robust optimization approach to the Resource-Constrained Project Scheduling Problem (RCPSP) under processing times uncertainty. The Anchor-Robust RCPSP is defined, to compute a baseline schedule with bounded makespan, sequencing decisions, and a max-size subset of jobs with guaranteed starting times, called anchored set. It is shown that the Adjustable-Robust RCPSP from the literature fits within the framework of anchored solutions. The Anchor-Robust RCPSP and the Adjustable-Robust RCPSP can benefit from each other to find both a worst-case makespan, and a baseline schedule with an anchored set. A dedicated graph model for anchored solutions is reviewed for budgeted uncertainty. Compact MIP reformulations are derived for both the Adjustable-Robust RCPSP and the Anchor-Robust RCPSP. Dedicated heuristics are designed based on the graph model. For both problems, the efficiency of the proposed MIP reformulations and heuristic approaches is assessed through numerical experiments on benchmark instances.
MSC:
| 90Cxx | Mathematical programming |
| 90Bxx | Operations research and management science |
| 91Bxx | Mathematical economics |
Keywords:
project scheduling; RCPSP; robust 2-stage optimization; anchored solutions; MIP reformulations; heuristicsReferences:
| [1] | Artigues, C., Demassey, S., Neron, E., Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. ISTE/Wiley, London (2008). https://hal.archives-ouvertes.fr/hal-00482946 |
| [2] | Artigues, C.; Leus, R.; Nobibon, FT, Robust optimization for resource-constrained project scheduling with uncertain activity durations, Flexible Services and Manufacturing Journal, 25, 175-205, 2013 · doi:10.1007/s10696-012-9147-2 |
| [3] | Artigues, C.; Michelon, P.; Reusser, S., Insertion techniques for static and dynamic resource-constrained project scheduling, European Journal of Operational Research, 149, 2, 249-267, 2003 · Zbl 1040.90013 · doi:10.1016/S0377-2217(02)00758-0 |
| [4] | Bendotti, P., Chrétienne, P., Fouilhoux, P., Pass-Lanneau, A., Anchored rescheduling problems under generalized precedence constraints. In Baïou, M., Gendron, B., Günlük, O., Mahjoub, A.R. (eds.) Combinatorial Optimization. ISCO 2020. Lecture Notes in Computer Science, vol. 12176 (2020). doi:10.1007/978-3-030-53262-8_13 · Zbl 1458.90255 |
| [5] | Bendotti, P.; Chrétienne, P.; Fouilhoux, P.; Pass-Lanneau, A., The Anchor-Robust Project Scheduling Problem, Operations Research in Print, 2022 · Zbl 1534.90048 · doi:10.1287/opre.2022.2315 |
| [6] | Bendotti, P.; Chrétienne, P.; Fouilhoux, P.; Quilliot, A., Anchored reactive and proactive solutions to the CPM-scheduling problem, European Journal of Operational Research, 261, 1, 67-74, 2017 · Zbl 1403.90303 · doi:10.1016/j.ejor.2017.02.007 |
| [7] | Ben-Tal, A.; Goryashko, AP; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Mathematical Programming, 99, 2, 351-376, 2004 · Zbl 1089.90037 · doi:10.1007/s10107-003-0454-y |
| [8] | Bertsimas, D.; Sim, M., The price of robustness, Operations Research, 52, 35-53, 2004 · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [9] | Bold, M.; Goerigk, M., A compact reformulation of the two-stage robust Resource-Constrained project scheduling problem, Computers & Operations Research, 130, 105232, 2021 · Zbl 1510.90099 · doi:10.1016/j.cor.2021.105232 |
| [10] | Bruni, M.E., Di Puglia Pugliese, L., Beraldi, P., Guerriero, F. (2018). A two-stage stochastic programming model for the resource constrained project scheduling problem under uncertainty. In International Conference on Operations Research and Enterprise Systems (ICORES), pp. 194-200. · Zbl 1458.90262 |
| [11] | Bruni, ME; 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 · doi:10.1016/j.omega.2016.09.009 |
| [12] | Bruni, ME; Di Puglia Pugliese, L.; Beraldi, P.; Guerriero, F., A computational study of exact approaches for the adjustable robust resource-constrained project scheduling problem, Computers and Operations Research, 99, 178-190, 2018 · Zbl 1458.90262 · doi:10.1016/j.cor.2018.06.016 |
| [13] | Hazir, Ö.; Ulusoy, G., A classification and review of approaches and methods for modeling uncertainty in projects, International Journal of Production Economics, 223, 107522, 2020 · doi:10.1016/j.ijpe.2019.107522 |
| [14] | Herroelen, W.; Leus, R., Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 165, 289-306, 2002 · Zbl 1066.90050 · doi:10.1016/j.ejor.2004.04.002 |
| [15] | Herroelen, W.; Leus, R., The construction of stable project baseline schedules, European Journal of Operational Research, 156, 3, 550-565, 2004 · Zbl 1056.90066 · doi:10.1016/S0377-2217(03)00130-9 |
| [16] | Kolisch, R., Hartmann, S.: In Weglarz, J. (ed.) Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis, pp. 147-178. Springer, Boston, MA (1999). doi:10.1007/978-1-4615-5533-9_7 |
| [17] | Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management Science, 41, 10, 1693-1703, 1995 · Zbl 0870.90070 · doi:10.1287/mnsc.41.10.1693 |
| [18] | Koné, O.; Artigues, C.; Lopez, P.; Mongeau, M., Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources, Flexible Services and Manufacturing Journal, 25, 1-2, 24-47, 2013 · doi:10.1007/s10696-012-9152-5 |
| [19] | Minoux, M., Models and algorithms for robust PERT scheduling with time-dependent task durations, Vietnam Journal of Mathematics, 35, 387-398, 2007 · Zbl 1142.90406 |
| [20] | Soyster, AL, Technical note - convex programming with set-inclusive constraints and applications to inexact linear programming, Operations Research, 21, 5, 1154-1157, 1973 · Zbl 0266.90046 · doi:10.1287/opre.21.5.1154 |
| [21] | Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Operations Research Letters, 41, 5, 457-461, 2013 · Zbl 1286.90143 · doi:10.1016/j.orl.2013.05.003 |
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.
