In this paper we study some aspects of weighted flow time on parallel machines. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for Pr(i), pmtn Sigma w(i)F(i). We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for Deadline Scheduling. We finally give an O(1)-competitive algorithm for Deadline Scheduling.

Online weighted flow time and deadline scheduling / Becchetti, Luca; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Pruhs, Kirk R.. - 2129:(2001), pp. 36-47. (Intervento presentato al convegno 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/5th Int Workshop on Randomization and Approximation Techniques in Comp Sci tenutosi a BERKELEY, CALIFORNIA nel AUG 18-20, 2001) [10.1007/3-540-44666-4_8].

Online weighted flow time and deadline scheduling

BECCHETTI, Luca;Stefano Leonardi;MARCHETTI SPACCAMELA, Alberto;
2001

Abstract

In this paper we study some aspects of weighted flow time on parallel machines. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for Pr(i), pmtn Sigma w(i)F(i). We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for Deadline Scheduling. We finally give an O(1)-competitive algorithm for Deadline Scheduling.
2001
9783540424703
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/251526
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact