Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures

DOI10.1287/moor.2015.0765zbMath1342.90069OpenAlexW2330297616MaRDI QIDQ3186540

José Verschae, Martin Skutella

Publication date: 10 August 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2015.0765

zbMATH Keywords

machine schedulingonline algorithmsrecourse

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (18)

Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Online load balancing with general reassignment cost ⋮ Bin stretching with migration on two hierarchical machines ⋮ Machine covering in the random-order model ⋮ Online load balancing on uniform machines with limited migration ⋮ Unnamed Item ⋮ Online minimization of the maximum starting time: migration helps ⋮ Online bin covering with limited migration ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Robust algorithms for total completion time ⋮ Exact lexicographic scheduling and approximate rescheduling ⋮ Fully dynamic bin packing revisited ⋮ Online Bin Covering with Limited Migration ⋮ Starting time minimization for the maximum job variant ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ Approximate and robust bounded job start scheduling for Royal Mail delivery offices ⋮ Online scheduling with migration on two hierarchical machines ⋮ Robust online algorithms for dynamic choosing problems

Cites Work

• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• New algorithms for an ancient scheduling problem.
• A robust APTAS for the classical bin packing problem
• Approximation schemes for scheduling on parallel machines
• Improved bounds for on-line load balancing
• A lower bound for randomized on-line scheduling algorithms
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Online algorithms: a survey
• On-line scheduling revisited
• Robust Approximation Schemes for Cube Packing
• Integer Programming with a Fixed Number of Variables
• Robust Algorithms for Preemptive Scheduling
• Online Scheduling with Bounded Migration
• On randomized online scheduling
• A Robust PTAS for Machine Covering and Packing
• Sensitivity theorems in integer linear programming
• Better Bounds for Online Scheduling
• Improved Bounds for the Online Scheduling Problem
• A Better Algorithm for an Ancient Scheduling Problem
• Load Balancing for Response Time
• Bounds for Certain Multiprocessing Anomalies
• On-line machine covering
• Competitive routing of virtual circuits with unknown duration

This page was built for publication: Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures