کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428744 686904 2008 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lower bounds on online deadline scheduling with preemption penalties
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Lower bounds on online deadline scheduling with preemption penalties
چکیده انگلیسی

We generalize and improve previous results of online preemptive deadline scheduling with preemption penalties. We consider both the preemption-restart and the preemption-resume models, and give new or improved lower bounds on the competitive ratio of deterministic online algorithms. In many cases the bounds are optimal when the job deadlines are tight. Our results show that the competitiveness varies linearly with the penalty factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 4, 31 October 2008, Pages 214-218