Parallel machines scheduling with machine maintenance for minsum criteria

DOI10.1016/j.ejor.2011.02.006zbMath1237.90099MaRDI QIDQ421521

An Zhang, Zhiyi Tan, Yong Chen

Publication date: 14 May 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2011.02.006

zbMATH Keywords

scheduling; approximation algorithm; machine maintenance; worst-case analysis

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

90B25: Reliability, availability, maintenance, inspection in operations research

Related Items

Absolute bounds of list algorithms for parallel machines scheduling with unavailability periods, Production-driven opportunistic maintenance for batch production based on MAM-APB scheduling, Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem, Dynamic maintenance decision-making for series-parallel manufacturing system based on MAM-MTW methodology

Cites Work

• Single machine flow-time scheduling with scheduled maintenance
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Minimizing the sum of job completion times on capacitated two-parallel machines
• Exponential inapproximability and FPTAS for scheduling with availability constraints
• Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times
• Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
• Single machine flow-time scheduling with a single breakdown
• Capacitated two-parallel machines scheduling to minimize sum of job completion times
• Applying extra-resource analysis to load balancing.
• The effect of machine availability on the worst-case performance of LPT
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Scheduling with limited machine availability
• Machine scheduling with an availability constraint
• Scheduling a maintenance activity on parallel identical machines
• `` Strong NP-Completeness Results
• Bounds for Certain Multiprocessing Anomalies
• Approximation algorithms for scheduling with reservations