Minimizing the flow time without migration
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev · 1999
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (tota time in the system).The performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption: i.e., intermpt a job and later continue its execution, perhaps migrating it to a different machine.Preemption is inherent to make a scheduling algorithm efficient.While in case of a single processor, most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead.Thus, it is not commonly used in most multiprocessor operating systems.The natural question is whether migration is an inherent component for an efficient scheduling algorithm, in either online or offline setting.Leonardi and Raz (STOC'97) showed that the well known algorithm, shortest remaining processing time (SRF'I'), performs within a logarithmic factor of the optimal algorithm.Note that SRPT must use both preemption and migration to schedule the jobs.It is not known if better approximation factors can be reached.In fact, in the on-line setting, Leonardi and Raz showed that no algorithm