Online makespan minimization with parallel schedules

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

zbMATH Keywords

schedulingcompetitive analysisonline algorithmsmakespan minimization

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (18)

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

This page was built for publication: Online makespan minimization with parallel schedules