Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes

DOI10.1016/j.ipl.2021.106211OpenAlexW3202877791MaRDI QIDQ2059895

Asaf Levin

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106211

zbMATH Keywords

schedulingonline algorithmsanalysis of algorithmsrobust algorithmsmigration factor

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Bin stretching with migration on two hierarchical machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Online scheduling with migration on two hierarchical machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robust algorithms for preemptive scheduling
• 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
• Using fast matrix multiplication to find basic solutions
• An optimal algorithm for preemptive on-line scheduling
• A lower bound for on-line scheduling on uniformly related machines
• Robust algorithms for total completion time
• Fully dynamic bin packing revisited
• Optimal preemptive scheduling for general target functions
• Scheduling with Deadlines and Loss Functions
• Robust Approximation Schemes for Cube Packing
• Online Scheduling with Bounded Migration
• Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Fully-Dynamic Bin Packing with Little Repacking
• Symmetry exploitation for online machine covering with bounded migration
• Online Bin Covering with Limited Migration
• A Robust AFPTAS for Online Bin Packing with Polynomial Migration

This page was built for publication: Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes