Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Scheduling on unrelated parallel machines to maximize the minimum load

SpeakerNikhil Bansal

Co-authorMaxim Sviridenko

Suppose we are given a collection of n jobs which need to be scheduled on m machines. In the unrelated machines setting, the size of a job depends arbitrarily on the machine it is assigned to (we can view the machines are people, and they will process some jobs faster than other jobs depending on their skills and the nature of the job). We consider the problem of assigning the jobs to machines such that the total load on the least loaded machine is maximized. A natural motivation for this problem is in fair allocation of jobs.

Somewhat surprisingly, not many non-trivial results are known even for very special cases of this problem. In this talk, I will survey the known results and describe an approximation algorithm which significantly improves the approximation ratio for the so called "restricted assignment" case of this problem.