Approximation schemes for parallel machine scheduling with availability constraints

DOI10.1016/j.dam.2011.06.007zbMath1231.90190OpenAlexW2030975628MaRDI 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 machineinapproximabilityPTAStotal weighted completion time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (6)

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

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

This page was built for publication: Approximation schemes for parallel machine scheduling with availability constraints