Minimizing flow time on related machines
Naveen Garg
IIT, Delhi.
18-01-06

---

Abstract

We consider a scheduling problem in which we have m machines with different speeds. Jobs arrive over time and can be scheduled on any machine. The time required by a machine to complete a job equals the length of the job divided by the speed of the machine. The jobs can be preempted but cannot migrate from one machine to another. The objective is to minimize the total flow time; the flow time of a job is the time that it is in the system.

We present an online algorithm with a competitive ratio of O(log P) where P is the ratio of the maximum to minimum length of a job. This is the first result for this problem and matches the competitive ratio for the case of parallel machines.