Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10347491 | Computers & Operations Research | 2013 | 12 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Feifeng Zheng, Yongxi Cheng, Ming Liu, Yinfeng Xu,