Algorithmic paradoxes of the single-machine total tardiness problem

DOI10.1002/jos.69zbMath0994.90076MaRDI QIDQ5937433

Wlodzimierz Szwarc, Andrea Grosso, Frederico Della Croce

Publication date: 12 July 2001

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

Full work available at URL: https://doi.org/10.1002/jos.69

zbMATH Keywords

decomposition; lower bound; tardiness; due dates; single machine scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

49M27: Decomposition methods

Related Items

On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation, A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem, A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem, Some remarks on the decomposition properties of the single machine total tardiness problem, A hybrid algorithm for the single-machine total tardiness problem, The single-machine total tardiness scheduling problem: review and extensions, On the single machine total tardiness problem, Scheduling a single machine to minimize a regular objective function under setup constraints, Finding the Pareto-optima for the total and maximum tardiness single machine problem, A special case of the single-machine total tardiness problem is NP-hard, One-Machine Sequencing to Minimize Total Tardiness: A Fourth Theorem for Emmons

Cites Work

• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• On decomposition of the total tardiness problem
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness