文献类型：期刊文献

英文题名：Optimal on-line algorithms for one batch machine with grouped processing times

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

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

年份：2011

卷号：22

期号：4

起止页码：509

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

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

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

语种：英文

外文关键词：Batching; Scheduling; On-line algorithm; Delivery time

摘要：In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1 + phi)p], where p > 0 and phi = (root 5-1)/2. Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio (root 5 + 1)/2 are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio (root 5+ 1)/2. The two class of algorithms are optimal for the problems studied here.