Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

DOI10.4230/LIPICS.ISAAC.2020.18MaRDI QIDQ6065415zbMATH OpenOpenAlexFDO

Authors Martin Koutecký, Johannes Zink

Publication date 14 November 2023

Full work available at URL https://arxiv.org/abs/2009.11840

zbMATH Keywords

schedulinghardnessparameterized complexitycutting stock

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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 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|C_{max}$) 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|C_{max}$), we show that if either the largest job size $p_{max}$, or the number of jobs $n$ are polynomially bounded in the instance size $|I|$, there are algorithms with complexity $|I{|}^{extrmpoly(k)}$. Our main result is that this is unlikely to be improved, because $Q||C_{max}$ is W[1]-hard parameterized by $k$ already when $n$, $p_{max}$, and the numbers describing the speeds are polynomial in $|I|$; the same holds for $R|HM|C_{max}$ (without speeds) when the job sizes matrix has rank $2$. Our positive and negative results also extend to the objectives $el{l}_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.

Cites work

• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 7559087 (Why is no real title available?)
• A Linear Programming Approach to the Cutting-Stock Problem
• About the structure of the integer cone and its application to bin packing
• An application of simultaneous diophantine approximation in combinatorial optimization
• Bin packing with fixed number of bins revisited
• Integer Programming
• Minimum makespan scheduling with low rank processing times
• Near-linear time algorithm for \(n\)-fold ILPs via color coding
• New algorithmic results for bin packing and scheduling
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• On the optimality of exact and approximation algorithms for scheduling problems
• On the parameterized tractability of single machine scheduling with rejection
• Parameterized algorithms
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• Parameterized complexity of machine scheduling: 15 open problems
• Polynomiality for bin packing with a constant number of item types
• Scheduling and fixed-parameter tractability
• Scheduling meets \(n\)-fold integer programming

Cited in

(2)

• Block-structured integer programming: can we parameterize without the largest coefficient?
• Fair and efficient allocation with few agent types, few item types, or small value levels

This page was built for publication: Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065415)