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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
