文献类型：期刊文献

英文题名：On-line scheduling algorithms for a batch machine with finite capacity

作者：Poon, Chung Keung[1]; Yu, Wenci[2]

机构：[1]City Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China;[2]E China Univ Sci & Technol, Inst Appl Math, Shanghai 200237, Peoples R China

年份：2005

卷号：9

期号：2

起止页码：167

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

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

语种：英文

外文关键词：scheduling; batch machine; release time; makespan; on-line

摘要：We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.