کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429317 | 687192 | 2006 | 18 صفحه PDF | دانلود رایگان |

In the classical load balancing or multiprocessor scheduling problem, we are given a sequence of jobs of varying sizes and are asked to assign each job to one of the m empty processors. A typical objective is to minimize the makespan, which is the load on the heaviest loaded processor. Since in most real world scenarios the load is a dynamic measure, the initial assignment may not remain optimal over time. Motivated by such considerations in a variety of systems, we formulate the problem of load rebalancing—given a possibly suboptimal assignment of jobs to processors, relocate a set of the jobs so as to decrease the makespan. Specifically, the goal is to achieve the best possible makespan under the constraint that no more than k jobs are relocated. We also consider the weighted version of this problem where there is an arbitrary cost associated with each job's relocation. The problem is NP-hard and hence, we focus on approximation algorithms. We construct an algorithm which achieves a 1.5-approximation, with near linear running time. We also show that the problem has a PTAS, thereby resolving the complexity issue. Finally, we investigate the approximability of several extensions of the load rebalancing model.
Journal: Journal of Algorithms - Volume 60, Issue 1, July 2006, Pages 42-59