Exponential inapproximability and FPTAS for scheduling with availability constraints

DOI10.1016/J.TCS.2009.03.012zbMath1188.68083OpenAlexW2005313518MaRDI QIDQ1029337

Bin Fu, Hairong Zhao, Yumei Huo

Publication date: 10 July 2009

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

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

zbMATH Keywords

schedulinginapproximabilityFPTAStotal weighted completion timemachine availability

Mathematics Subject Classification ID

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

Related Items (6)

Minimizing total weighted completion time with an unexpected machine unavailable interval ⋮ Parallel machines scheduling with machine maintenance for minsum criteria ⋮ Approximation schemes for parallel machine scheduling with availability constraints ⋮ Single machine scheduling with semi-resumable machine availability constraints ⋮ Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem ⋮ Parallel machines scheduling with deteriorating jobs and availability constraints

Cites Work

• Unnamed Item
• Single machine flow-time scheduling with scheduled maintenance
• Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints
• Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints
• Approximation results for flow shop scheduling problems with machine availability constraints
• Single machine flow-time scheduling with a single breakdown
• Machine scheduling with availability constraints
• Current trends in deterministic scheduling
• Non-preemptive two-machine open shop scheduling with non-availability constraints
• Scheduling preemptable tasks on parallel processors with limited availability
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Scheduling with limited machine availability
• Parallel machine scheduling with machine availability and eligibility constraints
• Machine scheduling with an availability constraint
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling jobs and maintenance activities on parallel machines
• Two-machine flow shops with limited machine availability

This page was built for publication: Exponential inapproximability and FPTAS for scheduling with availability constraints