A fully polynomial approximation scheme for the total tardiness problem

DOI10.1016/0167-6377(82)90022-0MaRDI QIDQ1839195zbMATH OpenOpenAlexFDO

Authors Eugene L. Lawler

Publication date 1982

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

Full work available at URL https://doi.org/10.1016/0167-6377(82)90022-0

zbMATH Keywords

fully polynomial approximation schemejob sequencingminimization of total tardinesspseudopolynomial algorithmsingle machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cited in

(26)

• The single-machine total tardiness scheduling problem: review and extensions
• A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• Approximation algorithms for scheduling a single machine to minimize total late work
• Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem
• Parallel machine batching and scheduling with deadlines
• Finding the Pareto-optima for the total and maximum tardiness single machine problem
• Improving the complexities of approximation algorithms for optimization problems
• Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs
• Metric approach for finding approximate solutions of scheduling problems
• A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
• The proportionate flow shop total tardiness problem
• Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
• A metric for total tardiness minimization
• Scheduling with monotonous earliness and tardiness penalties
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
• Minimizing total tardiness in a scheduling problem with a learning effect
• A theoretical development for the total tardiness problem and its application in branch and bound algorithms
• Supply chain scheduling to minimize holding costs with outsourcing
• Scheduling to approximate minimization objectives on identical machines
• An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
• A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem
• Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• A faster fully polynomial approximation scheme for the single-machine total tardiness problem

This page was built for publication: A fully polynomial approximation scheme for the total tardiness problem

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