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.