کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10347491 699240 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online interval scheduling on a single machine with finite lookahead
ترجمه فارسی عنوان
برنامه ریزی فاصله آنلاین بر روی یک دستگاه با چشم انداز محدود
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
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
نویسندگان
, , , ,