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

作者：Zhao Chuanli^*; Tang Hengyong

来源：Optimization Letters, 2011, 5(1): 183-190.

DOI：10.1007/s11590-010-0202-1

• Scheduling
• Flow shop
• Deteriorating jobs
• Makespan

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.

• 出版日期2011-2
• 单位沈阳师范大学