Semi-Online Algorithms for Scheduling with Machine Cost  

作　　者：蒋义伟 何勇 

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

出　　处：《Journal of Computer Science & Technology》2006年第6期984-988,共5页计算机科学技术学报（英文版）

基　　金：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）.

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

关 键 词：SEMI-ONLINE preemptive scheduling machine cost competitive ratio 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]