Semi-on-line scheduling problem for maximizing the minimum machine completion time on three special uniform machines

In this paper, we investigate a semi-on-line version for a special case of three machines M1, M2, M3 where the processing time of the largest job is known in advance. A speed si(s1 = s2 = 1, 1 ⩽ s3 = s) is associated with machine Mi. Our goal is to maximize the Cmin – the minimum workload of three machines. We give a Cmin3 algorithm and prove its competitive ratio is max{2,(3s+2)/(2+s)} and the algorithm is the best possible for 1⩽s⩽2. We also claim the competitive ratio of algorithm Cmin3 is tight.