Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
Summary: This paper addresses a new performance measure for scheduling problems, entitled ``biased tardiness penalty. We study the approximability of minimum biased tardiness on a single machine, provided that all the due dates are equal. Two heuristic algorithms are developed for this problem, and it is shown that one of them has a worst-case ratio bound of 2. Then, we propose a dynamic programming algorithm and use it to design an FPTAS. The FPTAS is generated by cleaning up some states in the dynamic programming algorithm, and it requires \(O(n^3 / \varepsilon)\) time.
- 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
- STACS 2004
- 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
- A faster fully polynomial approximation scheme for the single-machine total tardiness problem
- 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 Functional Equation and its Application to Resource Allocation and Sequencing Problems
- An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
- Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains
- Approximation algorithms for minimizing the total weighted tardiness on a single machine
- Approximation schemes for scheduling jobs with common due date on parallel machines to minimize Total tardiness
- Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
- scientific article; zbMATH DE number 167292 (Why is no real title available?)
- scientific article; zbMATH DE number 3550182 (Why is no real title available?)
- scientific article; zbMATH DE number 3550186 (Why is no real title available?)
- Improving the complexities of approximation algorithms for optimization problems
- Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- Minimizing Total Tardiness on One Machine is NP-Hard
- Single machine scheduling to minimize total weighted tardiness
This page was built for publication: Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2336632)
