Affordable Access

Publisher Website

Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
410
Identifiers
DOI: 10.1016/j.tcs.2009.07.056
Keywords
  • Online Scheduling
  • Deadline
  • Lookahead
  • Parallel Batch
Disciplines
  • Computer Science

Abstract

Abstract This paper studies online scheduling of unit length jobs on a parallel batching machine with the help of lookahead. The objective is to maximize the number of early jobs. Denote by b the size of each batch with b = ∞ in the unbounded batching and b < ∞ in the bounded batching. In the L K L lookahead model, at a time instant t , an online algorithm can foresee all jobs that will arrive in the time segment ( t , t + L ) . When 0 ≤ L < 1 , we show that a simple greedy online algorithm (independent of the value of L ) has a best possible competitive ratio of 1 / min { n , b + 1 } , where n is the number of jobs. This means that lookahead is useless when 0 ≤ L < 1 . When 1 ≤ L < 2 , we establish the upper bounds 0.39 (for b = ∞ ) and 2 / 3 (for b < ∞ ) of competitive ratios, and provide an online algorithm of competitive ratios 1 / 4 (for b = ∞ ) and 1 / 5 (for b < ∞ ).

There are no comments yet on this publication. Be the first to share your thoughts.