A better lower bound for on-line scheduling

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

Yuval Rabani, Yair Bartal, 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

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming, On-line algorithms for packing rectangles into several strips, Semi-online scheduling with decreasing job sizes, Preemptive multiprocessor scheduling with rejection, An optimal online algorithm for scheduling two machines with release times, Semi-online scheduling problems on a small number of machines, Semi-online scheduling revisited, Improved bounds for online scheduling with eligibility constraints, List's worst-average-case or WAC ratio, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Semi on-line algorithms for the partition problem, New algorithms for related machines with temporary jobs., On-line scheduling revisited, Load balancing of temporary tasks in the \(\ell _{p}\) norm

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