کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428583 686825 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead
چکیده انگلیسی

We consider online scheduling of unit length jobs on m parallel-batch machines with lookahead to minimize makespan. A parallel-batch machine can handle up to b jobs simultaneously as a batch with processing time equal to the maximum processing time of the jobs included in the batch. In the lookahead model, at a time instant t  , an online algorithm can foresee all the jobs that will arrive in the time segment (t,t+β](t,t+β]. In this paper, we deal with two variants: the unbounded model with b=∞b=∞ and the bounded model with b<∞b<∞. For the unbounded model, we present an optimal online algorithm for β⩾1/mβ⩾1/m, and provide a best possible online algorithm of competitive ratio 1+αm1+αm for 0⩽β<1/m0⩽β<1/m, where αmαm is the positive root of (1+α)(m+1)=α+2−β∑i=1m(1+α)i. For the bounded model, we establish a lower bound with a form of piecewise function, and provide an online algorithm with competitive ratios 1+α⁎1+α⁎ for 0⩽β⩽16 and 32 for β>16, respectively, where α⁎α⁎ is the positive root of α2+(β+1)α+β−1=0α2+(β+1)α+β−1=0. The online algorithm is the best possible when 0⩽β⩽16.


► For unbounded model, we present an optimal online algorithm for β⩾1/mβ⩾1/m.
► We provide a best possible online algorithm for 0⩽β<1/m0⩽β<1/m.
► For bounded model, we establish a lower bound with a form of piecewise function.
► We provide a best possible online algorithm for 0⩽β⩽1/60⩽β⩽1/6.
► The algorithm is 3/2-competitive for β>1/6β>1/6.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 7, 31 March 2012, Pages 292–297
نویسندگان
, , ,