کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431792 688629 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online weighted flow time and deadline scheduling
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Online weighted flow time and deadline scheduling
چکیده انگلیسی

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|∑wiFiP|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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 4, Issue 3, September 2006, Pages 339–352
نویسندگان
, , , ,