کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420532 683952 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online scheduling with general machine cost functions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Online scheduling with general machine cost functions
چکیده انگلیسی

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently online scheduling problems have been investigated with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. In all of these models the assumption has been made that each machine has unit cost. In this paper we consider the problem with general machine cost functions. Furthermore we also consider a more general version of the problem where the available machines have speed, the algorithm may purchase machines with speed 1 and machines with speed ss. We define and analyze some algorithms for the solution of these problems and their special cases. Moreover we prove some lower bounds on the possible competitive ratios.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 9, 6 May 2009, Pages 2070–2077
نویسندگان
,