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

DOI10.1016/J.TCS.2006.08.030zbMATH Open1140.90026OpenAlexW2093570686MaRDI QIDQ861263FDOQ861263

Authors: V. 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

Recommendations

• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• STACS 2004
• An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
• An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates

zbMATH Keywords

dynamic programmingFPTASsingle machine schedulingweighted total tardiness

Mathematics Subject Classification ID

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

Cites Work

• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Minimizing Total Tardiness on One Machine is NP-Hard
• Title not available (Why is that?)
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• Title not available (Why is that?)
• Single machine scheduling to minimize total weighted tardiness
• 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
• Title not available (Why is that?)
• A fully polynomial approximation scheme for the total tardiness problem
• Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

Cited In (30)

• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Scheduling with time-dependent discrepancy times
• Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
• Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
• Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
• Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem
• STACS 2004
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• An FPTAS of minimizing total weighted completion time on single machine with position constraint
• On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
• Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
• A faster fully polynomial approximation scheme for the single-machine total tardiness problem
• Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups
• A note on ``Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines
• Minsum scheduling with acceptable lead-times and optional job rejection
• Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments
• New results for scheduling to minimize tardiness on one machine with rejection and related problems
• Minimizing the maximum lateness for scheduling with release times and job rejection
• A fully polynomial time approximation scheme for weighted job-dependent earliness-tardiness problem with agreeable ratios
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Single machine scheduling to minimize total weighted tardiness
• Soft due window assignment and scheduling of unit-time jobs on parallel machines
• An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• An FPTAS for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs

This page was built for publication: A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

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