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

DOI10.1007/978-3-642-02882-3_24MaRDI QIDQ5323068zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
• STACS 2004
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

Cites work

• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• A fully polynomial approximation scheme for the total tardiness problem
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• scientific article; zbMATH DE number 167292 (Why is no real title available?)
• scientific article; zbMATH DE number 3471786 (Why is no real title available?)
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• Minimizing Total Tardiness on One Machine is NP-Hard
• Scheduling with deadlines and loss functions
• Single machine scheduling to minimize total weighted tardiness

Cited in

(10)

• Soft due window assignment and scheduling of unit-time jobs on parallel machines
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
• An FPTAS for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs
• An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
• Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
• STACS 2004
• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

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

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