Online weighted flow time and deadline scheduling |
| |
| Authors: | Luca Becchetti Stefano Leonardi Alberto Marchetti-Spaccamela Kirk Pruhs |
| |
| Institution: | aDipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Italy;bComputer Science Department, University of Pittsburgh, USA |
| |
| Abstract: | In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|ri,pmtn|∑wiFi. 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 then give an O(1)-competitive algorithm for deadline scheduling. |
| |
| Keywords: | Scheduling Weighted flow time On-line |
| 本文献已被 ScienceDirect 等数据库收录！ |
