Title:  Minimizing flow-time on unrelated machines

Abstract: The unrelated machine setting is the 
following: There are m machines and n jobs,  where 
job j has an arbitrary machine-dependent size p_ij 
on machine i. Given a schedule, the flow time of a 
job is defined as the time spent by the job in the 
system (i.e. its completion time minus  its arrival 
time). 

We consider the  two classic objectives of minimizing 
the average flow time and the maximum flow time, and 
describe the first poly-logarithmic approximation 
algorithms for these problems in the unrelated
machines setting.