کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10347491 | 699240 | 2013 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Online interval scheduling on a single machine with finite lookahead
ترجمه فارسی عنوان
برنامه ریزی فاصله آنلاین بر روی یک دستگاه با چشم انداز محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We study an online weighted interval scheduling problem on a single machine, where all intervals have unit length and the objective is to maximize the total weight of all completed intervals. We investigate how the function of finite lookahead improves the competitivities of deterministic online heuristics, under both preemptive and non-preemptive models. The lookahead model studied in this paper is that an online heuristic is said to have a lookahead ability of LD if at any time point it is able to foresee all the intervals to be released within the next LD units of time. We investigate both competitive online heuristics and lower bounds on the competitive ratio, with lookahead 0â¤LDâ¤1 under the preemptive model, and lookahead 0â¤LDâ¤2 under the non-preemptive model. A method to transform a preemptive lookahead online algorithm to a non-preemptive online algorithm with enhanced lookahead ability is also given. Computational tests are performed to compare the practical competitivities of the online heuristics with different lookahead abilities.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 1, January 2013, Pages 180-191
Journal: Computers & Operations Research - Volume 40, Issue 1, January 2013, Pages 180-191
نویسندگان
Feifeng Zheng, Yongxi Cheng, Ming Liu, Yinfeng Xu,