| Abstract: | 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 [10]. Restricting to the case of permutation schedules, we 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. We 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. Our numerical results confirm our preliminary study [10] that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory [7]. © 1993 John Wiley & Sons, Inc. |
