We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in online and online settings, can be significantly improved if we allow preemption, i.e., interrupt 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 the 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 the online or online setting. Leonardi and Raz [Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 110 119] showed that the well-known algorithm, shortest remaining processing time (SRPT), performs within a logarithmic factor of the optimal online 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 and thus SRPT, although it is an online algorithm, becomes the best known algorithm in the online setting. In fact, in the online setting, Leonardi and Raz showed that no algorithm can achieve a better bound. Without migration, no (online or online) approximations are known. This paper introduces a new algorithm that does not use migration, works online, and is just as effective ( in terms of approximation ratio) as the best known online algorithm that uses migration.

Minimizing the flow time without migration / Baruch, Awerbuch; Yossi, Azar; Leonardi, Stefano; Oded, Regev. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 31:5(2002), pp. 1370-1382. (Intervento presentato al convegno 31st Annual ACM Symposium on Theory of Computing tenutosi a ATLANDA, GEORGIA nel 1999) [10.1137/s009753970037446x].

Minimizing the flow time without migration

LEONARDI, Stefano;
2002

Abstract

We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in online and online settings, can be significantly improved if we allow preemption, i.e., interrupt 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 the 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 the online or online setting. Leonardi and Raz [Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 110 119] showed that the well-known algorithm, shortest remaining processing time (SRPT), performs within a logarithmic factor of the optimal online 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 and thus SRPT, although it is an online algorithm, becomes the best known algorithm in the online setting. In fact, in the online setting, Leonardi and Raz showed that no algorithm can achieve a better bound. Without migration, no (online or online) approximations are known. This paper introduces a new algorithm that does not use migration, works online, and is just as effective ( in terms of approximation ratio) as the best known online algorithm that uses migration.
2002
approximation; flow time; migration; online; scheduling
01 Pubblicazione su rivista::01a Articolo in rivista
Minimizing the flow time without migration / Baruch, Awerbuch; Yossi, Azar; Leonardi, Stefano; Oded, Regev. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 31:5(2002), pp. 1370-1382. (Intervento presentato al convegno 31st Annual ACM Symposium on Theory of Computing tenutosi a ATLANDA, GEORGIA nel 1999) [10.1137/s009753970037446x].
File allegati a questo prodotto
File Dimensione Formato  
VE_2002_11573-103510.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 169.39 kB
Formato Adobe PDF
169.39 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/103510
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 23
social impact