Paper Info
Title
Online Scheduling with Migration Cost
Abstract
In this paper, we consider a new variation of the classical online scheduling problem. In our model, an online scheduler is allowed to migrate the assigned jobs to different machines. Live migration is a powerful tool for load balancing. However, migration will incur additional cost in the destination machines. In this paper, we study the scheduling problem with migration cost model. Suppose that a job with processing time p which is already scheduled on the machine A is removed and transferred to the machine B, the load of the machine A will decrease p, but the load of the machine B will increase (1+ r) p, where 0 = r = 1 is a constant and it is called the migration factor. First, we propose an approximation algorithm for arbitrary machines. Then we give an improved algorithm for the case of two machines. Both algorithms are better than list scheduling algorithm [2] if the migration factor is smaller than a certain value. Finally, we implement our algorithms both in real data and random data. The experimental results indicate that the performances of algorithms are very close to the optimal algorithm.
Year
DOI
Venue
2012
10.1109/IPDPSW.2012.268
IPDPS Workshops
Keywords
Field
DocType
migration cost,destination machine,improved algorithm,list scheduling algorithm,migration factor,approximation algorithm,different machine,migration cost model,arbitrary machine,live migration,online scheduling,machine b,algorithm design and analysis,online algorithms,approximation,approximation algorithms,load balancing,computational modeling,scheduling,approximation theory,schedules,resource allocation
Online algorithm,Approximation algorithm,Mathematical optimization,Job shop scheduling,Algorithm design,Load balancing (computing),Computer science,Scheduling (computing),Live migration,Parallel computing,Schedule,Distributed computing
Conference
ISSN
Citations 
PageRank 
2164-7062
2
0.37
References 
Authors
5
1
Name
Order
Citations
PageRank
Shuangquan Yang170.82