文献类型：期刊文献

英文题名：An optimal semi-online algorithm for 2-machine scheduling with an availability constraint

作者：Li, Hongying[1];Su, Chunjie[1]

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

年份：2011

卷号：22

期号：2

起止页码：153

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

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

语种：英文

外文关键词：Scheduling; Semi-online; Availability; Algorithm; Competitive ratio

摘要：This paper considers a problem of semi-online scheduling jobs on two identical parallel machines with objective to minimize the makespan. We assume there is an unavailable period [B,F] on one machine and the largest job processing time P (max) is known in advance. After comparing B with P (max) we consider three cases, and we show a lower bound of the problem are 3/2, 4/3 and 3/2, 4/3 and (root 5 + 1)/2, respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.