点击次数：

论文类型：期刊论文

发表时间：2013-02-28

发表刊物：INFORMATION PROCESSING LETTERS

收录刊物：SCIE、EI

卷号：113

期号：4

页面范围：127-131

ISSN号：0020-0190

关键字：Analysis of algorithms; Semi-online scheduling; Competitive ratio; Hierarchy

摘要：In this paper, we consider semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the makespan. The first investigated problem is the buffer version, where a buffer of a fixed capacity K is available for storing at most K jobs. When the current job is given, we are allowed to assign it on some machine irrecoverably; or temporarily store it in the buffer. But in the latter case if the buffer was full then an earlier job is removed from the buffer and assigned it to some machine. The second one is a reassignment version, where when the input is end, we are allowed to reassign at most K jobs. For both versions, we show no online algorithm can have a competitive ratio less than 3/2, then propose two online algorithms with a competitive ratio 3/2 with K = 1 for both versions of the problem, i.e., using only buffer of size one, or using only one rearrangement at the end. (C) 2013 Elsevier B.V. All rights reserved.