A new algorithm for online uniform-machine scheduling to minimize the makespan

We consider the online scheduling problem with m−1, m⩾2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1⩽s⩽2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91–103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414–422]. It has a worst-case bound of 2.8795 for a big m and s=2. In this note we present a 2.45-competitive algorithm for m⩾4 and any s, 1⩽s⩽2.