Paper Info
Title
A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
Abstract
We consider the online scheduling on two identical parallel machines with chain precedence constraints to minimize makespan, where jobs arrive over time and have identical processing times. For this online scheduling problem, Huo and Leung [Y. Huo and J.Y.-T. Leung, Online scheduling of precedence constrained tasks, SIAM Journal on Computing, 34 (2005), 743-762] proved that it is impossible to have an online algorithm of a competitive ratio 1. We provide a best possible online algorithm of competitive ratio 13-12.
Year
DOI
Venue
2012
10.1016/j.tcs.2012.07.009
Theor. Comput. Sci.
Keywords
DocType
Volume
equal-length job,identical processing time,possible online algorithm,Y. Huo,online algorithm,competitive ratio,identical parallel machine,T. Leung,online scheduling,online scheduling problem,chain precedence constraint
Journal
457,
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
8
3
Name
Order
Citations
PageRank
Junling Yuan1166.52
Wenhua Li2506.33
Jinjiang Yuan366269.52