Optimal scheduling of the 3-machine assembly-type flow shop

Issue		RAIRO Oper. Res. Volume 33, Number 4, October-December 1999


Page(s)		439 - 445
DOI		10.1051/ro:1999120

DOI: 10.1051/ro:1999120

RAIRO Rech. Opér. (vol. 33, n $^\circ$ 4, 1999, pp. 439-445)

Optimal scheduling of the 3-machine assembly-type flow shop

Mohamed Haouari¹ and Thouraya Daouas²

¹Ecole Polytechnique de Tunisie, BP. 743, 2078 La Marsa, Tunisia.
²Institut des Hautes Etudes Commerciales, 2016 CarthagePresidence, Tunisia.

Abstract:

We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strong sense. We propose an exact branch and bound method based on a recursive enumeration of potential inputs and outputs of the machines. Using this algorithm, several large size instances have been solved to optimality.

Résumé:

Nous nous interessons au probleme d'ordonnancement de 3 machines dans un atelier d'assemblage de type flowshop. Ce probleme est connu comme etant NP-complet au sens fort. Nous proposons un algorithme exact de separation et evaluation progressives, base sur une enumeration recursive des entrees et des sorties potentielles des machines. Des problemes de grande taille ont ete resolus d'une maniere optimale. À notre connaissance, il s'agit de la premiere fois, ou ce probleme est resolu exactement.

Keywords: Scheduling, flow shop, branch and bound, assembly-type production.

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.