کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429317 687192 2006 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The load rebalancing problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The load rebalancing problem
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 60, Issue 1, July 2006, Pages 42-59