A project scheduling problem with periodically aggregated resource-constraints. (English) Zbl 1511.90197
Summary: We consider the so-called periodically aggregated resource-constrained project scheduling problem. This problem, introduced by Morin et al. (2017), is a variant of the well-known resource-constrained project scheduling problem that allows for a more flexible usage of the resource constraints. While the start and completion times of the activities can be arbitrary moments in time, the limitations on the resource usage are considered on average over aggregated periods of parameterized length. This paper presents new theoretical and experimental results for this problem. First, we settle the complexity status of the problem by proving NP-hardness of a number of special cases of the problem. Second, we propose a new mixed-integer programming formulation of the problem by disaggregating the precedence constraints over the periods. A theoretical comparison shows that the new formulation dominates the previously proposed one in terms of relaxation strength. Finally, we carry out computational experiments on instances from the literature to compare the merits of the different formulations.
Keywords:
project scheduling; periodic aggregation of resource-constraints; computational complexity; mixed-integer linear programmingSoftware:
PSPLIBReferences:
| [1] | Artigues, C., On the strength of time-indexed formulations for the resource-constrained project scheduling problem, Oper. Res. Lett., 45, 2, 154-159 (2017) · Zbl 1409.90085 |
| [2] | Artigues, C.; Gendreau, M.; Rousseau, L.-M.; Vergnaud, A., Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound, Comput. Oper. Res., 36, 8, 2330-2340 (2009) · Zbl 1179.90119 |
| [3] | Baptiste, P.; Demassey, S., Tight LP bounds for resource constrained project scheduling, OR Spectrum, 26, 2, 251-262 (2004) · Zbl 1072.90012 |
| [4] | Blazewicz, J.; Lenstra, J.; Rinnooy Kan, A., Scheduling subject to resource constraints: Classification and complexity, Discrete Appl. Math., 5, 1, 11-24 (1983) · Zbl 0516.68037 |
| [5] | Böttcher, J.; Drexl, A.; Kolisch, R.; Salewski, F., Project scheduling under partially renewable resource constraints, Manage. Sci., 45, 4, 543-559 (1999) · Zbl 1231.90178 |
| [6] | Brucker, P.; Knust, S., A linear programming and constraint propagation-based lower bound for the RCPSP, European J. Oper. Res., 127, 2, 355-362 (2000) · Zbl 0990.90055 |
| [7] | Carlier, J.; Néron, E., On linear lower bounds for the resource constrained project scheduling problem, European J. Oper. Res., 149, 2, 314-324 (2003) · Zbl 1040.90017 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide To the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039 |
| [9] | Haït, A.; Artigues, C., A hybrid CP/MILP method for scheduling with energy costs, Eur. J. Ind. Eng., 5, 4, 471-489 (2011) |
| [10] | Hans, E. W., Resource Loading by Branch-and-Price Techniques (2001), Twente Univ. Press, (Ph.D. thesis) |
| [11] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, At the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA. Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, At the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 1467.68065 |
| [12] | Kis, T., A branch-and-cut algorithm for scheduling of projects with variable-intensity activities, Math. Program., 103, 3, 515-539 (2005) · Zbl 1125.90019 |
| [13] | Kolisch, R.; Sprecher, A., PSPLIB - a project scheduling library, European J. Oper. Res., 96, 205-216 (1996) · Zbl 0947.90587 |
| [14] | Koné, O.; Artigues, C.; Lopez, P.; Mongeau, M., Event-based MILP models for resource-constrained project scheduling problems, Comput. Oper. Res., 38, 1, 3-13 (2011) · Zbl 1231.90202 |
| [15] | Mingozzi, A.; Maniezzo, V.; Ricciardelli, S.; Bianco, L., An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation, Manage. Sci., 44, 5, 714-729 (1998) · Zbl 1004.90036 |
| [16] | Morin, P.-A.; Artigues, C.; Haït, A., Periodically aggregated resource constrained project scheduling problem, Eur. J. Ind. Eng., 11, 6, 792-817 (2017) |
| [17] | Okubo, H.; Miyamoto, T.; Yoshida, S.; Mori, K.; Kitamura, S.; Izui, Y., Project scheduling under partially renewable resources and resource consumption during setup operations, Comput. Ind. Eng., 83, 91-99 (2015) |
| [18] | Paul, M.; Knust, S., A classification scheme for integrated staff rostering and scheduling problems, RAIRO-Oper. Res., 49, 2, 393-412 (2015) · Zbl 1310.90049 |
| [19] | Riedler, M.; Jatschka, T.; Maschler, J.; Raidl, G. R., An iterative time-bucket refinement algorithm for a high-resolution resource-constrained project scheduling problem, Int. Trans. Oper. Res., 27, 1, 573-613 (2020) · Zbl 07766437 |
| [20] | Schutt, A.; Feydy, T.; Stuckey, P. J., Explaining time-table-edge-finding propagation for the cumulative resource constraint, (International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (2013), Springer), 234-250 · Zbl 1382.68232 |
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.
