On the complexity of scheduling tasks with discrete starting times

DOI10.1016/0167-6377(92)90087-JzbMath0759.90045OpenAlexW2080664213WikidataQ56004685 ScholiaQ56004685MaRDI QIDQ1195868

J. Mark Keil

Publication date: 4 January 1993

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

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90087-j

zbMATH Keywords

NP-completesingle processorpolynomially solvable casediscrete starting times

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items (10)

Algorithmic properties of ciliate sequence alignment ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Order allocation, rack allocation and rack sequencing for pickers in a mobile rack environment ⋮ Parts-to-picker based order processing in a rack-moving mobile robots environment ⋮ Runway sequencing with holding patterns ⋮ Balanced splitting on weighted intervals ⋮ On the approximability of an interval scheduling problem ⋮ Single machine scheduling with forbidden start times ⋮ Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity results for scheduling tasks with discrete starting times
• On the Complexity of Timetable and Multicommodity Flow Problems

This page was built for publication: On the complexity of scheduling tasks with discrete starting times