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.90223OpenAlexW2102397127MaRDI QIDQ1042105

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

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 algorithmsingle machine schedulingtotal weighted completion timemachine non-availability

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (7)

Scheduling jobs and maintenance activities on parallel machines ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ 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

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

This page was built for publication: Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval