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 M_1, M_2, M_3 where the processing time of the largest job is known in advance. A speed s_i(s_1 = s_2 = 1,1 ≤ s_3 = s) is associated with machine M_i. Our goal is to maximize the C_(min) — the minimum workload of three machines. We give a C_(min3) 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 C_(min3) is tight.