作者:Yong; HE; Hao; ZHOU; Yi; Wei; JIANG准在线算法优先权竞争分析优化算法
摘要: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.
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社