Approximation schemes for parallel machine scheduling with availability constraints

DOI10.1016/j.dam.2011.06.007zbMath1231.90190MaRDI QIDQ642981

Hairong Zhao, Yumei Huo, Bin Fu

Publication date: 27 October 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.06.007

zbMATH Keywords

parallel machine; inapproximability; PTAS; total weighted completion time

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

Related Items

The parallel AGV scheduling problem with battery constraints: a new formulation and a matheuristic approach, A binary multiple knapsack model for single machine scheduling with machine unavailability, Minimizing total weighted completion time with an unexpected machine unavailable interval, Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem, Simultaneous scheduling of production and preventive maintenance on a single machine

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single machine flow-time scheduling with scheduled maintenance
• Approximability of single machine scheduling with fixed jobs to minimize total completion time
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Exponential inapproximability and FPTAS for scheduling with availability constraints
• Single machine flow-time scheduling with a single breakdown
• Non-preemptive two-machine open shop scheduling with non-availability constraints
• Scheduling preemptable tasks on parallel processors with limited availability
• Approximability of scheduling with fixed jobs
• Scheduling with limited machine availability
• Parallel machine scheduling with machine availability and eligibility constraints
• Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
• Machine scheduling with an availability constraint
• MAKESPAN MINIMIZATION WITH MACHINE AVAILABILITY CONSTRAINTS