A note on single-machine makespan scheduling with deteriorating jobs and scheduled maintenance

A single-machine scheduling problem with simple linear deteriorating jobs is considered in this paper. The objective is to minimize the makespan when the machine is not always available. We study the scheduling problem under a deterministic environment; specifically, the availability periods are known in advance and jobs are non-resumable. It is shown that the problem is NP-hard even with a single maintenance period. Thus, the 0–1 integer programming technique is utilized to solve the simple linear deterioration model.