Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart

作者：Liu Hailing; Yuan Jinjiang^*

来源：Theoretical Computer Science, 2014, 543: 24-36.

DOI：10.1016/j.tcs.2014.05.021

• Online scheduling
• Restart
• Limited restart
• Unit length jobs
• Restricted batch

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 alpha approximate to 0.29, beta approximate to 0.47, gamma approximate to 0.38, and phi approximate to 0.40 be four parameters defined in the text. When b = 2, we present a best possible online algorithm H-L,(b = 2) with a competitive ratio of 1 + alpha under the assumption of restart or limited restart. Under the assumption of limited restart with b >= 3, we present a best possible online algorithm H-L(b >= 3) with a competitive ratio of 1 + beta. Under the assumption of restart, when b = 3, we present a best possible online algorithm H(b = 3) with a competitive ratio of 1 + gamma, and when b >= 4, we present a best possible online algorithm H(b >= 4) with a competitive ratio of 1 + phi. 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.

• 出版日期2014-7-10
• 单位河南工程学院; 郑州大学