The twomachine permutation flow shop with statedependent processing times Academic Article uri icon


  • 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 NPhard 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 branchandbound 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. Copyright 1993 Wiley Periodicals, Inc., A Wiley Company

published proceedings

  • Naval Research Logistics

author list (cited authors)

  • Wagneur, E., & Sriskandarajah, C.

citation count

  • 17

complete list of authors

  • Wagneur, E||Sriskandarajah, C

publication date

  • August 1993