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

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.