Semi-online machine covering for two uniform machines

作     者：Chen, Xingyu Epstein, Leah Tan, Zhiyi 

作者机构：Univ Haifa Dept Math IL-31905 Haifa Israel Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2009年第410卷第47-49期

页      面：5047-5062页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [10671177, 60021201] Zhejiang Provincial Natural Science Foundation of China [Y607079] 

主　　题：Two-machine scheduling Semi-online algorithms 

摘      要：The machine covering problem deals with partitioning a sequence of jobs among a set of machines, so as to maximize the completion time of the least loaded machine. We study a semi-online variant, where jobs arrive one by one, sorted by non-increasing size. The jobs are to be processed by two uniformly related machines, with a speed ratio of q = 1. Each job has to be processed continuously, in a time slot assigned to it on one of the machines. This assignment needs to be performed upon the arrival of the job. The length of the time slot, which is required for a specific job to run on a given machine, is equal to the size of the job divided by the speed of the machine. We give a complete competitive analysis of this problem by providing an algorithm of the best possible competitive ratio for every q = 1. We first give a tight analysis of the performance of a natural greedy algorithm LPT for the problem. To achieve the best possible performance for the semi-online problem, we use a combination of LPT, together with two alternative algorithms which we design. The new algorithms attain the best possible competitive ratios in the two intervals q is an element of (1 . root 15) and q is an element of (2.4856, 1 + root 3). respectively, whereas the greedy algorithm has the best possible competitive ratio for any other q = 1. (C) 2009 Elsevier B.V. All rights reserved.