Complexity of scheduling few types of jobs on related and unrelated machines
Open Access
- 30 January 2025
- journal article
- research article
- Published by Springer Nature in Journal of Scheduling
- Vol. 28 (1) , 139-156
Abstract
The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general -hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines ( $$Q|HM|C_{\max }$$ ) is -hard already with 6 job types, and that the related Cutting Stock problem is -hard already with 8 item types. For the more general unrelated machines model ( $$R|HM|C_{\max }$$ ), we show that if the largest job size $$p_{\max }$$ or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity $$|I|^{{{\,\mathrm{\textrm{poly}}\,}}(k)}$$ . Our main result is that this is unlikely to be improved because $$Q||C_{\max }$$ is $$\mathsf {W[1]}$$ -hard parameterized by k already when n, $$p_{\max }$$ , and the numbers describing the machine speeds are polynomial in |I|; the same holds for $$R||C_{\max }$$ (without machine speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives $$\ell _2$$ -norm minimization of the load vector and, partially, sum of weighted completion times $$\sum w_j C_j$$ . Along the way, we answer affirmatively the question whether makespan minimization on identical machines ( $$P||C_{\max }$$ ) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for $$Q||C_{\max }$$ , this implies that the complexity of $$P|HM|C_{\max }$$ is the only remaining open case.
Keywords
All Related Versions
Funding Information
- Univerzita Karlova v Praze (UNCE 24/SCI/008)
- Deutsche Forschungsgemeinschaft (Wo758/11-1)
- Grantová Agentura České Republiky (22-22997 S)
This publication has 26 references indexed in Scilit:
- High-multiplicity N-fold IP via configuration LPMathematical Programming, 2022
- Approximation Schemes for the Generalized Extensible Bin Packing ProblemAlgorithmica, 2021
- Empowering the configuration-IP: new PTAS results for scheduling with setup timesMathematical Programming, 2021
- New algorithms for minimizing the weighted number of tardy jobs on a single machineAnnals of Operations Research, 2018
- New Algorithmic Results for Bin Packing and Scheduling2017
- Parameterized Algorithms2015
- Scheduling and fixed-parameter tractabilityMathematical Programming, 2014
- Integer Programming2014
- An application of simultaneous diophantine approximation in combinatorial optimizationCombinatorica, 1987
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956