文献类型：期刊文献

英文题名：Online LPT algorithms for parallel machines scheduling with a single server

作者：Su, Chunjie[1]

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

年份：2013

卷号：26

期号：3

起止页码：480

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

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

语种：英文

外文关键词：Parallel machines; Server; Online algorithm; Competitive ratio

摘要：We consider two parallel machines scheduling problems with a single server. For the general case we present an online LPT algorithm with competitive ratio 2, and give a lower bound . We also apply the online LPT algorithm to the special case where all the setup times are equal to 1. We show that the competitive ratio is 1.5, and no online algorithm can has a competitive ratio less than root 2.