Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

DOI10.1023/B:JOSH.0000013056.09936.FDzbMath1306.90048OpenAlexW2086104103MaRDI QIDQ5892099

Vangelis Th. Paschos, Andrea Grosso, Frederico Della Croce

Publication date: 22 January 2015

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

Full work available at URL: https://doi.org/10.1023/b:josh.0000013056.09936.fd

zbMATH Keywords

schedulingapproximationtotal tardiness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date ⋮ New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives ⋮ Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness ⋮ A special case of the single-machine total tardiness problem is NP-hard ⋮ A hybrid algorithm for the single-machine total tardiness problem ⋮ A faster fully polynomial approximation scheme for the single-machine total tardiness problem ⋮ The single-machine total tardiness scheduling problem: review and extensions

This page was built for publication: Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem