A historical note on the complexity of scheduling problems

DOI10.1016/J.ORL.2022.11.006MaRDI QIDQ6161270zbMATH OpenFDO

Authors Jan Karel Lenstra, V. A. Strusevich, Milan Vlach

Publication date 27 June 2023

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/J.ORL.2022.11.006

zbMATH Keywords

computational complexityNP-hardnesspartitionscheduling

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3891075
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• scientific article; zbMATH DE number 1820024
• scientific article; zbMATH DE number 4031379
• scientific article; zbMATH DE number 3882159

Cites work

• A brief history of NP-completeness, 1954--2012
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• 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 724323 (Why is no real title available?)
• scientific article; zbMATH DE number 782644 (Why is no real title available?)
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Minimizing maximum lateness on one machine: computational experience and some applications
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Reducibility among combinatorial problems
• Scheduling independent tasks to reduce mean finishing time
• Sequencing \(n\) jobs on two machines with arbitrary time lags

Cited in

(2)

• A brief history of NP-completeness, 1954--2012
• Theory and methodology of time-dependent scheduling: past, present and future

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

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