Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

DOI10.1016/j.ejor.2008.11.003zbMath1176.90223MaRDI QIDQ1042105

Vitaly A. Strusevich, Hans Kellerer, Mikhail A. Kubzin

Publication date: 7 December 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.11.003

zbMATH Keywords

approximation algorithm; single machine scheduling; total weighted completion time; machine non-availability

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Parallel machines scheduling with machine maintenance for minsum criteria, Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates, Single machine scheduling with semi-resumable machine availability constraints, Differential approximation schemes for half-product related functions and their scheduling applications, The symmetric quadratic knapsack problem: approximation and scheduling applications, Scheduling jobs and maintenance activities on parallel machines, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications

Cites Work

• Unnamed Item
• Unnamed Item
• Single machine flow-time scheduling with scheduled maintenance
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Single machine flow-time scheduling with a single breakdown
• A new fully polynomial time approximation scheme for the Knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
• Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times
• Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
• Machine scheduling with an availability constraint