Approximation algorithms for scheduling with reservations

DOI10.1007/s00453-008-9271-2zbMath1204.68273OpenAlexW1971872799MaRDI QIDQ5961975

Denis Trystram, Klaus Jansen, Florian Diedrich, Fanny Pascual

Publication date: 16 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9271-2

zbMATH Keywords

complexityschedulingapproximation algorithmsapproximation schemeinapproximabilityPTASreservations

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (3)

Absolute bounds of list algorithms for parallel machines scheduling with unavailability periods ⋮ Parallel machines scheduling with machine maintenance for minsum criteria ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel machines scheduling with nonsimultaneous machine available time
• A new fully polynomial time approximation scheme for the Knapsack problem
• 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
• Makespan minimization for two parallel machines with an availability constraint
• A note on parallel machine scheduling with non-simultaneous machine available time
• Approximability of scheduling with fixed jobs
• Parallel machine scheduling with machine availability and eligibility constraints
• Machine scheduling with an availability constraint
• The Multiple Subset Sum Problem
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Fast Approximation Algorithms for Knapsack Problems
• 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 Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

This page was built for publication: Approximation algorithms for scheduling with reservations