Online makespan minimization: the power of restart

DOI10.4230/LIPICS.APPROX-RANDOM.2018.14MaRDI QIDQ5009506zbMATH OpenFDO

Authors Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yu-Hao Zhang, Zhiyi Huang

Publication date 4 August 2021

Full work available at URL https://arxiv.org/abs/1806.02207

zbMATH Keywords

identical machinesmakespan minimizationonline scheduling

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
• scientific article; zbMATH DE number 1947447
• Minimizing the total completion time on-line on a single machine, using restarts
• Online scheduling with restart on parallel machines
• Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

Cites work

• A Better Algorithm for an Ancient Scheduling Problem
• A lower bound for on-line scheduling on uniformly related machines
• A lower bound for randomized on-line scheduling algorithms
• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• An optimal algorithm for preemptive on-line scheduling
• An optimal online algorithm for scheduling two machines with release times
• Better Bounds for Online Scheduling
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 1305421 (Why is no real title available?)
• Improved Bounds for the Online Scheduling Problem
• Minimizing total flow time and total completion time with immediate dispatching
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On-Line Load Balancing for Related Machines
• On-line scheduling on a single machine: Maximizing the number of early jobs
• On-line scheduling revisited
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online scheduling with a buffer on related machines
• Preemptive on-line scheduling for two uniform processors
• Preemptive online scheduling with reordering
• Preemptive online scheduling: Optimal algorithms for all speeds
• Scheduling on identical machines: How good is LPT in an on-line setting?
• Semi on-line algorithms for the partition problem
• The Power of Reordering for Online Minimum Makespan Scheduling

Cited in

(6)

• Minimizing the maximum starting time on-line
• The Power of Reordering for Online Minimum Makespan Scheduling
• scientific article; zbMATH DE number 1947447 (Why is no real title available?)
• Minimizing the total completion time on-line on a single machine, using restarts
• Well-behaved online load balancing against strategic jobs
• A simpler competitive analysis for scheduling equal-length jobs on one machine with restarts

This page was built for publication: Online makespan minimization: the power of restart

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009506)