Groupe d’études et de recherche en analyse des décisions

G-92-08

The Two-machine Permutation Flow Shop with State Dependent Processing Times

et

If the processing time of each job in a flow-shop also depends on waiting time (or on the time spent prior to processing), then the choice of a sequence influences processing times. This non standard 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 (Sriskandarajah and Wagneur, 1991). 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 (1991) that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory (1964).

, 25 pages