An exact method for solving the multi-processor flow-shop. (English) Zbl 0963.90027

Carlier, Jacques; Néron, Emmanuel

RAIRO, Oper. Res. 34, No. 1, 1-25 (2000).

Summary: The aim of this paper is to present a new branch and bound method for solving the multi-processor flow-shop. This method is based on the relaxation of the initial problem to \(m\)-machine problems corresponding to centers. Release dates and tails are associated with operations and machines. The branching scheme consists in fixing the inputs of a critical center and the lower bounds are those of the \(m\)-machine problem. Several techniques for adjusting release dates and tails have also been introduced. As shown by our personal study, the overall method is very efficient.

MSC:

90B35	Deterministic scheduling theory in operations research
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

multi-processor flow-shop; inputs and selection; \(m\)-machine problems; branch and bound method