Minimizing average flow-time : the unrelated case

machines setting. We have a set of machines, and jobs arrive over time.
Each job gets processed on exactly one machine, but may require different
processing times on different machines. The flow-time of a job is defined
as its total waiting time in the system before it gets completely
processed. The goal is to find a schedule which minimizes the total
flow-time of jobs. We shall use the standard assumption that jobs can be pre-empted.

We give general techniques for getting good approximation algorithms for a large sub-class of this problem. As special cases, we get following
results : (1) O(K)-approximation algorithm if the set of processing times
of all the jobs (on all machines) is of size K, (2) O(log P)-approximation
algorithm if each job can only go on a specified subset of machines, but
has the same processing requirement on each such machine. Further, the
machines can have different speeds. Here P is the ratio of the largest to the smallest
processing requirement, (3) constant approximation algorithm for the
unrelated case if we assume that our algorithm has slightly more resources
than the optimum.

Another merit of our algorithm is that it is very simple, and considerably
simplifies known results for several special cases of the scheduling problem.
This is joint work with Naveen Garg and V. Muralidhara.