Scheduling the maintenance on a single machine

This paper considers a single machine scheduling problem with preventive ma intenance. In many cases, a machine must be maintained after it continuousl y works for a period of time. But most papa in the literature ignore non-av ailability of the machine. For this reason, this paper studies the problem of scheduling processing of jobs and maintenance of machine simultaneously. The objective is to minimise total completion time of jobs. The problem is proved to be NP-hard in the strong sense. Three heuristic algorithms and a branch and bound algorithm are proposed. Computational experiments are don e to evaluate the effectiveness of the algorithms.