Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876160 | Theoretical Computer Science | 2014 | 13 Pages |
Abstract
We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with a capacity b to minimize makespan with restart or limited restart. Let αâ0.29, βâ0.47, γâ0.38, and Ïâ0.40 be four parameters defined in the text. When b=2, we present a best possible online algorithm HL(b=2) with a competitive ratio of 1+α under the assumption of restart or limited restart. Under the assumption of limited restart with bâ¥3, we present a best possible online algorithm HL(bâ¥3) with a competitive ratio of 1+β. Under the assumption of restart, when b=3, we present a best possible online algorithm H(b=3) with a competitive ratio of 1+γ, and when bâ¥4, we present a best possible online algorithm H(bâ¥4) with a competitive ratio of 1+Ï. In our online algorithms under the assumption of restart, each job is interrupted at most two times. Consequently, our results cover the setting of k-limited restart for all kâ¥1.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hailing Liu, Jinjiang Yuan,