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.