The Power of Reordering for Online Minimum Makespan Scheduling
From MaRDI portal
Publication:3190699
DOI10.1137/130919738zbMath1301.68277MaRDI 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
68Q25: Analysis of algorithms and problem complexity
90B35: Deterministic scheduling theory in operations research
68W27: Online algorithms; streaming algorithms
Related Items
Unnamed Item, Online Makespan Scheduling with Job Migration on Uniform Machines, Tight Bounds for Online Coloring of Basic Graph Classes, Improved semi-online makespan scheduling with a reordering buffer, Semi-online scheduling revisited, Online scheduling with one rearrangement at the end: revisited, Online scheduling with rejection and reordering: exact algorithms for unit size jobs, Semi-online preemptive scheduling: one algorithm for all variants, Online scheduling with rearrangement on two related machines, Optimal algorithms for online scheduling with bounded rearrangement at the end, Online scheduling with a buffer on related machines, Scheduling with testing on multiple identical parallel machines, Online makespan minimization with budgeted uncertainty, A survey on makespan minimization in semi-online environments, Scheduling on parallel identical machines with late work criterion: offline and online cases, 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, A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model, Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence, Tight bounds for online coloring of basic graph classes, Online makespan minimization with parallel schedules, On the value of job migration in online makespan minimization, Semi-online scheduling: a survey
