A Survey on Approximation Algorithms for Scheduling with Machine Unavailability

DOI10.1007/978-3-642-02094-0_3zbMath1248.68112OpenAlexW2167828639MaRDI QIDQ3637311

Ulrich M. Schwarz, Florian Diedrich, Klaus Jansen, Denis Trystram

Publication date: 9 July 2009

Published in: Algorithmics of Large and Complex Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02094-0_3

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (4)

Dual Techniques for Scheduling on a Machine with Varying Speed ⋮ Total completion time minimization on multiple machines subject to machine availability and makespan constraints ⋮ Speed-robust scheduling: sand, bricks, and rocks ⋮ Speed-robust scheduling. Sand, bricks, and rocks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel machines scheduling with nonsimultaneous machine available time
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Online scheduling on semi-related machines
• Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times
• On the two-phase method for preemptive scheduling
• Single machine flow-time scheduling with a single breakdown
• Bin packing can be solved within 1+epsilon in linear time
• A new fully polynomial time approximation scheme for the Knapsack problem
• Nearly on line scheduling of preemptive independent tasks
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A 3/4-approximation algorithm for multiple subset sum
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• A PTAS for the multiple subset sum problem with different knapsack capacities
• The effect of machine availability on the worst-case performance of LPT
• Preemptive scheduling with variable profile, precedence constraints and due dates
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Makespan minimization for two parallel machines with an availability constraint
• Stochastic scheduling on a single machine subject to multiple breakdowns according to different probabilities
• A note on parallel machine scheduling with non-simultaneous machine available time
• Approximability of scheduling with fixed jobs
• Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times
• Parallel-machine scheduling under potential disruption
• Minimizing makespan on a single machine subject to random breakdowns
• The Multiple Subset Sum Problem
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Scheduling with Deadlines and Loss Functions
• Parameterized Approximation Scheme for the Multiple Knapsack Problem
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Preemptive scheduling with staircase and piecewise linear resource availability
• Fast Approximation Algorithms for Knapsack Problems
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• `` Strong NP-Completeness Results
• Fault-Tolerant Scheduling
• Approximation in Preemptive Stochastic Online Scheduling
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Scheduling with unexpected machine breakdowns
• Approximation algorithms for scheduling with reservations

This page was built for publication: A Survey on Approximation Algorithms for Scheduling with Machine Unavailability