A Flexible On-line Scheduling Algorithm for Batch Machine with Infinite Capacity

Authors :: Chung Keung Poon
Wenci Yu
Source :: Annals of Operations Research. 133:175-181
Publication Year :: 2005
Publisher :: Springer Science and Business Media LLC, 2005.
Abstract: We study on-line scheduling on a batch machine with infinite capacity. We present a flexible on-line scheduling algorithm that aims at minimizing the makespan and achieves the optimal competitive ratio of $(1+\sqrt{5})/2$ .

Subjects :: TheoryofComputation_MISCELLANEOUS
Rate-monotonic scheduling
Mathematical optimization
Competitive analysis
I/O scheduling
Job shop scheduling
Computer science
Distributed computing
General Decision Sciences
Flow shop scheduling
Dynamic priority scheduling
Management Science and Operations Research
Round-robin scheduling
Fair-share scheduling
Scheduling (computing)
Computer Science::Operating Systems

Full Text Access

Tools