×

A computational study of exact approaches for the adjustable robust resource-constrained project scheduling problem. (English) Zbl 1458.90262

Summary: We study the robust resource-constrained project scheduling problem under budgeted uncertainty polytope. The problem can be seen as a very challenging variant of the resource-constrained project scheduling problem, where the objective function minimises the worst-case makespan, assuming that activity durations are subject to interval uncertainty. The model allows to control the level of robustness by means of a protection factor related to the risk aversion of the decision maker. The paper introduces two exact decomposition approaches to tackle the solution of this difficult problem. An extensive computational experimentation, on standard benchmark instances from the literature, is carried out to assess and compare the performance of the proposed methods, also with respect to the state-of-the-art exact solution approach.

MSC:

90B35 Deterministic scheduling theory in operations research
90C31 Sensitivity, stability, parametric optimization

Software:

PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Artigues, C.; Leus, R.; Nobibon, F. T., Robust optimization for resource-constrained project scheduling with uncertain activity durations, Flex. Serv. Manuf. J., 25, 1-2, 175-205, (2013)
[2] Artigues, C.; Michelon, P.; Reusser, S., Insertion techniques for static and dynamic resource-constrained project scheduling, Eur. J. Oper. Res., 149, 2, 249-267, (2003) · Zbl 1040.90013
[3] Beck, A.; Ben-Tal, A., Duality in robust optimization: primal worst equals dual best, Oper. Res. Lett., 37, 1, 1-6, (2009) · Zbl 1154.90614
[4] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust optimization, Princeton Series in Applied Mathematics, (2009), Princeton University Press · Zbl 1221.90001
[5] Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Math. Program., 99, 2, 351-376, (2004) · Zbl 1089.90037
[6] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238-252, (1962) · Zbl 0109.38302
[7] Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 464-501, (2011) · Zbl 1233.90259
[8] Bertsimas, D.; Sim, M., The price of robustness, Oper. Res., 52, 1, 35-53, (2004) · Zbl 1165.90565
[9] Bertsimas, D.; Tsitsiklis, J. N., Introduction to linear optimization, (1997), Athena Scientific
[10] Birge, J. R.; Louveaux, F., Introduction to stochastic programming, Springer Series in Operations Research and Financial Engineering, (2011), Springer · Zbl 1223.90001
[11] Bruni, M. E.; Beraldi, P.; Guerriero, F., The stochastic resource-constrained project scheduling problem, Handbook on Project Management and Scheduling Vol. 2, 811-835, (2015)
[12] Bruni, M. E.; Beraldi, P.; Guerriero, F.; Pinto, E., A heuristic approach for resource constrained project scheduling with uncertain activity durations, Comput. Oper. Res., 38, 1305-1318, (2011) · Zbl 1208.90055
[13] Bruni, M. E.; Beraldi, P.; Guerriero, F.; Pinto, E., A scheduling methodology for dealing with uncertainty in construction projects, Eng. Comput., 28, 8, 1064-1078, (2011)
[14] 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, (2017)
[15] Bruni, M. E.; Di Puglia Pugliese, L.; Beraldi, P.; Guerriero, F., A two-stage stochastic programming model for the resource constrained project scheduling problem under uncertainty, Proceedings of the 7th International Conference on Operations Research and Enterprise Systems - Vol. 1 ICORES, 194-200, (2018)
[16] Chen, X.; Zhang, Y., Uncertain linear programs: extended affinely adjustable robust counterparts, Oper. Res., 57, 6, 1469-1482, (2009) · Zbl 1226.90053
[17] Gabrel, V.; Lacroix, M.; Murat, C.; Remli, N., Robust location transportation problems under uncertain demands, Discrete Appl. Math., 164, 1, 100-111, (2014) · Zbl 1331.90096
[18] Gourgand, M.; Kellert, P., Conception d′un environnement de modélisation de syst\(\overset{`}{e}\)mes de production, 3\(\overset{`}{e}\)me congr\(\overset{`}{e}\)s international de Genie industriel, Tours, France, (1991)
[19] Herroelen, W.; Leus, R., Robust and reactive project scheduling: a review and classification of procedures, Int. J. Prod. Res., 42, 8, 1599-1620, (2004)
[20] Herroelen, W.; Leus, R., Project scheduling under uncertainty survey and research potentials, Eur. J. Oper. Res., 165, 2, 289-306, (2005) · Zbl 1066.90050
[21] Hooker, J. N., A hybrid method for planning and scheduling, Principles and Practice of Constraint Programming-Lecture Notes in Computer Science, 3258, 305-316, (2004) · Zbl 1152.90445
[22] Horst, R.; Tuy, H., Global optimization: deterministic approaches, Ch. Special Problems of Concave Minimization, (1996), Springer-Verlag Berlin, Heidelberg, New York · Zbl 0867.90105
[23] Kall, P.; Wallace, S. W., Stochastic programming, (1994), Wiley · Zbl 0812.90122
[24] Kolisch, R.; Sprecher, A., PSPLIB - a project scheduling problem library, Eur. J. Oper. Res., 96, 1, 205-216, (1997) · Zbl 0947.90587
[25] Koné, O.; Artigues, C.; Lopez, P.; Mongeau, M., Event-based MILP models for resource-constrained project scheduling problems, Comput. Oper. Res.Arch., 38, 1, 3-13, (2011) · Zbl 1231.90202
[26] 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, Flex. Serv. Manuf. J., 25, 1, 25-47, (2013)
[27] Pritsker, A.; Watters, L.; Wolfe, P., Multi-project scheduling with limited resources: a zero-one programming approach, Manag. Sci., 16, 93-108, (1969)
[28] Schwindt, C.; Trautmann, N., Scheduling the production of rolling ingots: industrial context, model, and solution method, Int. Trans. Oper. Res., 10, 547-563, (2003) · Zbl 1108.90315
[29] Thiele, A.; Terry, T.; Epelman, M., Robust linear optimization with recourse, Technical Report tr09-01, (2009), Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI
[30] Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., 41, 5, 457-461, (2013) · Zbl 1286.90143
[31] Zhu, G.; Bard, J. F.; Yu, G., A two-stage stochastic programming approach for project planning with uncertain activity durations, J. Schedul., 10, 3, 167-180, (2007) · Zbl 1168.90570
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.