A historical note on the complexity of scheduling problems

DOI10.1016/j.orl.2022.11.006zbMath1525.90208MaRDI QIDQ6161270

Milan Vlach, Vitaly A. Strusevich, Jan Karel Lenstra

Publication date: 27 June 2023

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

partitioncomputational complexityschedulingNP-hardness

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A brief history of NP-completeness, 1954--2012
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Sequencing n Jobs on Two Machines with Arbitrary Time Lags
• Minimizing maximum lateness on one machine: computational experience and some applications
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling independent tasks to reduce mean finishing time
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Reducibility among Combinatorial Problems
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems

This page was built for publication: A historical note on the complexity of scheduling problems