Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval

DOI10.1007/S10878-015-9924-4zbMath1353.90063OpenAlexW2212575943MaRDI QIDQ326506

Imed Kacem, Maryam Seifaddini, Hans Kellerer

Publication date: 12 October 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9924-4

zbMATH Keywords

schedulingsingle machineapproximation schemesmaximum latenessfixed operator intervalmachine non-availability interval

Mathematics Subject Classification ID

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

Related Items (8)

Minimizing maximum delivery completion time for order scheduling with rejection ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown ⋮ Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions ⋮ Single-machine scheduling with operator non-availability to minimize total weighted completion time ⋮ Single machine scheduling with rejection and a non-availability interval to minimize the maximum delivery completion time plus the total rejection cost ⋮ Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints ⋮ Minimizing the maximum lateness for scheduling with release times and job rejection

Cites Work

• Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times
• Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Improved algorithms for two single machine scheduling problems
• A note on worst-case performance of heuristics for maintenance scheduling problems
• Operator non-availability periods
• Fast approximation algorithm for job sequencing with deadlines
• The one-machine sequencing problem
• Scheduling with limited machine availability
• Single machine scheduling with small operator-non-availability periods
• Machine scheduling with an availability constraint
• Scheduling the maintenance on a single machine
• Planning Machine Maintenance in Two-Machine Shop Scheduling
• SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

This page was built for publication: Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval