Indexed by:Journal Article

Date of Publication:2013-11-01

Journal:Journal of Computational Information Systems

Included Journals:Scopus、EI

Volume:9

Issue:21

Page Number:8781-8786

ISSN:15539105

Abstract: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.