کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876160 | 690239 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart](/preview/png/6876160.png)
چکیده انگلیسی
We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with a capacity b to minimize makespan with restart or limited restart. Let αâ0.29, βâ0.47, γâ0.38, and Ïâ0.40 be four parameters defined in the text. When b=2, we present a best possible online algorithm HL(b=2) with a competitive ratio of 1+α under the assumption of restart or limited restart. Under the assumption of limited restart with bâ¥3, we present a best possible online algorithm HL(bâ¥3) with a competitive ratio of 1+β. Under the assumption of restart, when b=3, we present a best possible online algorithm H(b=3) with a competitive ratio of 1+γ, and when bâ¥4, we present a best possible online algorithm H(bâ¥4) with a competitive ratio of 1+Ï. In our online algorithms under the assumption of restart, each job is interrupted at most two times. Consequently, our results cover the setting of k-limited restart for all kâ¥1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 24-36
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 24-36
نویسندگان
Hailing Liu, Jinjiang Yuan,