The two-machine permutation flow shop with state-dependent processing times

If the processing time of each job in a flow shop also depends on the time spent prior to processing, then the choice of a sequence influences processing times. This nonstandard scheduling problem is studied here for the minimum makespan schedule in a flow shop with two machines. The problem is NP-hard in the strong sense and already contains the main features of the general case. Restricting to the case of permutation schedules, the authors first determine the optimal release times of the jobs for a given sequence. Permutation schedules are evaluated for this optimal policy, and the scheduling problem is solved using branch-and-bound techniques. The authors also show the surprising result that the optimal schedule may not be a permutation schedule. Numerical results on randomly generated data are provided for permutation schedules. The present numerical results confirm the preliminary study that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory.