Maximum lateness minimization with positive tails on a single machine with an unexpected non-availability interval

摘要

In this paper, we consider the single machine scheduling problem with an unexpected non-availability interval. The objective is to minimize the maximum lateness. We have to decide the scheduling of jobs without any knowledge of the machine non-availability interval. Hence, we consider two possible models related to this constraint: breakdown model and emergent-job model. In both cases, the starting time of the non-availability interval and the length of the interval are unknown. We show that no equation-competitive online algorithm exists for the breakdown model and no equation-competitive online algorithm exists for the emergent model and we show the Jackson's rule can give a 2-approximation for the two models and this ratio is tight.