Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time

DOI10.1016/j.ins.2013.07.003zbMath1321.90053OpenAlexW1977470429MaRDI QIDQ497629

Zhiyi Tan, An Zhang, Yong Chen

Publication date: 24 September 2015

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2013.07.003

zbMATH Keywords

schedulingapproximation algorithmmachine maintenanceworst-case analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (8)

Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval ⋮ High-multiplicity scheduling on one machine with forbidden start and completion times ⋮ A binary multiple knapsack model for single machine scheduling with machine unavailability ⋮ A lower bound for minimizing the total completion time of a three-agent scheduling problem ⋮ Two-machine flow shop scheduling with an operator non-availability period to minimize makespan ⋮ Single-machine scheduling with operator non-availability to minimize total weighted completion time ⋮ Robust single machine scheduling with a flexible maintenance activity ⋮ Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval

Cites Work

• Unnamed Item
• Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• The single processor total weighted completion time scheduling problem with the sum-of-processing-time based learning model
• Single machine flow-time scheduling with scheduled maintenance
• Improved algorithms for two single machine scheduling problems
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Operator non-availability periods
• Single machine flow-time scheduling with a single breakdown
• Non-preemptive two-machine open shop scheduling with non-availability constraints
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint
• Single machine scheduling with small operator-non-availability periods
• Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties

This page was built for publication: Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time