Approximation algorithms for minimizing the total weighted tardiness on a single machine

DOI10.1016/j.tcs.2005.11.039zbMath1088.68024MaRDI QIDQ2368997

Stavros G. Kolliopoulos, George Steiner

Publication date: 28 April 2006

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

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

zbMATH Keywords

Scheduling; Approximation algorithms; Weighted tardiness

Mathematics Subject Classification ID

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68W25: Approximation algorithms

Related Items

An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates, Optimal restricted due date assignment in scheduling, Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups, Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments, Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem, A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date, A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines, Non-approximability of just-in-time scheduling, Energy-efficient bi-objective single-machine scheduling with power-down mechanism, The symmetric quadratic knapsack problem: approximation and scheduling applications, 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, Approximation algorithms for scheduling problems with a modified total weighted tardiness objective, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single machine scheduling to minimize total weighted tardiness
• A fully polynomial approximation scheme for the total tardiness problem
• Scheduling with Deadlines and Loss Functions
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• Single Machine Scheduling to Minimize Total Late Work
• A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
• Single Machine Scheduling to Minimize Total Weighted Late Work
• STACS 2004
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems