Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi....Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.展开更多
文摘Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.
