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

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.


90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI Numdam EuDML