The two‐machine permutation flow shop with state‐dependent processing times Academic Article uri icon

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

author list (cited authors)

  • Wagneur, E., & Sriskandarajah, C.

citation count

  • 18

complete list of authors

  • Wagneur, E||Sriskandarajah, C

publication date

  • August 1993

publisher