An On-Line Algorithm for Some Uniform Processor Scheduling

This paper considers the problem of on-line scheduling a set of independent jobs on m uniform machines (M1 , M2 ,..., Mm ) in which machine Mi's processing speed is si =1 (i=1,..., m-1) and sm=s >1. List scheduling [Y. Cho and S. Sahni, SIAM J. Comput., 9 (1980), pp. 91--103] guarantees a worst-case performance of 3m-1/m+1 (m≥ 3) and 1+√ 52 (m=2) for this problem. We prove that this worst-case bound cannot be improved for m=2 and m=3 and for every m≥ 4, an algorithm with worst-case performance at most 3m-1/m+1- is presented when sm=2,$ where e is a fixed positive number, and then we improve the bound for general sm=s > 1.