Paper Info
Title
Online interval scheduling on a single machine with finite lookahead
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.
Year
DOI
Venue
2013
10.1016/j.cor.2012.06.003
Computers & OR
Keywords
DocType
Volume
finite lookahead,non-preemptive online algorithm,competitive online heuristics,deterministic online heuristics,single machine,preemptive lookahead online algorithm,different lookahead ability,non-preemptive model,lookahead model,enhanced lookahead ability,lookahead ability,Online interval scheduling
Journal
40
Issue
ISSN
Citations 
1
0305-0548
7
PageRank 
References 
Authors
0.77
10
4
Name
Order
Citations
PageRank
Feifeng Zheng121442.51
Yongxi Cheng212515.23
Ming Liu313830.45
Yinfeng Xu41636108.18