文献类型：期刊文献

英文题名：On-line scheduling of parallel machines to minimize total completion times

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

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

年份：2009

卷号：36

期号：9

起止页码：2647

外文期刊名：COMPUTERS & OPERATIONS RESEARCH

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

语种：英文

外文关键词：Parallel machine scheduling; Analysis of algorithm; On-line algorithm

摘要：In this paper, we consider the scheduling problem on identical parallel machines, in which jobs are arriving over time and preemption is not allowed. The goal is to minimize the total completion times. According to the idea of the Delayed-SPT Algorithm proposed by Hoogeven and Vestjens [Optimal on-line algorithms for single-machine scheduling. In: Proceedings 5th international conference on integer programming and combinatorial optimization (IPCO). Lecture notes in computer science, vol. 1084. Berlin: Springer; 1996. p. 404-14], we give an on-line algorithm for the scheduling problem on m identical parallel machines. We show that this algorithm is 2-competitive and the bound is tight. (C) 2008 Elsevier Ltd. All rights reserved.