Online interval scheduling on a single machine with finite lookahead

Online interval scheduling on a single machine with finite lookahead

0.00 Avg rating0 Votes
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: , , ,
Keywords: combinatorial optimization, manufacturing industries, heuristics
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 equ1 under the preemptive model, and lookahead 0 = LD = 2 equ2 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.

Reviews

Required fields are marked *. Your email address will not be published.