We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC ’01, SODA ’03, FOCS ’18) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time – namely O(logP), O(logD) and O(logW), where P,D,W are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully.

Flow time scheduling with uncertain processing time / Azar, Yossi; Leonardi, Stefano; Touitou, Noam. - (2021), pp. 1070-1080. (Intervento presentato al convegno 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 tenutosi a Roma/visrtual) [10.1145/3406325.3451023].

Flow time scheduling with uncertain processing time

Leonardi, Stefano
;
2021

Abstract

We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC ’01, SODA ’03, FOCS ’18) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time – namely O(logP), O(logD) and O(logW), where P,D,W are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully.
2021
53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Flow-Time Scheduling; Online Algorithms; Predicted processing times
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Flow time scheduling with uncertain processing time / Azar, Yossi; Leonardi, Stefano; Touitou, Noam. - (2021), pp. 1070-1080. (Intervento presentato al convegno 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 tenutosi a Roma/visrtual) [10.1145/3406325.3451023].
File allegati a questo prodotto
File Dimensione Formato  
Azar_Flow-time_2021.pdf

solo gestori archivio

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

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Creative commons
Dimensione 743.4 kB
Formato Adobe PDF
743.4 kB Adobe PDF

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/1557216
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 9
social impact