Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines  

作　　者：Yong HE Yi Wei JIANG Hao ZHOU 

机构地区：[1]Department of Mathematics, Zhejiang University. Hangzhou 310027. P. R. China [2]Faculty of Science, Zhejiang Sci- Tech University Hangzhou 310018, P. R. China. [3]Department of Mathematics, Zhejiang University Hangzhou 310027. P. R. China [4]Basic Course Department, Zhejiang Shorten University Hangzhou 310015. P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2007年第1期165-174,共10页数学学报（英文版）

基　　金：National Natural Science Foundation of"China(10271110,60021201);the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE,China

摘　　要：In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.

关 键 词：SEMI-ONLINE preemptive scheduling uniform machines competitive ratio 

分 类 号：O24[理学—计算数学]