An optimal semi‐online algorithm for 2‐machine scheduling with an availability constraint

This paper considers a problem of semi‐online scheduling jobs on two identical parallel machines with objective to minimize the makespan. We assume there is an unavailable period [B,F] on one machine and the largest job processing time P max is known in advance. After comparing B with P max we consider three cases, and we show a lower bound of the problem are 3/2, 4/3 and $(\sqrt{5}+1)/2$ , respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.