Approximation algorithms for scheduling with reservations

DOI10.1007/S00453-008-9271-2MaRDI QIDQ5961975zbMATH OpenOpenAlexFDO

Authors Florian Diedrich, Klaus Jansen, Fanny Pascual, Denis Trystram

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

approximation algorithmsapproximation schemecomplexityinapproximabilityPTASreservationsscheduling

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for scheduling with resource and precedence constraints
• scientific article; zbMATH DE number 16428
• Approximation scheduling algorithms: a survey
• Approximation algorithms for time constrained scheduling
• Approximation algorithms for problems in scheduling with set-ups
• On approximating a scheduling problem
• scientific article; zbMATH DE number 1560337
• On the optimality of exact and approximation algorithms for scheduling problems
• Approximation schemes for scheduling with availability constraints

Cites work

• A 3/4-approximation algorithm for multiple subset sum
• A new fully polynomial time approximation scheme for the Knapsack problem
• A note on parallel machine scheduling with non-simultaneous machine available time
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A PTAS for the multiple subset sum problem with different knapsack capacities
• Algorithms for Scheduling Independent Tasks
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Approximability of scheduling with fixed jobs
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• scientific article; zbMATH DE number 1418266 (Why is no real title available?)
• Machine scheduling with an availability constraint
• Makespan minimization for two parallel machines with an availability constraint
• Parallel machine scheduling with machine availability and eligibility constraints
• Parallel machines scheduling with nonsimultaneous machine available time
• The effect of machine availability on the worst-case performance of LPT
• The multiple subset sum problem
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(8)

• Periodic scheduling with obligatory vacations
• Approximability of scheduling with fixed jobs
• Reservation table scheduling: branch-and-bound based optimizationvs. integer linear programming techniques
• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• Parallel machines scheduling with machine maintenance for minsum criteria
• Improved approximation algorithms for scheduling with fixed jobs
• Algorithms – ESA 2005
• Absolute bounds of list algorithms for parallel machines scheduling with unavailability periods

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961975)