Approximation algorithms for single machine scheduling with one unavailability period

DOI10.1007/s10288-008-0076-6zbMath1162.90458OpenAlexW1999566861MaRDI QIDQ1022445

Mohamed Haouari, Imed Kacem

Publication date: 22 June 2009

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-008-0076-6

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Scheduling jobs and maintenance activities on parallel machines ⋮ A branch-and-bound method for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization ⋮ Online and semi-online scheduling to minimize makespan on single machine with an availability constraint ⋮ Semi-online scheduling on a single machine with unexpected breakdown ⋮ Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines ⋮ An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown ⋮ Online scheduling with deterioration and unexpected processor breakdown ⋮ Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates ⋮ Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem ⋮ Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints

Cites Work

• Unnamed Item
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• New single machine and job-shop scheduling problems with availability constraints
• Fast approximation algorithm for job sequencing with deadlines
• Scheduling with limited machine availability
• Machine scheduling with an availability constraint
• A comment on scheduling two parallel machines with capacity constraints
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem