文献类型：期刊文献

英文题名：A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines

作者：Liu, Peihai[1];Lu, Xiwen[1];Fang, Yang[1]

机构：[1]E China Univ Sci & Technol, Sch Sci, Shanghai 200237, Peoples R China

年份：2012

卷号：15

期号：1

起止页码：77

外文期刊名：JOURNAL OF SCHEDULING

收录：;EI(收录号：20122115051628);WOS:【SCI-EXPANDED(收录号:WOS:000300489600008)】；

基金：The authors would like to thank the anonymous referees whose comments very much helped to improve this paper. This research was supported by the grant 09ZR1407200 of Science Foundation of Shanghai and NSFC (10771067).

语种：英文

外文关键词：Scheduling; Parallel Batch Machines; On-line

摘要：We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than 1 + (root m(2) + 4 - m)/2, where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.