Minimizing total tardiness on parallel machines with preemptions

DOI10.1007/s10951-010-0198-5zbMath1280.90059WikidataQ57633844 ScholiaQ57633844MaRDI QIDQ2434279

Svetlana A. Kravchenko, Frank Werner

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-010-0198-5

zbMATH Keywords

linear programming; parallel machines; polynomial algorithm; NP-hardness; total tardiness; preemptive problems

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

A note on the paper ``Minimizing total tardiness on parallel machines with preemptions, Erratum to: ``Minimizing total tardiness on parallel machines with preemptions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
• The complexity of mean flow time scheduling problems with release times
• On a parallel machine scheduling problem with equal processing times
• Minimizing Total Tardiness on One Machine is NP-Hard