摘要
This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.
This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least （2m-3）/（m-1） for any m〉2 and present optimal semi-online algorithms for m = 2, 3.
基金
support by the Teaching and Research Award Program for Outstanding Young Teachers in Higer Education Institutions of MOE,China
by National Natural Science Foundation of China (10271110, 60021201)
