Consider the optimal control problem for the two processor flow-shop when processing time is a (linear) function of the state. Since the latter also depends on the sequence, a hierarchical approach is proposed. In Wagneur , the problem of optimally lounching n parts is solved for an arbitrary sequence. In Sriskandarajah and Wagneur , the sequencing problem is shown to be NP-hard in the strong sense, even with only two processors. Inspired by this complexity result, as well as by the formulas of , we devise here a branch-and-bound algorithm and a polynomial heuristique for the sequencing problem associated to the minimum makespan. The performances of these algorithms are then analyzed and compared.
Paru en mai 1988 , 16 pages
Ce cahier a été révisé en octobre 1989