A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints

This paper is concerned with two-machine no-wait flow shop scheduling problems in which the actual processing time of each job is a proportional function of its starting time and each machine may have non-availability intervals. The objective is to minimize the makespan. We assume that the non-availability intervals are imposed on only one machine. Moreover, the number of non-availability intervals, the start time and end time of each interval are known in advance. We show that the problem with a single non-availability interval is NP-hard in the ordinary sense and the problem with an arbitrary number of non-availability intervals is NP-hard in the strong sense.