2020/09/24 by Martin Koutecký, Koutecký, Martin, Johannes Zink +1
Computer Science · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · doi:10.48550/arxiv.2009.11840
openalex publication_date 2020/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 NP-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|Cmax) is NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-hard already with 8 item types. For the more general unrelated machines model (R|HM|Cmax), we show that if either the largest job size pmax, or the number of jobs n are polynomially bounded in the instance size |I|, there are algorithms with complexity |I|^\textrmpoly(k). Our main result is that this is unlikely to be improved, because Q||Cmax is W[1]-hard parameterized by k already when n, pmax, and the numbers describing the speeds are polynomial in |I|; the same holds for R|HM|Cmax (without speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives ℓ2-norm minimization of the load vector and, partially, sum of weighted completion times ∑ wj Cj. Along the way, we answer affirmatively the question whether makespan minimization on identical machines (P||Cmax) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for Q||Cmax this implies that the complexity of P|HM|Cmax is the only remaining open case.