Exponential inapproximability and FPTAS for scheduling with availability constraints

DOI10.1016/J.TCS.2009.03.012MaRDI QIDQ1029337zbMATH OpenOpenAlexFDO

Authors Bin Fu, Yumei Huo, Hairong Zhao

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

FPTASschedulinginapproximabilitytotal weighted completion timemachine availability

Mathematics Subject Classification ID

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

Recommendations

• Approximation schemes for scheduling with availability constraints
• Approximation schemes for parallel machine scheduling with availability constraints
• Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
• Makespan Minimization with Machine Availability Constraints
• A fully polynomial time approximation scheme for makespan minimization problems on two machines with a fixed non-availability interval

Cites work

• scientific article; zbMATH DE number 5345853 (Why is no real title available?)
• Approximation results for flow shop scheduling problems with machine availability constraints
• Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints
• Current trends in deterministic scheduling
• Machine scheduling with an availability constraint
• Machine scheduling with availability constraints
• Non-preemptive two-machine open shop scheduling with non-availability constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parallel machine scheduling with machine availability and eligibility constraints
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Scheduling jobs and maintenance activities on parallel machines
• Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints
• Scheduling preemptable tasks on parallel processors with limited availability
• Scheduling with limited machine availability
• Single machine flow-time scheduling with a single breakdown
• Single machine flow-time scheduling with scheduled maintenance
• Two-machine flow shops with limited machine availability

Cited in

(8)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029337)