کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655161 | 684032 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper investigates the semi-online version of scheduling problem P||Cmax on a three-machine system. We assume that all jobs have their processing times between p and rp (p>0,r⩾1). We give a comprehensive competitive ratio of LS algorithm which is a piecewise function on r⩾1. It shows that LS is an optimal semi-online algorithm for every râ[1,1.5], [3,2] and [6,+â). We further present an optimal algorithm for every râ[2,2.5], and an almost optimal algorithm for every râ(2.5,3] where the largest gap between its competitive ratio and the lower bound of the problem is at most 0.01417. We also present an improved algorithm with smaller competitive ratio than that of LS for every râ(3,6).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 150, Issues 1â3, 1 September 2005, Pages 140-159
Journal: Discrete Applied Mathematics - Volume 150, Issues 1â3, 1 September 2005, Pages 140-159
نویسندگان
Yong He, György Dósa,