Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

DOI10.1016/j.dam.2010.01.013zbMath1197.90209MaRDI QIDQ708332

Imed Kacem

Publication date: 11 October 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.01.013

zbMATH Keywords

scheduling; approximation; common due date; tardiness; FPTAS

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, Scheduling with time-dependent discrepancy times, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, 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, A note on ``Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications

Cites Work

• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Fast approximation algorithm for job sequencing with deadlines
• Approximation algorithms for scheduling a single machine to minimize total late work
• Approximation schemes for a class of subset selection problems
• A comment on scheduling two parallel machines with capacity constraints
• Minimization of Half-Products
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Combinatorial Problems: Reductibility and Approximation
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem