Approximation algorithms for scheduling with reservations

DOI10.1007/S00453-008-9271-2MaRDI QIDQ5961975zbMATHOpenAlexFDO

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

complexityapproximation algorithmsschedulinginapproximabilityapproximation schemePTASreservations

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

• 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?)
• A 3/4-approximation algorithm for multiple subset sum
• A PTAS for the multiple subset sum problem with different knapsack capacities
• 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 new fully polynomial time approximation scheme for the Knapsack problem
• A note on parallel machine scheduling with non-simultaneous machine available time
• 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
• 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)

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

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)