Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
From MaRDI portal
Publication:708332
DOI10.1016/j.dam.2010.01.013zbMath1197.90209OpenAlexW1963587549MaRDI QIDQ708332
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
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
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, 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, Scheduling with time-dependent discrepancy times, Scheduling jobs with a V-shaped time-dependent processing time, A note on ``Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, New results for scheduling to minimize tardiness on one machine with rejection and related problems, Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
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
