The Power of Reordering for Online Minimum Makespan Scheduling

DOI10.1137/130919738MaRDI QIDQ3190699zbMATH OpenOpenAlexFDO

Authors Matthias Englert, Deniz Özmen, Matthias Westermann

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

zbMATH Keywords

competitive analysisminimum makespan schedulingonline algorithmsreordering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Improved semi-online makespan scheduling with a reordering buffer
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Preemptive online scheduling with reordering
• Preemptive Online Scheduling with Reordering
• Max-min online allocations with a reordering buffer
• Max-min online allocations with a reordering buffer
• Online makespan minimization: the power of restart
• On-line scheduling on a batch machine to minimize makespan with limited restarts

Cited in

(29)

• 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
• Semi-online scheduling: a survey
• Online minimum makespan scheduling with a buffer
• 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
• Online makespan minimization: the power of restart
• Online Makespan Scheduling with Job Migration on Uniform Machines
• Tight bounds for online coloring of basic graph classes
• Semi-online preemptive scheduling: one algorithm for all variants
• Preemptive online scheduling with reordering
• Max-min online allocations with a reordering buffer
• Max-min online allocations with a reordering buffer
• Preemptive Online Scheduling with Reordering
• Online scheduling with rearrangement on two related machines
• Optimal algorithms for online scheduling with bounded rearrangement at the end
• Semi-online scheduling with non-increasing job sizes and a buffer
• Online scheduling with a buffer on related machines
• Semi-online models for cardinality constrained bin packing
• Scheduling with testing on multiple identical parallel machines
• Online makespan minimization with budgeted uncertainty

This page was built for publication: The Power of Reordering for Online Minimum Makespan Scheduling

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