Méthode heuristique pour le problème de flow shop hybride avec machines dédiées

¹ Unité de recherche OASIS, ENIT, B.P. 37, Le belvédère 100, Tunis, Tunisie; najoua.dridi@enit.rnu.tn
² Unité de Recherche URAII, INSAT-TUNIS, Centre Urbain Nord B.P. No. 676, 1080 Tunis Cedex, Tunisie; hatem.hadda@esti.rnu.tn sonia.gabouj@insat.rnu.tn

Reçu : 26 Janvier 2008
Accepté : 17 Juin 2009

Résumé

Dans ce papier, nous traitons le problème de minimisation du makespan dans un flow shop hybride à deux étages avec machines dédiées. En premier lieu, nous présentons des propriétés de base, un ensemble de bornes inférieures et deux cas polynomiaux. En second lieu, nous proposons une nouvelle heuristique qui exploite ces propriétés, et cherche à placer les jobs, en tenant compte pour chaque instance du problème, de la valeur de la borne inférieure. La dernière partie de ce travail présente les résultats expérimentaux d'une étude comparative avec une heuristique de la littérature. L'analyse de ces résultats permet d'apprécier la qualité de notre proposition.

Abstract

In this paper we deal with the two-stage hybrid flow shop with dedicated machines. The objective is to minimize the makespan. We first provide some basic properties, a set of lower bounds and two polynomial cases. We then propose a new heuristic based on the established properties. The heuristic tries to sequence jobs in such a way that the obtained makespan corresponds to the lower bound. In the last part, we present the results of a computational experience comparing our heuristic with another heuristic found in the literature. The analysis of those results allows us to appreciate the quality of our proposition.