An Exact Method for Solving the Multi-Processor Flow-Shop

UMR CNRS 6599 HEUDIASYC, Centre de Recherches de Royallieu, Université de Technologie de Compiègne, 60205 Compiègne Cedex, France.

Received: February 1998

Abstract

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.

Résumé

Nous presentons dans cet article, une nouvelle méthode arborescente pour la résolution du flowshop hybride. Cette méthode est basée sur des relaxations du problème à l'un de ses centres. Des dates de disponibilité et des durées de latence sont associées aux opérations et aux machines. Le schéma de branchement impose une suite d'entrées successives pour le centre critique. Les évaluations par defaut utilisées sont celles du problème à m machines. Des méthodes d'ajustement sur les dates de disponibilité et les durées de latence sont également presentées. La méthode arborescente ainsi construite s'est revelée être efficace comme le montrent nos résultats experimentaux.