An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates

DOI10.1007/978-3-642-02882-3_24zbMath1248.90050OpenAlexW1579494035MaRDI QIDQ5323068

George Karakostas, Stavros G. Kolliopoulos, Jing Wang

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.553.6015

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (4)

Soft due window assignment and scheduling of unit-time jobs on parallel machines ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem ⋮ Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty

Cites Work

• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• Single machine scheduling to minimize total weighted tardiness
• A fully polynomial approximation scheme for the total tardiness problem
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• Scheduling with Deadlines and Loss Functions
• Minimizing Total Tardiness on One Machine is NP-Hard
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates