A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

DOI10.1016/j.tcs.2006.08.030zbMath1140.90026OpenAlexW2093570686MaRDI QIDQ861263

Vitaly A. Strusevich, Hans Kellerer

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.08.030

zbMATH Keywords

dynamic programmingsingle machine schedulingFPTASweighted total tardiness

Mathematics Subject Classification ID

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

Related Items

Minsum scheduling with acceptable lead-times and optional job rejection, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates, Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, Soft due window assignment and scheduling of unit-time jobs on parallel machines, The symmetric quadratic knapsack problem: approximation and scheduling applications, Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups, Scheduling with time-dependent discrepancy times, Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals, MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK, Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date, Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem, New results for scheduling to minimize tardiness on one machine with rejection and related problems, A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines, Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval, Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem