THE 2-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 influenc es processing times. This nonstandard scheduling problem is studied he re 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 m ain features of the general case [10]. Restricting to the case of perm utation schedules, we first determine the optimal release times of the jobs for a given sequence. Permutation schedules are evaluated for th is optimal policy, and the scheduling problem is solved using branch-a nd-bound techniques. We also show the surprising result that the optim al schedule may not be a permutation schedule. Numerical results on ra ndomly generated data are provided for permutation schedules. Our nume rical results confirm our preliminary study [10] that fairly good appr oximate solutions can efficiently be obtained in the case of limited c omputing time using the heuristics due to Gilmore and Gomory [7]. (C) 1993 John Wiley & Sons, Inc.