Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size  

作　　者：Yong HE Hao ZHOU Yi Wei JIANG 

机构地区：[1]State Key Lab of CAD & CG, Zhejiang University [2]Department of Mathematics, Zhejiang University

出　　处：《Acta Mathematica Sinica,English Series》2006年第2期587-594,共8页数学学报（英文版）

基　　金：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)

摘　　要：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.

关 键 词：SEMI-ONLINE Preemptive scheduling Competitive analysis 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O224[自动化与计算机技术—计算机科学与技术]