Article ID: | iaor20125424 |
Volume: | 40 |
Issue: | 1 |
Start Page Number: | 180 |
End Page Number: | 191 |
Publication Date: | Jan 2013 |
Journal: | Computers and Operations Research |
Authors: | Xu Yinfeng, Liu Ming, Zheng Feifeng, Cheng Yongxi |
Keywords: | combinatorial optimization, manufacturing industries, heuristics |
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