AN EXACT METHOD FOR SOLVING THE MULTI-PROCESSOR FLOW-SHOP

Issue		RAIRO Oper. Res. Volume 34, Number 1, January-March 2000


Page(s)		1 - 25
DOI		10.1051/ro:2000103

DOI: 10.1051/ro:2000103

RAIRO Rech. Opér. (vol. 34, n $^\circ$ 1, 2000, pp. 1-25)

AN EXACT METHOD FOR SOLVING THE MULTI-PROCESSOR FLOW-SHOP

Jacques CARLIER and Emmanuel NERON

Received February 1998

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

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.

Keywords: Branch and bound, multi-processor flow-shop, m-machine problems, inputs and selection.

Contents

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.