The Power of Reordering for Online Minimum Makespan Scheduling
From MaRDI portal
Publication:3190699
DOI10.1137/130919738zbMath1301.68277OpenAlexW2094578294MaRDI QIDQ3190699
Matthias Westermann, Matthias Englert, Deniz Özmen
Publication date: 18 September 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/60729/7/WRAP_Englert_paper.pdf
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)
Related Items (24)
A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Online makespan minimization with budgeted uncertainty ⋮ Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence ⋮ On the value of job migration in online makespan minimization ⋮ Semi-online scheduling: a survey ⋮ Improved semi-online makespan scheduling with a reordering buffer ⋮ Online scheduling with rearrangement on two related machines ⋮ Scheduling on parallel identical machines with late work criterion: offline and online cases ⋮ Unnamed Item ⋮ Semi-online scheduling revisited ⋮ Online scheduling with one rearrangement at the end: revisited ⋮ Optimal algorithms for online scheduling with bounded rearrangement at the end ⋮ Tight bounds for online coloring of basic graph classes ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Scheduling In the random-order model ⋮ Semi-online algorithms for hierarchical scheduling on three parallel machines with a buffer size of 1 ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ Online scheduling with a buffer on related machines ⋮ Online makespan scheduling with job migration on uniform machines ⋮ A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model ⋮ Tight Bounds for Online Coloring of Basic Graph Classes
This page was built for publication: The Power of Reordering for Online Minimum Makespan Scheduling
