Semi on-line scheduling problem for maximizing the minimum machine completion time on m identical machines

In this paper, a semi on-line version on m identical machines M1, M2,…,Mm (m>3) was considered, where the processing time of the largest job is known in advance. The goal is to maximize the minimum machine load, an algorithm was presented and its worst-case ratio was proved to be equal to m−1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2m−1) pmax where pmax is the largest job's processing time, then the worst case ratio is 2.1/m.