A better lower bound for on-line scheduling

DOI10.1016/0020-0190(94)00026-3zbMath0807.68013OpenAlexW1993134505WikidataQ127323639 ScholiaQ127323639MaRDI QIDQ1327292

Yair Bartal, Yuval Rabani, Howard J. Karloff

Publication date: 15 June 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00026-3

zbMATH Keywords

\(m\)-machine scheduling problem

Mathematics Subject Classification ID

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

Related Items (30)

A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ A lower bound for randomized on-line multiprocessor scheduling ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Online makespan minimization with budgeted uncertainty ⋮ List's worst-average-case or WAC ratio ⋮ On two dimensional packing ⋮ Improved lower bounds for the online bin stretching problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On the value of job migration in online makespan minimization ⋮ Randomized algorithms for that ancient scheduling problem ⋮ Semi-online scheduling problems on a small number of machines ⋮ Machine covering in the random-order model ⋮ Semi-online scheduling revisited ⋮ Tight Bounds for Online Vector Scheduling ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Scheduling In the random-order model ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Semi-online scheduling with decreasing job sizes ⋮ On-line algorithms for packing rectangles into several strips ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ Preemptive multiprocessor scheduling with rejection ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ Semi on-line algorithms for the partition problem ⋮ 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 ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ New algorithms for related machines with temporary jobs. ⋮ On-line scheduling revisited

Cites Work

• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Bounds for Certain Multiprocessing Anomalies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A better lower bound for on-line scheduling