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

DOI10.4230/LIPICS.ISAAC.2020.18arXiv2009.11840OpenAlexW3115671652MaRDI QIDQ6065415FDOQ6065415

Martin Koutecký, Johannes Zink

Publication date: 14 November 2023

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.

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)

Cites Work

• A Linear Programming Approach to the Cutting-Stock Problem
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Parameterized Algorithms
• Title not available (Why is that?)
• An application of simultaneous diophantine approximation in combinatorial optimization
• On the optimality of exact and approximation algorithms for scheduling problems
• Bin packing with fixed number of bins revisited
• Scheduling meets \(n\)-fold integer programming
• Integer Programming
• Scheduling and fixed-parameter tractability
• Parameterized complexity of machine scheduling: 15 open problems
• Title not available (Why is that?)
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• Title not available (Why is that?)
• Minimum Makespan Scheduling with Low Rank Processing Times
• About the Structure of the Integer Cone and its Application to Bin Packing
• On the parameterized tractability of single machine scheduling with rejection
• New Algorithmic Results for Bin Packing and Scheduling

Cited In (2)

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

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)