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


Hierarchical Control of the Two Processor Flow-Shop with State Dependent Processing Times: 3. Exact and Heuristic Algorithms


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 [10], the problem of optimally lounching n parts is solved for an arbitrary sequence. In Sriskandarajah and Wagneur [9], 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 [10], 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.

, 16 pages

Ce cahier a été révisé en octobre 1989