文献类型：期刊文献

英文题名：Online batch scheduling on parallel machines with delivery times

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

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

年份：2011

卷号：412

期号：39

起止页码：5333

外文期刊名：THEORETICAL COMPUTER SCIENCE

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

基金：This research was supported by the grant 09ZR1407200 of the Science Foundation of Shanghai and the National Natural Science Foundation of China (No. 11071072).

语种：英文

外文关键词：Online algorithm; Batch scheduling; Parallel machines; Delivery time

摘要：We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m = 2 or m = 3, respectively. When m >= 4, we present an online algorithm with a competitive ratio of 1.5 + o(1). (C) 2011 Elsevier B.V. All rights reserved.