A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption

Abstract

We prove a new lower bound of 2.564 on deterministic online algorithms for makespan scheduling on related machines (without preemptions).

Keywords

• online algorithms
• scheduling