A multivariate complexity analysis of the material consumption scheduling problem. (English) Zbl 1520.90095
Summary: The NP-hard problem Material Consumption Scheduling and related problems have been thoroughly studied since the 1980’s. Roughly speaking, the problem deals with scheduling jobs that consume non-renewable resources – each job has individual resource demands. The goal is to minimize the makespan. We focus on the single-machine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary precondition for processing further jobs. We initiate a systematic exploration of the parameterized computational complexity landscape of Material Consumption Scheduling, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the problem’s computational complexity. This leads to a deepened understanding of this fundamental scheduling problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
non-renewable resources; makespan minimization; parameterized computational complexity; fine-grained complexity; exact algorithmsReferences:
| [1] | Belkaid, F., Maliki, F., Boudahri, F., & Sari, Z. (2012). A branch and bound algorithm to minimize makespan on identical parallel machines with consumable resources. In: Proceedings of the 3rd International Conference on Mechanical and Electronic Engineering, (pp. 217-221). Springer. |
| [2] | Bentert, M., Bredereck, R., Györgyi, P., Kaczmarczyk, A., & Niedermeier, R. (2021). A multivariate complexity analysis of the material consumption scheduling problem. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence, (pp. 11755-11763). AAAI Press. · Zbl 1520.90095 |
| [3] | Bentert, M.; van Bevern, R.; Niedermeier, R., Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: A review, Journal of Scheduling, 22, 1, 3-20 (2019) · Zbl 1425.90039 · doi:10.1007/s10951-018-0595-8 |
| [4] | Bérczi, K., Király, T., & Omlor, S. (2020). Scheduling with non-renewable resources: Minimizing the sum of completion times. In: Proceedings of the 6th International Symposium on Combinatorial Optimization, (pp. 167-178). Springer. · Zbl 1458.90256 |
| [5] | Bodlaender, HL; Fellows, MR, W[2]-hardness of precedence constrained \(k\)-processor scheduling, Operations Research Letters, 18, 2, 93-97 (1995) · Zbl 0857.90056 · doi:10.1016/0167-6377(95)00031-9 |
| [6] | Bodlaender, H.L., & van der Wegen, M. (2020). Parameterized complexity of scheduling chains of jobs with delays. In: Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC ’20), (pp. 4:1-4:15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik · Zbl 07764095 |
| [7] | Bredereck, R.; Faliszewski, P.; Niedermeier, R.; Skowron, P.; Talmon, N., Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting, Theoretical Computer Science, 814, 86-105 (2020) · Zbl 1435.90087 · doi:10.1016/j.tcs.2020.01.017 |
| [8] | Carlier, J. (1984). Problèmes d’ordonnancements à contraintes de ressources: Algorithmes et complexité. Thèse d’état. Université Paris 6 |
| [9] | Carrera, S., Ramdane-Cherif, W., & Portmann, M.C. (2010). Scheduling supply chain node with fixed component arrivals and two partially flexible deliveries. In: Proceedings of the 5th International Conference on Management and Control of Production and Logistics (MCPL ’10),( p. 6). IFAC Publisher. |
| [10] | Carlier, J.; Rinnooy Kan, AHG, Scheduling subject to nonrenewable resource constraints, Operations Research Letters, 1, 52-55 (1982) · Zbl 0494.90041 · doi:10.1016/0167-6377(82)90045-1 |
| [11] | Chrétienne, P., On single-machine scheduling without intermediate delays, Discrete Applied Mathematics, 156, 13, 2543-2550 (2008) · Zbl 1152.90436 · doi:10.1016/j.dam.2008.03.010 |
| [12] | Cygan, M.; Fomin, FV; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [13] | Davari, M.; Ranjbar, M.; De Causmaecker, P.; Leus, R., Minimizing makespan on a single machine with release dates and inventory constraints, European Journal of Operational Research, 286, 1, 115-128 (2020) · Zbl 1443.90177 · doi:10.1016/j.ejor.2020.03.029 |
| [14] | Downey, RG; Fellows, MR, Fundamentals of Parameterized Complexity (2013), Springer · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1 |
| [15] | Fellows, MR; McCartin, C., On the parametric complexity of schedules to minimize tardy tasks, Theoretical Computer Science, 298, 2, 317-324 (2003) · Zbl 1038.68049 · doi:10.1016/S0304-3975(02)00811-3 |
| [16] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer · Zbl 1143.68016 |
| [17] | Frank, A.; Tardos, É., An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, 7, 1, 49-65 (1987) · Zbl 0641.90067 · doi:10.1007/BF02579200 |
| [18] | Ganian, R., Hamm, T., & Mescoff, G. (2020). The complexity landscape of resource-constrained scheduling. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI ’20), (pp. 1741-1747). International Joint Conferences on Artificial Intelligence Organization |
| [19] | Graham, RL; Lawler, EL; Lenstra, JK; Kan, AR, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [20] | Grigoriev, A.; Holthuijsen, M.; van de Klundert, J., Basic scheduling problems with raw material constraints, Naval Research of Logistics, 52, 527-553 (2005) · Zbl 1122.90349 · doi:10.1002/nav.20095 |
| [21] | Guo, J., Hüffner, F., & Niedermeier, R. (2004). A structural view on parameterizing problems: Distance from triviality. In: Proceedings of the First International Workshop on Parameterized and Exact Computation, (pp. 162-173). Berlin Heidelberg:Springer. · Zbl 1104.68050 |
| [22] | Györgyi, P.; Kis, T., Approximation schemes for single machine scheduling with non-renewable resource constraints, Journal of Scheduling, 17, 135-144 (2014) · Zbl 1297.90045 · doi:10.1007/s10951-013-0346-9 |
| [23] | Györgyi, P.; Kis, T., Approximability of scheduling problems with resource consuming jobs, Annals of Operations Research, 235, 1, 319-336 (2015) · Zbl 1332.90111 · doi:10.1007/s10479-015-1993-3 |
| [24] | Györgyi, P.; Kis, T., Reductions between scheduling problems with non-renewable resources and knapsack problems, Theoretical Computer Science, 565, 63-76 (2015) · Zbl 1315.90015 · doi:10.1016/j.tcs.2014.11.007 |
| [25] | Györgyi, P.; Kis, T., Approximation schemes for parallel machine scheduling with non-renewable resources, European Journal of Operational Research, 258, 1, 113-123 (2017) · Zbl 1380.90116 · doi:10.1016/j.ejor.2016.09.007 |
| [26] | Györgyi, P.; Kis, T., Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints, Journal of Scheduling, 22, 6, 623-634 (2019) · Zbl 1432.90057 · doi:10.1007/s10951-019-00601-1 |
| [27] | Györgyi, P.; Kis, T., New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints, Discrete Applied Mathematics, 311, 97-109 (2022) · Zbl 1483.90056 · doi:10.1016/j.dam.2022.01.009 |
| [28] | Heeger, K., Hermelin, D., Mertzios, G.B., Molter, H., Niedermeier, R., & Shabtay, D. (2021). Equitable scheduling on a single machine. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI ’21), (pp. 11818-11825). AAAI Press. · Zbl 1517.90048 |
| [29] | Hermelin, D.; Kubitza, JM; Shabtay, D.; Talmon, N.; Woeginger, GJ, Scheduling two agents on a single machine: A parameterized analysis of NP-hard problems, Omega, 83, 275-286 (2019) · doi:10.1016/j.omega.2018.08.001 |
| [30] | Hermelin, D.; Manoussakis, G.; Pinedo, M.; Shabtay, D.; Yedidsion, L., Parameterized multi-scenario single-machine scheduling problems, Algorithmica, 82, 9, 2644-2667 (2020) · Zbl 1453.68095 · doi:10.1007/s00453-020-00702-w |
| [31] | Hermelin, D.; Pinedo, M.; Shabtay, D.; Talmon, N., On the parameterized tractability of single machine scheduling with rejection, European Journal of Operational Research, 273, 1, 67-73 (2019) · Zbl 1403.90332 · doi:10.1016/j.ejor.2018.07.038 |
| [32] | Hermelin, D.; Shabtay, D.; Talmon, N., On the parameterized tractability of the just-in-time flow-shop scheduling problem, Journal of Scheduling, 22, 6, 663-676 (2019) · Zbl 1432.90058 · doi:10.1007/s10951-019-00617-7 |
| [33] | Herr, O.; Goel, A., Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, European Journal of Operational Research, 248, 1, 123-135 (2016) · Zbl 1346.90351 · doi:10.1016/j.ejor.2015.07.001 |
| [34] | Jansen, K.; Kratsch, S.; Marx, D.; Schlotter, I., Bin packing with fixed number of bins revisited, Journal of Computer and System Sciences, 79, 1, 39-49 (2013) · Zbl 1261.68065 · doi:10.1016/j.jcss.2012.04.004 |
| [35] | Kannan, R., Minkowski’s convex body theorem and integer programming, Mathematics of Operations Research, 12, 3, 415-440 (1987) · Zbl 0639.90069 · doi:10.1287/moor.12.3.415 |
| [36] | Knop, D.; Koutecký, M., Scheduling meets \(n\)-fold integer programming, Journal of Scheduling, 21, 5, 493-503 (2018) · Zbl 1418.90113 · doi:10.1007/s10951-017-0550-0 |
| [37] | Knop, D.; Koutecký, M.; Mnich, M., Combinatorial \(n\)-fold integer programming and applications, Mathematical Programming, 184, 1, 1-34 (2020) · Zbl 1451.90100 · doi:10.1007/s10107-019-01402-2 |
| [38] | Lenstra, H. W., Jr. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research,8(4), 538-548. · Zbl 0524.90067 |
| [39] | Mnich, M.; van Bevern, R., Parameterized complexity of machine scheduling: 15 open problems, Computers & Operations Research, 100, 254-261 (2018) · Zbl 1458.90333 · doi:10.1016/j.cor.2018.07.020 |
| [40] | Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming,154(1-2), 533-562. · Zbl 1332.68089 |
| [41] | Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press. · Zbl 1095.68038 |
| [42] | Slowinski, R., Preemptive scheduling of independent jobs on parallel machines subject to financial constraints, European Journal of Operational Research, 15, 366-373 (1984) · Zbl 0535.90045 · doi:10.1016/0377-2217(84)90105-X |
| [43] | Toker, A.; Kondakci, S.; Erkip, N., Scheduling under a non-renewable resource constraint, Journal of the Operational Research Society, 42, 811-814 (1991) · Zbl 0737.90036 · doi:10.1057/jors.1991.152 |
| [44] | van Bevern, R.; Mnich, M.; Niedermeier, R.; Weller, M., Interval scheduling and colorful independent sets, Journal of Scheduling, 18, 5, 449-469 (2015) · Zbl 1328.90065 · doi:10.1007/s10951-014-0398-5 |
| [45] | van Bevern, R.; Niedermeier, R.; Suchý, O., A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: Few machines, small looseness, and small slack, Journal of Scheduling, 20, 3, 255-265 (2017) · Zbl 1376.90028 · doi:10.1007/s10951-016-0478-9 |
| [46] | Xie, J., Polynomial algorithms for single machine scheduling problems with financial constraints, Operations Research Letters, 21, 1, 39-42 (1997) · Zbl 0885.90063 · doi:10.1016/S0167-6377(97)00007-2 |
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.
