文献类型：期刊文献

英文题名：On minimizing total completion time in batch machine scheduling

作者：Poon, CK; Cu, WC

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

年份：2004

卷号：15

期号：4

起止页码：593

外文期刊名：INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

收录：;WOS:【SCI-EXPANDED(收录号:WOS:000227176400002)】；

语种：英文

外文关键词：scheduling; batch machine; bounded capacity; total completion

摘要：We study the scheduling problem on a batch machine which is capable of processing a batch of jobs at a time. For a batch machine of capacity c, we designed an algorithm for minimizing the total completion time in O(n(6c)) time (for sufficiently large c). This improves the best previous time bound of O(n(c(c-1))) given by Brucker et al [1]. We also designed a new algorithm with running time n(O(rootn)).