点击次数：

论文类型：期刊论文

发表时间：2013-11-01

发表刊物：Journal of Computational Information Systems

收录刊物：EI、Scopus

卷号：9

期号：21

页面范围：8781-8786

ISSN号：15539105

摘要：In this paper, we consider a semi-online hierarchical scheduling problem with reassignment at any time on two identical machines, with the purpose of minimizing the makespan. Jobs arrive one by one over list, when a new job arrives, at most K already scheduled jobs can be removed from one machine to the other, then all removed jobs and the new job must be assigned to the machines, where K>0 is a fixed integer. We prove the lower bound of this problem is 3/2, and then propose an optimal algorithm using K=1 to match this lower bound. ? 2013 Binary Information Press.