Semi-online scheduling on a single machine with unexpected breakdown

In this paper, we consider a single machine scheduling problem where a breakdown period occurs in an online way. Two main objective functions are studied: the makespan and the maximum lateness. We propose two approximation algorithms for the makespan minimization for solving two variants of the problem: with different release dates or without release dates. We show that the competitive ratio of the two algorithms is 3/2 and that this bound is the best possible for the makespan minimization. For the maximum lateness minimization we propose a (1+2/2)≈1.70-approximation algorithm capable to solve the problem with delivery times but no release dates. This ratio is tight for the proposed algorithm and allows us to establish a precise window for the best possible ratio, which belongs to [3/2,1+2/2]≈[1.50,1.70].