Robust algorithms for preemptive scheduling

DOI10.1007/s00453-012-9718-3zbMath1307.68091OpenAlexW2153644134MaRDI QIDQ472464

Leah Epstein, Asaf Levin

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9718-3

zbMATH Keywords

preemptive schedulingrobust algorithmsmigration factor

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (12)

Online load balancing with general reassignment cost ⋮ Bin stretching with migration on two hierarchical machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ 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 ⋮ Online Bin Covering with Limited Migration ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration ⋮ Online scheduling with migration on two hierarchical machines ⋮ Robust online algorithms for dynamic choosing problems

Cites Work

• Unnamed Item
• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• Approximation algorithms for scheduling unrelated parallel machines
• Minimizing makespan and preemption costs on a system of uniform machines
• A robust APTAS for the classical bin packing problem
• Preemptive online scheduling: Optimal algorithms for all speeds
• Optimal and online preemptive scheduling on uniformly related machines
• Preemptive on-line scheduling for two uniform processors
• On-line scheduling revisited
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for on-line scheduling on uniformly related machines
• Optimal preemptive scheduling for general target functions
• Scheduling with Deadlines and Loss Functions
• Robust Approximation Schemes for Cube Packing
• AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items
• Online Scheduling with Bounded Migration
• A Robust PTAS for Machine Covering and Packing
• PREEMPTIVE SCHEDULING ALGORITHMS WITH NESTED PROCESSING SET RESTRICTION
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• The Competitiveness of On-Line Assignments
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Approximation schemes for ordered vector packing problems
• On-Line Load Balancing for Related Machines
• Bounds for Certain Multiprocessing Anomalies
• Optimal Preemptive Scheduling on Two-Processor Systems
• Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
• Preemptive Online Scheduling with Reordering
• Randomized on-line scheduling on two uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios

This page was built for publication: Robust algorithms for preemptive scheduling