On the complexity of scheduling problems with a fixed number of parallel identical machines

DOI10.1007/978-3-031-23101-8_13MaRDI QIDQ6169524zbMATH OpenOpenAlexFDO

Authors Klaus Jansen, Kai Kahler

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

fine-grained complexitypseudo-polynomial algorithmsschedulingSETHsubset sum

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Abstract: In parallel machine scheduling, we are given a set of jobs, together with a number of machines and our goal is to decide for each job, when and on which machine(s) it should be scheduled in order to minimize some objective function. Different machine models, job characteristics and objective functions result in a multitude of scheduling problems and many of them are NP-hard, even for a fixed number of identical machines. In this work, we give conditional running time lower bounds for a large number of scheduling problems, indicating the optimality of some classical algorithms. Most notably, we show that the algorithm by Lawler and Moore for $1||sum{w}_j{U}_j$ and $Pm||C_{max}$, as well as the algorithm by Lee and Uzsoy for $P2||sum{w}_j{C}_j$ are probably optimal. There is still small room for improvement for the $1|RejleqQ|sum{w}_j{U}_j$ algorithm by Zhang et al., the algorithm for $1||sum{T}_j$ by Lawler and the FPTAS for $1||sum{w}_j{U}_j$ by Gens and Levner. We also give a lower bound for $P2|any|C_{max}$ and improve the dynamic program by Du and Leung from $mathcalO(n{P}^2)$ to $mathcalO(nP)$, matching this new lower bound. Here, $P$ is the sum of all processing times. The same idea also improves the algorithm for $P3|any|C_{max}$ by Du and Leung from $mathcalO(n{P}^5)$ to $mathcalO(n{P}^2)$. While our results suggest the optimality of some classical algorithms, they also motivate future research in cases where the best known algorithms do not quite match the lower bounds.

Recommendations

• On the optimality of approximation schemes for the classical scheduling problem
• On the optimality of exact and approximation algorithms for scheduling problems
• Approximation algorithms for scheduling unrelated parallel machines
• Scheduling problem with multi-purpose parallel machines
• Lower bounds for scheduling on identical parallel machines with heads and tails

Cites work

• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A new dynamic programming algorithm for the parallel machines total weighted completion time problem
• A subquadratic approximation scheme for partition
• Bounding the running time of algorithms for scheduling and packing problems
• Complexity of Scheduling Parallel Task Systems
• Fast approximation algorithm for job sequencing with deadlines
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• On problems equivalent to \((\min,+)\)-convolution
• On the complexity of k-SAT
• On the optimality of approximation schemes for the classical scheduling problem
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parameterized complexity of machine scheduling: 15 open problems
• Reducibility among combinatorial problems
• Scheduling and fixed-parameter tractability
• Scheduling for parallel processing
• Scheduling independent tasks to reduce mean finishing time
• Scheduling lower bounds via AND subset sum
• Scheduling meets n-fold integer programming
• SETH-based lower bounds for subset sum and bicriteria path
• Single-machine scheduling under the job rejection constraint

Cited in

(9)

• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• A note on the maximum number of on-time jobs on parallel identical machines.
• Heuristic and exact algorithms for the identical parallel machine scheduling problem
• scientific article; zbMATH DE number 6007890 (Why is no real title available?)
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
• Uniform parallel machine scheduling problems with fixed machine cost
• Fifty years of research in scheduling -- theory and applications
• An approximation algorithm for identical parallel machine scheduling with resource dependent processing times

This page was built for publication: On the complexity of scheduling problems with a fixed number of parallel identical machines

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