Semi-Online Algorithms for Scheduling with Machine Cost

作     者：蒋义伟 何勇 

作者机构：Faculty of Science Zhejiang Sci- Tech University Hangzhou 310018 P R. China Department of Mathematics Zhejiang University Hangzhou 310027 P.R. China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2006年第21卷第6期

页      面：984-988页

核心收录：

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

基　　金：Research supported by the Natural Science Foundation of Zhejiang Province (Grant No. Y605316)  and Natural Science Foundation of Education Department of Zhejiang Province (Grant No. 20060578) 

主　　题：semi-online preemptive scheduling machine cost competitive ratio 

摘      要：In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.