Semi-online scheduling revisited

DOI10.1016/j.tcs.2012.03.031zbMath1243.68093OpenAlexW2063410603MaRDI QIDQ442235

Matthias Hellwig, Susanne Albers

Publication date: 10 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.031

zbMATH Keywords

competitive analysismakespan minimizationonline computation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items (19)

A survey on makespan minimization in semi-online environments ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence ⋮ Rejecting jobs to minimize load and maximum flow-time ⋮ Semi-online scheduling: a survey ⋮ A two-phase algorithm for bin stretching with stretching factor 1.5 ⋮ Semi-online scheduling problems on a small number of machines ⋮ Bin stretching with migration on two hierarchical machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Dynamic scheduling of patients in emergency departments ⋮ Online early work maximization on three hierarchical machines with a common due date ⋮ An efficient algorithm for semi-online multiprocessor scheduling with given total processing time ⋮ Online bin stretching with three bins ⋮ An efficient algorithm for bin stretching ⋮ Online bin stretching with bunch techniques ⋮ Unnamed Item ⋮ Dynamic programming optimization in line of sight networks ⋮ An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time ⋮ Online bin packing with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• Semi-on-line multiprocessor scheduling with given total processing time
• New algorithms for an ancient scheduling problem.
• Semi on-line algorithms for the partition problem
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• Bin stretching revisited
• On-line scheduling revisited
• Semi-on-line scheduling on two parallel processors with an upper bound on the items
• The on-line multiprocessor scheduling problem with known sum of the tasks
• Semi-online scheduling on two uniform processors
• The Power of Reordering for Online Minimum Makespan Scheduling
• On randomized online scheduling
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• 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: Semi-online scheduling revisited