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 3/2, 4/3 and (root 5 + 1)/2, respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.