Online makespan minimization with parallel schedules
From MaRDI portal
Publication:2362356
DOI10.1007/s00453-016-0172-5zbMath1370.68331arXiv1304.5625OpenAlexW1569597315MaRDI QIDQ2362356
Susanne Albers, Matthias Hellwig
Publication date: 7 July 2017
Published in: Algorithmica, Algorithm Theory – SWAT 2014 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.5625
Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)
Related Items
A survey on makespan minimization in semi-online environments, Scheduling with testing on multiple identical parallel machines, Online algorithms with advice for the dual bin packing problem, Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence, Semi-online scheduling: a survey, Optimal Online Edge Coloring of Planar Graphs with Advice, Multi-round cooperative search games with multiple players, Parallel solutions for preemptive makespan scheduling on two identical machines, A Production Plan Considering Parallel Machines and Deteriorating Effects: Minimizing the Makespan in the Section of Steel Box Girder Processing, Parallel solutions for ordinal scheduling with a small number of machines, Speed-robust scheduling: sand, bricks, and rocks, Reordering buffer management with advice, Parallel online algorithms for the bin packing problem, Online algorithms with advice: the tape model, Weighted online problems with advice, Weighted Online Problems with Advice, Speed-robust scheduling. Sand, bricks, and rocks, A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online algorithms with advice for bin packing and scheduling problems
- Online bin stretching with bunch techniques
- Online computation with advice
- Semi-on-line multiprocessor scheduling with given total processing time
- New algorithms for an ancient scheduling problem.
- An on-line graph coloring algorithm with sublinear performance ratio
- Semi on-line algorithms for the partition problem
- Coloring inductive graphs on-line
- A better lower bound for on-line scheduling
- On-line scheduling revisited
- Semi-on-line scheduling on two parallel processors with an upper bound on the items
- On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
- On the value of job migration in online makespan minimization
- An efficient algorithm for bin stretching
- The on-line multiprocessor scheduling problem with known sum of the tasks
- On the Advice Complexity of the k-Server Problem
- Online Scheduling with Bounded Migration
- The Power of Reordering for Online Minimum Makespan Scheduling
- Collective tree exploration
- Better Algorithms for Online Bin Stretching
- How to learn an unknown environment. I
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Better Bounds for Online Scheduling
- Navigating in Unfamiliar Geometric Terrain
- An Online Algorithm for Improving Performance in Navigation
- Improved Bounds for the Online Scheduling Problem
- A Better Algorithm for an Ancient Scheduling Problem
- Bounds for Certain Multiprocessing Anomalies
- On-line bin-stretching