Approximation algorithms for scheduling with reservations

DOI10.1007/S00453-008-9271-2zbMATH Open1204.68273OpenAlexW1971872799MaRDI QIDQ5961975FDOQ5961975

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

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

zbMATH Keywords

complexityapproximation algorithmsschedulinginapproximabilityapproximation schemePTASreservations

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A 3/4-approximation algorithm for multiple subset sum
• The multiple subset sum problem
• 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)?
• Title not available (Why is that?)
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Makespan minimization for two parallel machines with an availability constraint
• A PTAS for the multiple subset sum problem with different knapsack capacities
• Machine scheduling with an availability constraint
• A new fully polynomial time approximation scheme for the Knapsack problem
• Parallel machine scheduling with machine availability and eligibility constraints
• Title not available (Why is that?)
• The effect of machine availability on the worst-case performance of LPT
• Parallel machines scheduling with nonsimultaneous machine available time
• Approximability of scheduling with fixed jobs
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A note on parallel machine scheduling with non-simultaneous machine available time

Cited In (7)

• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• Algorithms – ESA 2005
• Parallel machines scheduling with machine maintenance for minsum criteria
• Approximability of scheduling with fixed jobs
• Reservation table scheduling: branch-and-bound based optimizationvs. integer linear programming techniques
• Periodic scheduling with obligatory vacations
• 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)