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

Abstract

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 (3m-1)/(m+1) [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.