l’ordonnancement d’ateliers job-shop flexibles

N d'ordre : 98 COLE CENTRALE DE LILLE

UNIVERSIT DE TUNIS EL MANAR

COLE NATIONALE DINGNIEURS DE TUNIS

Thse en cotutelle prpare au Laboratoire dAutomatique, Gnie Informatique et Signal de lEcole Centrale de Lille et lUnit de Recherche LARA Automatique

de lEcole Nationale dIngnieurs de Tunis

THSE

prsente en vue dobtenir le grade de

DOCTEUR

en Automatique et Informatique Industrielle

par

Hela BOUKEF BEN OTHMAN

Doctorat dlivr conjointement par lcole Centrale de Lille et lcole Nationale dIngnieurs de Tunis

Sur lordonnancement dateliers job-shop flexibles et flow-shop en industries pharmaceutiques

Optimisation par algorithmes gntiques et essaims particulaires

soutenue le 3 Juillet 2009, devant le jury dexamen compos de :

MM. Noureddine ELLOUZE Prsident Abdellah EL MOUDNI Rapporteur Noureddine LIOUANE Rapporteur Imed KACEM Examinateur Mohamed BENREJEB Co-Directeur de Thse Pierre BORNE Directeur de Thse

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Avant propos

2

Avant Propos

Ce prsent travail a t effectu au sein de lUnit de Recherche LARA Automatique de

lEcole Nationale dIngnieurs de Tunis (ENIT) et du Laboratoire dAutomatique, Gnie

Informatique et Signal (LAGIS) de lEcole Centrale de Lille (EC-Lille).

Nous sommes particulirement sensibles au grand honneur que Monsieur le Professeur

Noureddine ELLOUZE, Directeur de lUnit de Recherche LSTS de lEcole Nationale

dIngnieurs de Tunis, nous fait en acceptant de prsider notre Jury dExamen. Quil trouve

ici lexpression de notre profonde reconnaissance.

Cest un agrable devoir pour nous dexprimer notre trs vive reconnaissance Monsieur le

Professeur Mohamed BENREJEB, Directeur de lUnit de Recherche LA.R.A. Automatique,

et Monsieur Pierre BORNE, Professeur lEcole Centrale de Lille pour nous avoir guid

durant toute llaboration de ce mmoire avec le srieux et la comptence qui les

caractrisent. Quils trouvent ici le tmoignage de notre trs profonde gratitude.

Nous tenons remercier vivement Monsieur Abdellah EL MOUDNI, Professeur

lUniversit de Technologie Belfort-Monbliard et Monsieur Noureddine LIOUANE, Matre

de Confrences lInstitut Suprieur des Sciences Appliques et Technologies de Gafsa et

Directeur de lInstitut Suprieur des Sciences Appliques et Technologies de Kairouan,

davoir bien voulus accept de rapporter sur notre travail. Quils trouvent ici, le tmoignage

de notre profonde reconnaissance.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Avant Propos

3

Nos remerciements sadressent galement Monsieur Imed KACEM, Professeur

lUniversit Paul Verlaine-Metz; pour lintrt quil a bien voulu porter nos travaux en

acceptant de participer notre Jury dExamen.

Nous tenons, enfin remercier tous les chercheurs de lUnit de Recherche LARA

Automatique de lENIT et du Laboratoire dAutomatique, Gnie Informatique et Signal de

lEC-Lille pour leur amicale prsence et la sympathie quils nous ont constamment

tmoignes. Nous leur exprimons, ici, toute notre gratitude.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Table des Matires

4

Table des Matires

Avant Propos ................................................................................................................... 2

Table des Matires .......................................................................................................... 4

Table des Figures............................................................................................................. 8

Liste des Tableaux......................................................................................................... 10

Introduction gnrale.................................................................................................... 11

Chapitre I - Ordonnancement : spcificits, ateliers, mthodes et

complexit............................................................................. 14

I.1 - Introduction ........................................................................................................... 14

I.2 - Gnralits sur lordonnancement....................................................................... 15

I.3 - Formulation dun problme dordonnancement................................................ 16

I.3.1 - Les tches ................................................................................................. 16

I.3.2 - Les ressources .......................................................................................... 17

I.3.3 - Les contraintes......................................................................................... 17

I.3.4 - Les critres ............................................................................................... 18

I.4 - Les ateliers.............................................................................................................. 19

I.4.1 - Les ateliers de type flow-shop................................................................. 19

I.4.2 - Les ateliers de type job-shop .................................................................. 19

I.4.3 - Les ateliers de type open-shop................................................................ 19

I.5 - Reprsentation des problmes dordonnancement ............................................ 20

I.5.1 - Le diagramme de Gantt .......................................................................... 20

I.5.2 - Graphe Potentiel-Tches ........................................................................ 21

I.5.3 - Mthode PERT ........................................................................................ 22

I.6 - Complexit des problmes dordonnancement................................................... 23

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Table des Matires

5

I.7 - Mthodes doptimisation ...................................................................................... 25

I.7.1 - Les mthodes exactes............................................................................... 25

a - La mthode Branch and Bound............................................................... 25

b - La programmation dynamique ............................................................... 26

c - La programmation linaire ...................................................................... 26

d - Les heuristiques ........................................................................................ 26

I.7.2 - Les mthodes approches ou mtaheuristiques.................................... 27

a - Les mthodes bases sur la recherche locale .......................................... 27

b - Les algorithmes volutionnistes : algorithmes gntiques .................... 33

I.8 - Position du problme............................................................................................. 38

I.9 - Conclusion.............................................................................................................. 38

Chapitre II - Algorithmes gntiques pour la rsolution de problmes

dordonnancement en industries pharmaceutiques........ 40

II.1 - Introduction.......................................................................................................... 40

II.2 - Ordonnancement en industries pharmaceutiques ............................................ 41

II.2.1 - Types de produits utiliss dans les industries pharmaceutiques ....... 41

II.2.2 - Cheminement des produits au niveau des industries

Pharmaceutiques 42

II.2.3 - Spcificits dun atelier de conditionnement....................................... 42

II.2.4 - Lignes de conditionnement ................................................................... 43

II.2.5 - Problmes survenant dans un atelier de conditionnement ................ 44

II.3 - Problmes dordonnancement de type flow-shop ............................................. 45

II.3.1 - Prsentation des ateliers de type flow-shop......................................... 45

II.3.2 - Ordonnancement dateliers de type flow-shop ................................... 46

II.4 - Optimisation mono-objectif / Optimisation multi-objectifs............................. 46

II.4.1 - Optimisation mono-objectif .................................................................. 46

II.4.2 - Optimisation multi-objectifs ................................................................. 47

II.5 - Rsolution dun problme dordonnancement en industries

pharmaceutiques par les algorithmes gntiques........................................ 48

II.5.1 - Prsentation du problme ..................................................................... 48

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Table des Matires

6

II.5.2 - Formulation du problme ..................................................................... 49

a - Notations .................................................................................................... 49

b - Critres minimiser ................................................................................. 50

c - Fonction fitness optimiser...................................................................... 50

II.5.3 - Algorithmes gntiques ......................................................................... 51

a - Prsentation des algorithmes gntiques ................................................ 51

b - Fonctionnement dun algorithme gntique .......................................... 52

c - Codage des algorithmes gntiques ......................................................... 52

d - Oprateurs des algorithmes gntiques .................................................. 53

II.5.4 - Codage CLOS propos .......................................................................... 54

II.5.5 - Oprateurs proposs.............................................................................. 55

a - Oprateur de slection.............................................................................. 55

b - Oprateur de croisement.......................................................................... 56

c - Oprateur de mutation ............................................................................. 58

II.5.6 - Algorithme propos ............................................................................... 58

II.6 - Simulation et rsultats ......................................................................................... 60

II.6.1 - Exemple de 16 produits traits sur 2 lignes de conditionnement ...... 61

II.6.2 - Exemple de 30 produits traits sur 2 lignes de conditionnement ...... 63

II.7 - Conclusion ............................................................................................................ 65

Chapitre III - Rsolution de problmes dordonnancement job-shop

flexible par la mthode base sur loptimisation par

essaim particulaire............................................................. 66

III.1 - Introduction ........................................................................................................ 66

III.2 - Problmes dordonnancement de type job-shop flexible (FJSP) ................... 67

III.2.1 - Prsentation des problmes FJSP....................................................... 68

III.2.2 - Formulation des problmes FJSP....................................................... 68

III.3 - Optimisation par essaim particulaire (OEP) ................................................... 69

III.3.1 - Prsentation de la mthode OEP ........................................................ 69

III.3.2 - Optimisation par essaim particulaire dans le cas continu................ 69

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Table des Matires

7

III.3.3 - Optimisation par essaim particulaire dans le cas discret ................. 70

a - Formulation gnrale des problmes dordonnancement FJSP par

essaim particulaire .................................................................................... 70

b - Prsentation de la structure dune particule.......................................... 71

III.3.4 - Algorithme Bas sur la mthode dOptimisation par Essaim

Particulaire pour le cas discret (BOEP)............................................. 72

a - Etapes de lalgorithme BOEP propos ................................................... 72

b - Algorithme BOEP propos ...................................................................... 73

III.4 - Elaboration dun ordonnancement dateliers de type job-shop flexible par la

mthode base sur lessaim particulaire minimisant le Makespan ............... 75

III.4.1 - Prsentation des cas dateliers tudis ............................................... 75

III.4.2 - Rsultats de mise en uvre de la mthode BOEP............................. 77

III.4.3 - Influence du choix des coefficients , et sur les rsultats

obtenus................................................................................................... 81

III.4.4 - Influence de la modification du voisinage sur les rsultats obtenus 83

III.4.5 - Comparaison des rsultats avec ceux obtenus par les algorithmes

gntiques.............................................................................................. 86

III.5 - Comparaison de lefficacit des AG et de la mthode BOEP pour la

rsolution de problmes flow-shop en industries pharmaceutiques.............. 87

III.5.1 - Efficacit de la mthode BOEP Position du problme................... 87

III.5.2 - Rsultats de lapplication de lalgorithme BOEP.............................. 88

III.6 - Conclusion........................................................................................................... 92

Conclusion gnrale................................................................................... 93

Bibliographie.............................................................................................. 96

Annexe ...................................................................................................... 104

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Table des Figures

8

Table des Figures

Figure 1. 1 - Classification des types dateliers ....................................................................... 20

Figure 1. 2 - Diagramme de Gantt dun ordonnancement........................................................ 21

Figure 1. 3 - Graphe Potentiel-Tches d'un ordonnancement .................................................. 22

Figure 1. 4 - Exploration de lespace de recherche dans la mthode de recherche locale ....... 28

Figure 1. 5 - Algorithme relatif au fonctionnement gnral du recuit simul.......................... 30

Figure 1. 6 - Algorithme relatif au fonctionnement gnral de la mthode de recherche

tabou .................................................................................................................... 32

Figure 1. 7 - Fonctionnement gnral dun algorithme gntique ........................................... 35

Figure 1. 8 - Dplacement des fourmis vers une source de nourriture..................................... 36

Figure 1. 9 - Dplacement des fourmis aprs placement d'un obstacle sur leur chemin.......... 36

Figure 1. 10 - Choix du chemin le plus court par la plupart des fourmis................................. 37

Figure 2. 1 - Machines composant une ligne de conditionnement........................................... 44

Figure 2. 2 - Cheminement des produits dans un atelier de type flow-shop ............................ 45

Figure 2. 3 - Types de minima ................................................................................................. 47

Figure 2. 4 - Fonctionnement de loprateur de croisement .................................................... 53

Figure 2. 5 - Fonctionnement de loprateur de mutation........................................................ 54

Figure 2. 6 - Placement des chromosomes sur la roulette la roulette....................................... 56

Figure 2. 7 - Lancement dune bille sur la roulette .................................................................. 56

Figure 2. 8 - Arrt de la bille sur un chromosome, ici, sur celui ayant la meilleure fitness..... 56

Figure 2. 9 - Fonctionnement de l'oprateur de croisement un point .................................... 57

Figure 2. 10 - Fonctionnement de l'oprateur de croisement deux points............................. 57

Figure 2. 11 - Fonctionnement de l'oprateur de mutation un point ..................................... 58

Figure 2. 12 - Fonctionnement de l'oprateur de mutation deux points propos .................. 58

Figure 2. 13 - Etapes de mise en uvre de lalgorithme gntique propos............................ 60

Figure 2. 14 - Evolution des cots travers les gnrations pour le problme

dordonnancement 16x2 en industries pharmaceutiques .................................. 62

Figure 2. 15 - Diagramme de Gantt relatif au meilleur individu pour le problme 16 x 2

utilisant les algorithmes gntiques................................................................... 62

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Table des Figures

9



Figure 2. 17 - Diagramme de Gantt relatif au meilleur individu pour le problme 30 x 2

utilisant les algorithmes gntiques.................................................................. 65

Figure 3. 1 - Etapes relatives lvolution de lalgorithme BOEP.......................................... 73

Figure 3. 2 - Evolution du Cmax travers les gnrations pour un problme FJSP 20x5....... 78

Figure 3. 3 - Diagramme de Gantt de la meilleure solution pour le problme 20x5................ 78

Figure 3. 4 - Evolution du Cmax travers les gnrations pour un problme FJSP 10x6....... 79

Figure 3. 5 - Diagramme de Gantt de la meilleure solution pour le problme 10x6................ 79

Figure 3. 6 - Evolution du Cmax travers les gnrations pour un problme FJSP 3x5......... 80

Figure 3. 7 - Diagramme de Gantt de la meilleure solution pour le problme 3x5.................. 80

Figure 3. 8 - Evolution du Cmax travers les gnrations pour un problme FJSP 20x5

pour un choix alatoire des coefficients , et ................................................ 81


pour un choix alatoire des coefficients , et ................................................ 82


pour un choix alatoire des coefficients , et .............................................. 82


pour un voisinage de 10 particules.................................................................... 84







Figure 3. 15 - Diagramme de Gantt relatif au meilleur individu pour le problme 16 x 2 par

application de la mthode BOEP ...................................................................... 90



Figure 3. 17 - Diagramme de Gantt relatif au meilleur individu pour le problme 30 x 2 par

application de la mthode BOEP ...................................................................... 91

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Liste des tableaux

10

Liste des Tableaux

Tableau 1. 1 - Donnes utilises pour la ralisation dun graphe potentiel-tches .................. 21

Tableau 2. 1 - Codage CLOS pour n lignes et m produits pour un individu i donn............... 55

Tableau 2. 2 - Donnes relatives un problme dordonnancement 16x2 en industries

pharmaceutiques................................................................................................ 61

Tableau 2. 3 - Donnes relatives un problme dordonnancement 30x2 en industries

pharmaceutiques................................................................................................ 63

Tableau 3.1- Exemple de structure dune particule................................................................. 72

Tableau 3.2 - Benchmark 20x5 relatif un problme dordonnancement de type job-shop

flexible mono-opration toutes les machines tant utilisables ........................... 76

Tableau 3.3 - Benchmark 10x6 relatif un problme dordonnancement de type job-shop

flexible mono-opration certaines machines ntant pas utilisables .................. 77

Tableau 3.4 - Benchmark 3x5 relatif un problme dordonnancement

de type job-shop flexible multi-oprations......................................................... 77

Tableau 3.5 - Rsultats comparatifs des diffrentes variantes de la mthode BOEP............... 86

Tableau 3.6 -Tableau comparatif des rsultats relatifs aux mises en uvre de la mthode base

sur loptimisation par essaim particulaire (BOEP) et des algorithmes gntiques

(AG) pour les problmes FJSP........................................................................... 86

Tableau 3.7 - Tableau comparatif des rsultats relatifs aux mises en uvre de la mthode

BOEP et des AG pour les problmes flow-shop en industries pharmaceutiques 91

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Introduction Gnrale

11

Introduction gnrale

Parmi les problmes rencontrs par le chercheur et lingnieur, les problmes doptimisation

occupent notre poque une place de choix. Formuler les problmes doptimisation et tenter

de les rsoudre reprsentent lobjectif principal de nombreux chercheurs.

Comprendre, analyser et formuler un problme doptimisation ncessitent dabord une

dfinition des paramtres, des variables, de lespace de recherche ainsi que des fonctions

optimiser.

Une fois la (ou les) fonction(s) optimiser dfinie(s), une mthode adapte pour la rsolution

du problme pos est choisie.

A ce niveau, la taille et la complexit du problme entrent en compte pour le choix de la

mthode doptimisation. Si le problme est de petite taille et de complexit rduite, la mise en

uvre dune mthode exacte peut suffire et aboutir une solution optimale.

Dans le cas de problmes de tailles importantes, les mthodes approches constituent le

moyen le plus efficace de se rapprocher le plus possible de la solution optimale.

Quil sagisse dune optimisation mono ou multi-objectifs entre galement en ligne de

compte. Dans le cas dun objectif unique, la dfinition de la fonction fitness, f, ne pose

gnralement pas de problme. Par exemple, si lon se fixe lobjectif de minimiser un cot C,

la fonction fitness sera gale C.

Certains problmes doptimisation doivent satisfaire des objectifs multiples, souvent

concurrents, ce qui ncessite parfois la recherche dun compromis. Une mthode classique, en

prsence de fonctions objectifs fi, consiste les combiner en effectuant, par exemple, une

somme pondre des fonctions objectifs, =i

ii ff , ramenant ainsi un problme multi-

objectifs un problme mono-objectif.

Cest lutilisateur de fixer convenablement les poids des objectifs, tenant compte de leur

importance ou de les adapter, parfois, par ttonnement.

Les problmes dordonnancement dans le secteur industriel, sont parmi les problmes

doptimisation les plus tudis. Amliorer le rendement des ressources et minimiser les cots

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Introduction Gnrale

12

de production sont devenus les leitmotivs des industriels. Chercher le meilleur moyen de

maximiser son profit est aujourdhui lun des objectifs principaux de toute entreprise.

Cest dans ce contexte quentre nos travaux de recherche. Ils concernent la rsolution de

problmes multi-objectifs dordonnancement en industries pharmaceutiques. Au niveau de ce

type dindustries, assurer la production en quantit et surtout de qualit irrprochable, dans les

dlais impartis et tenant compte des diffrentes saisons tout en minimisant les cots,

reprsente un challenge de tous les jours.

Sachant que les problmes de production dans les industries pharmaceutiques sont complexes

et ncessitent la prise en compte de plusieurs facteurs essentiellement lis au respect de

lhygine ainsi que de lassurance et du contrle de la qualit, nous nous orientons pour leur

rsolution vers le choix des mthodes approches.

Deux mthodes sont donc utilises tout au long de ce rapport. La mthode des algorithmes

gntiques et la mthode doptimisation par essaim particulaire qui sont des mthodes

volutionnistes.

Les algorithmes volutionnistes doivent leur nom l'analogie avec les mcanismes

d'volution des espces vivantes. Un algorithme volutionniste est compos de trois lments

essentiels : une population constitue de plusieurs individus reprsentant des solutions

potentielles pour problme pos, un mcanisme d'valuation de ladaptation de chaque

individu de la population l'gard de son environnement et un mcanisme d'volution

compos d'oprateurs permettant d'liminer certains individus et de produire de nouveaux

individus partir des individus slectionns.

Un algorithme volutionniste dbute, donc par la cration dune population initiale souvent

gnre alatoirement et rpte ensuite un cycle d'volution compos de trois tapes

essentielles qui sont la mesure de la qualit de chaque individu de la population par le

mcanisme d'valuation, la slection des individus pour une ventuelle volution et la

gnration de nouveaux individus par recombinaisons d'individus slectionns. Une condition

darrt indique la fin de ce processus.

Le premier chapitre de ce mmoire propose, dans un premier temps, une vue densemble sur

les problmes dordonnancement des systmes de production et sur leur complexit. Ainsi les

diffrentes composantes de lordonnancement sont prsentes et les types dateliers pouvant

les caractriser introduits. Diffrentes reprsentations possibles des problmes

dordonnancement sont par la suite proposes. Dans un deuxime temps, nous focalisons

notre attention sur la prsentation des diffrentes mthodes doptimisation allant des mthodes

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Introduction Gnrale

13

exactes aux mthodes approches indiquant celles qui sont les plus utilises dans la littrature.

En conclusion ce chapitre, la problmatique relative lordonnancement en industries

pharmaceutiques et des critres minimiser est prsente.

Dans la premire partie du deuxime chapitre, les spcificits et les diffrents problmes

rencontrs dans un atelier de conditionnement en industries pharmaceutiques sont introduits.

Les lignes de conditionnement composant le poste en question sont dtailles nous amenant

ainsi nous intresser aux ateliers de type flow-shop dont elles font partie.

La deuxime partie, quant elle traite de la rsolution du problme multi-objectifs pos en

utilisant la mthode des algorithmes gntiques.

Un Codage spcifique est recherch pour permettre la meilleure reprsentation possible du

problme trait.

Deux exemples sont par la suite traits, et les rsultats relatifs consigns pour leur

comparaison ultrieure avec la mthode doptimisation par essaim particulaire au niveau du

chapitre suivant.

Dans le troisime chapitre, la mthode doptimisation par essaim particulaire est introduite et

son utilisation dans le cas continu prsente. La formulation de cette mthode est, par la suite,

modifie pour permettre son adaptation au cas discret.

Dans une premire partie, trois exemples traitant de lordonnancement job-shop flexible ont

t traits et compars avec des rsultats obtenus par utilisation des algorithmes gntiques.

Dans une deuxime partie, nous revenons au problme dordonnancement en industries

pharmaceutiques trait au deuxime chapitre pour effectuer une comparaison des rsultats

obtenus.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Chapitre I Ordonnancement : spcificits, ateliers, mthodes et complexit

14

Chapitre I

Ordonnancement : spcificits, ateliers,

mthodes et complexit

I.1 - Introduction La ralisation dun projet ncessite souvent une succession de tches auxquelles sattachent

certaines contraintes :

- de temps, relatives aux dlais respecter pour lexcution des tches,

- dantriorit, o certaines tches doivent sexcuter avant dautres,

- de production, concernant le temps doccupation du matriel ou des hommes qui

lutilisent, ...

Les techniques dordonnancement dans le cadre de la gestion dun projet ont pour objectif de

rpondre au mieux aux besoins exprims par un client, au meilleur cot et dans les meilleurs

dlais, en tenant compte des diffrentes contraintes.

Lordonnancement se droule en trois tapes qui sont:

- la planification, qui vise dterminer les diffrentes oprations raliser, les dates

correspondantes, et les moyens matriels et humains y affecter.

- lexcution, qui consiste mettre en uvre les diffrentes oprations dfinies dans la

phase de planification.

- le contrle, qui consiste effectuer une comparaison entre planification et excution,

soit au niveau des cots, soit au niveau des dates de ralisation.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


15

Ainsi, le rsultat dun ordonnancement est un calendrier prcis de tches raliser qui se

dcompose en trois importantes caractristiques :

- laffectation, qui attribue les ressources ncessaires aux tches,

- le squencement, qui indique lordre de passage des tches sur les ressources,

- le datage, qui indique les temps de dbut et de fin dexcution des tches sur les

ressources.

Dans ce chapitre, quelques gnralits sur les problmes dordonnancement dans les ateliers

de production dont les spcificits : les types dateliers, les critres doptimisation et la

complexit sont introduites. Dans un deuxime temps, une description des principales

mthodes doptimisation utilises dans la littrature est ralise nous permettant ainsi de

prsenter celles que nous utiliserons dans la suite de ce rapport.

I.2 - Gnralits sur lordonnancement Lordonnancement est une branche de la recherche oprationnelle et de la gestion de la

production qui vise amliorer lefficacit dune entreprise en termes de cots de production

et de dlais de livraison. Les problmes dordonnancement sont prsents dans tous les

secteurs dactivits de lconomie, depuis lindustrie manufacturire [Pinedo, 55] jusqu

linformatique [Blazewicz et al, 96].

Ordonnancer le fonctionnement dun systme industriel de production consiste grer

lallocation des ressources au cours du temps, tout en optimisant au mieux un ensemble de

critres [Rodammer et al, 88]. Cest aussi programmer lexcution dune ralisation en

attribuant des ressources aux tches et en fixant leurs dates dexcution [Carlier et al, 88].

Ordonnancer peut galement consister programmer lexcution des oprations en leur

allouant les ressources requises et en fixant leurs dates de dbut de fabrication.

Dune manire plus simple, un problme dordonnancement consiste affecter des tches

des ressources des instants donns pour rpondre au mieux aux besoins exprims par un

client, au meilleur cot et dans les meilleurs dlais, tout en tenant compte des contraintes.

Les problmes dallocation des ressources, dorganisation des tches, de respect des dlais et

de prise de dcision en temps requis constituent autant de difficults quil est ncessaire de

surmonter dans la gestion des systmes de production en milieu industriel.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


16

Au niveau de lentreprise, lordonnancement concerne plusieurs postes : les ventes, la

production, la maintenance, etc. Son rle est de plus en plus important, car il permet une

gestion de ces diffrents postes qui peut tre optimale.

Pour la bonne gestion de ces postes ainsi que des contraintes pouvant y tre relies, il est

ncessaire :

- de dterminer les diffrentes oprations raliser, les dates correspondantes, les

moyens matriels et humains y affecter,

- dexcuter ces oprations et de contrler les cots qui en dcoulent.

Cest ainsi que lordonnancement intervient pour permettre la meilleure gestion possible du

systme de production.

I.3 - Formulation dun problme dordonnancement Les problmes dordonnancement apparaissent dans tous les domaines : informatique,

industrie, construction, administration, etc [Carlier, 88].

Les diffrentes donnes dun problme dordonnancement sont les tches, les ressources, les

contraintes et les critres.

Ainsi, tant donns un ensemble de tches et un ensemble de ressources, il sagit de

programmer les tches et affecter les ressources de faon optimiser un ou plusieurs objectifs

(un objectif correspondant un critre de performance), en respectant un ensemble de

contraintes.

I.3.1 - Les tches

Une tche est une entit lmentaire localise dans le temps, par une date de dbut et/ou de

fin, et dont la ralisation ncessite une dure pralablement dfinie.

Elle est constitue dun ensemble doprations qui requiert, pour son excution, certaines

ressources et quil est ncessaire de programmer de faon optimiser un certain objectif.

On distingue deux types de tches :

o les tches morcelables (premptibles) qui peuvent tre excutes en plusieurs fois, facilitant ainsi la rsolution de certains problmes,

o les tches non morcelables (indivisibles) qui doivent tre excutes en une seule fois et ne sont interrompues quune fois termines.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


17

I.3.2 - Les ressources Une ressource est un moyen technique ou humain utilis pour raliser une tche. On trouve

plusieurs types de ressources :

o les ressources renouvelables, qui, aprs avoir t alloues une tche, redeviennent disponibles (machines, personnel, etc),

o les ressources consommables, qui, aprs avoir t alloues une tche, ne sont plus disponibles (argent, matires premires, etc).

Qu'elle soit renouvelable ou consommable, la disponibilit d'une ressource peut varier au

cours du temps. Par ailleurs, dans le cas des ressources renouvelables, on distingue

principalement, les ressources disjonctives qui ne peuvent excuter qu'une tche la fois et

les ressources cumulatives qui peuvent tre utilises par plusieurs tches simultanment mais

en nombre limit .

I.3.3 - Les contraintes

Suivant la disponibilit des ressources et suivant lvolution temporelle, deux types de

contraintes peuvent tre distingues [Carlier et al, 88] : contraintes de ressources et

contraintes temporelles.

o les contraintes de ressources : plusieurs types de contraintes peuvent tre induites par la nature des ressources. A titre dexemple, la capacit limite dune ressource

implique un certain nombre, ne pas dpasser, de tches excuter sur cette

ressource.

Les contraintes relatives aux ressources peuvent tre disjonctives, induisant une

contrainte de ralisation des tches sur des intervalles temporels disjoints pour une

mme ressource, ou cumulatives impliquant la limitation du nombre de tches

raliser en parallle.

o les contraintes temporelles : elles reprsentent des restrictions sur les valeurs que peuvent prendre certaines variables temporelles dordonnancement. Ces contraintes

peuvent tre :

- des contraintes de dates butoirs, certaines tches doivent tre acheves avant

une date pralablement fixe,

- des contraintes de prcdence, une tche i doit prcder la tche j,

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


18

- des contraintes de dates au plus tt, lies lindisponibilit de certains facteurs

ncessaires pour commencer lexcution des tches.

I.3.4 - Les critres

Un critre correspond des exigences qualitatives et quantitatives satisfaire permettant

dvaluer la qualit de lordonnancement tabli.

Les critres dpendant dune application donne sont trs nombreux; plusieurs critres

peuvent tre retenus pour une mme application. Le choix de la solution la plus satisfaisante

dpend du ou des critres pralablement dfinis, pouvant tre classs suivant deux types,

rguliers et irrguliers.

Les diffrents critres ne sont pas indpendants; certains mme sont quivalents. Deux

critres sont quivalents si une solution optimale pour lun est aussi optimale pour lautre et

inversement [Carlier et al, 88]

o Les critres rguliers constituent des fonctions dcroissantes des dates dachvement des oprations. Quelques exemples sont cits ci-dessous:

- la minimisation des dates dachvement des actions,

- la minimisation du maximum des dates dachvement des actions,

- la minimisation de la moyenne des dates dachvement des actions,

- la minimisation des retards sur les dates dachvement des actions,

- la minimisation du maximum des retards sur les dates dachvement des actions.

o Les critres irrguliers sont des critres non rguliers, c'est--dire qui ne sont pas des fonctions monotones des dates de fin dexcution des oprations, tels que:

- la minimisation des encours,

- la minimisation du cot de stockage des matires premires,

- lquilibrage des charges des machines,

- loptimisation des changements doutils.

La satisfaction de tous les critres la fois est souvent dlicate, car elle conduit souvent des

situations contradictoires [Roy et al, 93] et la recherche de solutions des problmes

complexes doptimisation.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


19

I.4 - Les ateliers Une classification des problmes dordonnancement dans un atelier peut soprer selon le

nombre de machines et leur ordre dutilisation pour fabriquer un produit, qui dpend de la

nature de latelier considr. Un atelier est caractris par le nombre de machines quil

contient et par son type.

Comme le montre la figure1.1, On distingue les trois types dateliers suivants : flow-shop,

job-shop et open-shop, avec des extensions possibles pour chacun deux.

I.4.1 - Les ateliers de type flow-shop

Appels galement ateliers cheminement unique, ce sont des ateliers o une ligne de

fabrication est constitue de plusieurs machines en srie; toutes les oprations de toutes les

tches passent par les machines dans le mme ordre. Dans les ateliers de type flow-shop

hybride, une machine peut exister en plusieurs exemplaires identiques fonctionnant en

parallle.

I.4.2 - Les ateliers de type job-shop

Appels galement ateliers cheminement multiple, ce sont des ateliers o les oprations sont

ralises selon un ordre bien dtermin, variant selon la tche excuter; le job-shop flexible

est une extension du modle job-shop classique; sa particularit rside dans le fait que

plusieurs machines sont potentiellement capables de raliser un sous-ensemble doprations.

I.4.3 - Les ateliers de type open-shop

Ce type datelier est moins contraint que celui de type flow-shop ou de type job-shop. Ainsi,

lordre des oprations nest pas fix a priori; le problme dordonnancement consiste, dune

part, dterminer le cheminement de chaque produit et, dautre part, ordonnancer les

produits en tenant compte des gammes trouves, ces deux problmes pouvant tre rsolus

simultanment. Compar aux autres modles dateliers, lopen-shop nest pas couramment

utilis dans les entreprises.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


20

Figure 1. 1 - Classification des types dateliers

I.5 - Reprsentation des problmes dordonnancement Il existe trois sortes de reprsentations possibles dun problme dordonnancement: le

diagramme de Gantt, le graphe Potentiel-Tches et la mthode PERT.

I.5.1 - Le diagramme de Gantt

Le diagramme de Gantt est un outil permettant de modliser la planification des tches

ncessaires la ralisation d'un projet. Il s'agit d'un outil labor en 1917 par Henry L. Gantt.

Etant donn la facilit relative de lecture des diagrammes de Gantt, cet outil est utilis par la

quasi-totalit des chefs de projet dans tous les secteurs. Il permet de reprsenter

graphiquement l'avancement du projet et constitue galement un bon moyen de

communication entre les diffrents acteurs d'un projet. Le diagramme de Gantt prsente en

ordonne la liste des tches, notes Ti excuter par les machines notes Mj et en abscisse

lchelle du temps, comme le montre la figure 1.2 dans le cas o i = 1,2,,5 et j = 1,2.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


21

Figure 1. 2 - Diagramme de Gantt dun ordonnancement

I.5.2 - Graphe Potentiel-Tches

Cette outil graphique a t dvelopp grce la thorie des rseaux de Ptri qui ont surtout

servi modliser les systmes dynamiques vnements discrets [Carlier et al, 84].

Dans ce genre de modlisation, les tches sont reprsentes par des nuds et les contraintes

par des arcs [Roy 70], comme le montre la figure 1.3.

Ainsi, les arcs peuvent tre de deux types :

- les arcs conjonctifs illustrant les contraintes de prcdence et indiquant les dures des

tches,

- les arcs disjonctifs indiquant les contraintes de ressources [Gotha, 93], [Jain et al, 99].

Exemple de graphe potentiel-tches

Tableau 1. 1 - Donnes utilises pour la ralisation dun graphe potentiel-tches

Tches Dures Contraintes

a 6 mois

b 3 mois

c 6 mois

d 2 mois b acheve

e 4 mois b acheve

f 3 mois d et a acheves

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


22

Pour qu'une tche puisse commencer, il est ncessaire que toutes les tches qui la relient la

tche du dbut S du projet, soient ralises. On dfinit donc :

- la date au plus tt de la tche, qui correspond la date de dbut, au plus tt, de

l'excution de la tche.

Exemple : la tche f ne peut s'excuter que si a et d ont t ralises. Donc, pour

excuter a il faut 6 mois et pour excuter d il faut 2+3 mois. La tche f ne pourra

commencer au plus tt que 6 mois aprs le dbut du projet: c'est donc le plus long

chemin entre a et f.

- la dure du projet, qui correspond au plus long chemin entre S (tche de dbut du

projet) et S (tche de fin du projet).

Figure 1. 3 - Graphe Potentiel-Tches d'un ordonnancement

I.5.3 - Mthode PERT (Program Evaluation and Research Task)

Cette reprsentation, semblable la prcdente, permet de reprsenter une tche par un arc,

auquel est associ un chiffre qui reprsente la dure de la tche. Entre les arcs, figurent des

cercles, appels sommets ou vnements, qui marquent laboutissement dune ou de plusieurs

tches. Ces cercles sont numrots afin de suivre lordre de succession des divers vnements.

Les mthodes graphiques ont connu une trs importante volution surtout avec lapparition

des Rseaux de Ptri (RdP) [Chrtienne, 83], [Carlier et al, 84], qui permettent de traduire

plusieurs notions fondamentales ayant un lien avec les problmes dordonnancement, telles

que :

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


23

- les conflits sur les ressources,

- les dures opratoires certaines,

- les dures opratoires alatoires,

- les gammes,

- les disponibilits, les multiplicits et les capacits de ressources

- la rptitivit, etc

I.6 - Complexit des problmes dordonnancement Dune manire gnrale, les problmes dordonnancement dateliers tant des problmes

combinatoires difficiles, il nexiste pas de mthodes universelles permettant de rsoudre tous

les cas.

Plusieurs algorithmes peuvent tre utiliss pour rsoudre un problme dordonnancement

mais tous ne sont pas quivalents.

On peut diffrencier les divers algorithmes de rsolution par le moyen des critres suivants :

o l'efficacit de l'algorithme en terme de dure d'excution; un algorithme est dit plus efficace qu'un autre si pour les mmes donnes, il s'excute en un laps de temps plus

court;

o l'efficacit de l'algorithme en espace mmoire de stockage; un algorithme est dit plus efficace qu'un autre si pour rsoudre le mme problme, il utilise moins d'espace

mmoire;

o la fiabilit de l'algorithme; plus un programme est complexe, plus il y a des risques d'existence de bugs, les bugs tant des erreurs plus ou moins videntes qui se

manifestent lors de la mise en exploitation dun programme. Un programme est jug

plus fiable ou plus stable qu'un autre s'il prsente moins de bugs;

o la robustesse de l'algorithme; elle mesure son degr de tolrance aux erreurs des utilisateurs et sa rsistance aux attaques des pirates; un programme est plus robuste

qu'un autre s'il rsiste mieux aux erreurs de manipulations des utilisateurs plus ou

moins bien attentionns.

Il est noter qu'il n'y a pas de mthode ou d'chelle de mesure permettant d'valuer la fiabilit

ou la robustesse d'un algorithme. C'est l'usage que ces qualits sont mesures. Par contre, il

existe des mthodes rationnelles et rigoureuses pour valuer l'efficacit en temps ou en espace

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


24

d'un algorithme. Ces mthodes d'valuation portent le nom d'analyse de complexit des

algorithmes.

Deux types de complexit peuvent tre cits:

o la complexit mthodologique, qui exprime une fonction du nombre doprations lmentaires de calcul effectues par la mthode ou par lalgorithme de rsolution en

fonction du nombre des donnes du problme trait,

o la complexit problmatique, lie la difficult du problme rsoudre et au nombre des oprations lmentaires quun algorithme dterministe peut effectuer pour trouver

loptimum en fonction de la taille du problme.

Selon son degr de complexit, un problme peut appartenir lune des quatre classes

suivantes [Sakarovitch 84] :

les problmes les plus difficiles, qui sont des problmes pour lesquels il nexiste aucune mthode de rsolution; ils sont dits indcidables,

les problmes de la classe P, dits polynomiaux, sil existe un algorithme de complexit polynomiale pour leur rsolution,

les problmes de la classe NP, dits problmes NP-difficiles, qui ne peuvent priori tre rsolus en un temps polynomial que par des mthodes approches

(heuristiques); au cours de leur excution, ces algorithmes font des choix dont

loptimalit nest pas dmontrable,

les problmes NP-Complets, qui rpondent la dfinition suivante : un problme de dcision A est dit NP-Complet sil appartient la classe NP et si pour tout A de

NP :

- il existe une application polynomiale qui transforme toute instance I de A

en une instance I de A,

- A admet une rponse "oui" pour linstance I, si et seulement si A admet

une rponse "oui" pour linstance I.

Autrement dit, sil existe un algorithme polynomial pour rsoudre A, alors, pour

tout le reste des problmes de la classe, il existe des algorithmes polynomiaux pour

les rsoudre.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


25

I.7 - Mthodes doptimisation Etant donns un ensemble de tches et un ensemble de ressources, il est ncessaire de

programmer les tches et daffecter les ressources de faon optimiser un ou plusieurs

objectifs (un objectif correspondant un critre de performance), en respectant un ensemble

de contraintes. La principale difficult laquelle est confront un dcideur, en prsence dun

problme doptimisation est celui du choix dune mthode efficace capable de produire une

solution optimale en un temps de calcul raisonnable.

Les diffrentes mthodes de rsolution dveloppes peuvent tre classes en deux catgories :

les mthodes exactes qui garantissent la compltude de la rsolution et les mthodes

approches qui perdent la compltude pour gagner en efficacit.

I.7.1 - Les mthodes exactes

On peut dfinir une mthode exacte comme tant une mthode qui fournit une solution

optimale pour un problme doptimisation.

Lutilisation de ce type de mthodes savre particulirement intressante dans les cas des

problmes de petites tailles. La mthode par sparation et valuation (branch and bound) [Le

Pape, 95], [Baptiste, 96] constituent certainement celles qui sont les plus utilises pour

rsoudre les problmes doptimisation multi-objectifs [Sakarovitch, 84]. Dautres mthodes

telles que la programmation linaire ou la programmation dynamique, sont aussi utilises

couramment.

Toutes ces mthodes examinent dune manire implicite, la totalit de lespace de recherche

pour produire la solution optimale.

a - La mthode Branch and Bound

Lalgorithme Branch and Bound consiste placer progressivement les tches sur les

ressources en explorant un arbre de recherche dcrivant toutes les combinaisons possibles.

Il sagit de trouver la meilleure configuration donne de manire laguer les branches de

larbre qui conduisent de mauvaises solutions.

Lalgorithme branch and bound effectue une recherche complte de lespace des solutions

dun problme donn, pour trouver la meilleure solution.

La dmarche de lalgorithme Branch and Bound consiste [Collette et al, 02] :

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


26

- diviser lespace de recherche en sous espaces,

- chercher une borne minimale en terme de fonction objectif associe chaque

sous espace de recherche,

- liminer les mauvais sous-espaces,

- reproduire les tapes prcdentes jusqu lobtention de loptimum global.

b - La programmation dynamique

Elle se base sur le principe de Bellman [Bellman, 86] : Si C est un point qui appartient au

chemin optimal entre A et B, alors la portion de ce mme chemin allant de A C est le

chemin optimal entre A et C . Cest une mthode qui consiste donc construire dabord les

sous-chemins optimaux et ensuite par rcurrence le chemin optimal pour le problme entier.

Cette mthode est destine rsoudre des problmes doptimisation vocation plus gnrale

que la mthode de sparation et dvaluation (branch and bound) sans permettre pour autant

daborder des problmes de tailles importantes.

c - La programmation linaire

Cest lune des techniques classiques de recherche oprationnelle. Elle repose sur la mthode

du simplexe et les algorithmes de points intrieurs de Karmarkar [Sakarovitch, 84].

Elle consiste minimiser une fonction cot en respectant des contraintes, le critre et les

contraintes tant des fonctions linaires des variables du problme [Mellouli et al, 04].

d - Les heuristiques

Les heuristiques sont des mthodes empiriques qui donnent gnralement de bons rsultats

sans pour autant tre dmontrables. Elles se basent sur des rgles simplifies pour optimiser

un ou plusieurs critres. Le principe gnral de cette catgorie de mthodes est dintgrer des

stratgies de dcision pour construire une solution proche de celle optimale tout en cherchant

avoir un temps de calcul raisonnable [Bel, 01]. Parmi ces stratgies, nous distinguons :

- FIFO (First In First Out) o la premire tche arrive est la premire tre

ordonnance,

- SPT (Shortest Processing Time) o la tche ayant le temps opratoire le plus

court est traite en premier,

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


27

- LPT (Longest Processing Time) o la tche ayant le temps opratoire le plus

important est traite en premier,

- EDD (Earliest Due Date) o la tche ayant la date due la plus petite est la plus

prioritaire,

I.7.2 - Les mthodes approches ou mtaheuristiques

Malgr lvolution permanente de linformatique, il existe toujours, pour un problme

polynomial, une taille critique au-dessus de laquelle une numration, mme partielle, des

solutions admissibles devient prohibitive. Compte tenu de ces difficults, la plupart des

spcialistes de loptimisation combinatoire ont orient leurs recherches vers le dveloppement

des mtaheuristiques [Widmer, 01]. Une mtaheuristique est souvent dfinie comme une

procdure exploitant au mieux la structure du problme considr, dans le but de trouver une

solution de qualit raisonnable en un temps de calcul aussi faible que possible [Nicholson,

71].

Les mtaheuristiques sont ainsi des mthodes de recherche gnrales, ddies aux problmes

doptimisation difficile. Elles sont, en gnral, prsentes sous forme de concepts.

Les principales mtaheuristiques sont celles bases sur la recherche locale, telles que le recuit

simul et la recherche Tabou, et celles bases sur les algorithmes volutionnistes telles que

les algorithmes gntiques ainsi que les algorithmes bass sur la recherche globale tels que les

algorithmes de colonies de fourmis et les algorithmes reposant sur la mthode doptimisation

par essaim particulaire.

a - Les mthodes bases sur la recherche locale

La recherche locale peut tre rsume comme tant une procdure de recherche itrative qui,

partir d'une premire solution ralisable, l'amliore progressivement en appliquant une srie

de modifications (ou mouvements) locales, comme montr dans la figure 1.4. Il faut, pour

cela introduire une structure de voisinage qui consiste spcifier un voisinage pour chaque

solution. Ainsi, chaque itration, la recherche s'oriente vers une nouvelle solution ralisable

qui diffre lgrement de la solution courante en remplaant celle-ci par une meilleure situe

dans son voisinage. La recherche se termine si un optimum local est rencontr. L'inconvnient

important de cette mthode est qu' moins d'tre extrmement chanceux, cet optimum local

est souvent une solution assez mdiocre. Dans la recherche locale, la qualit des solutions

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


28

obtenues dpend fortement de la richesse de l'ensemble des transformations (mouvements)

considres chaque itration.

Pour faire face cette limitation, des mthodes de recherche locale plus sophistiques ont t

dveloppes au cours de ces vingt dernires annes. Ces mthodes acceptent des solutions

voisines moins bonnes que la solution courante afin dchapper aux minima locaux. En rgle

gnrale, seule une portion du voisinage courant est explore chaque tape [Widmer, 01].

Les mthodes les plus connues sont le recuit simul [Kirkpatrick et al, 83] et la recherche

tabou [Glover, 89], [Glover, 90].

Figure 1. 4 - Exploration de lespace de recherche dans la mthode de recherche locale

Le recuit simul Inspir du recuit physique, ce processus est utilis en mtallurgie pour amliorer la qualit

dun solide et cherche un tat dnergie minimale qui correspond une structure stable du

solide. Ainsi, pour quun mtal retrouve une structure proche du cristal parfait, on porte celui-

ci une temprature leve, puis on le laisse refroidir lentement de manire ce que les

atomes aient le temps de sordonner rgulirement.

L'algorithme du recuit simul [Kirkpatrick et al, 83], permet de rsoudre les problmes de

minima locaux. En effet, une nouvelle solution de cot suprieur celui de la solution

courante ne sera pas forcment rejete, son acceptation sera dtermine alatoirement en

tenant compte de la diffrence entre les cots ainsi que du facteur temprature T. Ce

paramtre, sert prendre en compte le fait que plus le processus d'optimisation est avanc,

moins on est prs accepter une solution plus coteuse. Par contre, l'acceptation de solutions

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


29

fortement coteuses permet, au dbut, de mieux explorer l'espace des solutions possibles et

ainsi, d'accrotre les chances d'approcher le minimum global.

Kirkpatrick [Kirkpatrick et al, 83] et Cerny [Cerny, 85] se sont inspirs dune telle technique

pour rsoudre des problmes doptimisation combinatoire. Le voisinage N(s) dune solution,

sapparente lensemble des tats atteignables depuis ltat courant, en faisant subir des

dplacements aux atomes du systme physique.

A chaque itration, une seule solution voisine est gnre. Celle-ci est accepte si elle est

meilleure que la solution courante. Dans le cas contraire, la nouvelle solution est accepte

avec une certaine probabilit qui dpend de limportance de la dtrioration et du paramtre T

correspondant la temprature. En rgle gnrale, la temprature est diminue par paliers,

chaque fois quun certain nombre ditrations est effectu. La meilleure solution trouve est

mmorise. Lalgorithme est interrompu lorsquaucune solution voisine na t accepte

pendant un cycle complet ditrations temprature constante [Widmer, 01].

De nombreuses tudes ont t effectues sur la mthode du recuit simul [Collins et al, 88],

[Osman et Christofides, 1994]. En optimisation, le processus du recuit simul rpte une

procdure itrative qui cherche des configurations de cots plus faibles tout en acceptant de

manire contrle des configurations qui dgradent la fonction de cot [Collette, 02], [Hao,

99]. Ainsi, si une amlioration du critre est constate, le nouvel tat est retenu, sinon une

diminution du critre est calcule et le nouvel tat est retenu si p tant un nombre tir de

faon alatoire entre 0 et 1, on a exp(-/T) > p.

Un algorithme doptimisation par recuit simul se dcompose selon les tapes suivantes

[Laquerbe et al, 98] :

- choix dune fonction optimiser,

- adoption dun schma de recuit dans lequel sont prciss la temprature initiale,

le nombre de configurations gnres chaque temprature et le schma de

dcroissance du critre,

- gnration stochastique de configurations voisines, correspondant aux

transitions,

- choix dun critre dacceptation.

Cet algorithme est prsent dans la figure 1.5.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


30

Figure 1. 5 - Algorithme relatif au fonctionnement gnral du recuit simul

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


31

La recherche tabou Bien que son origine remonte 1977, la recherche tabou nest propose quau milieu des

annes 80 par Fred Glover [Glover, 89], [Glover, 90]. Cette mthode, dveloppe pour

rsoudre des problmes combinatoires, la plupart NP-difficiles, propose de surmonter le

problme des optima locaux par lutilisation dune mmoire.

La mthode tabou est une procdure itrative qui, partant dune solution initiale, tente de

converger vers la solution optimale en excutant, chaque pas, un mouvement dans lespace

de recherche. Chaque pas consiste dabord engendrer un ensemble de solutions voisines de

la solution courante pour ensuite en choisir la meilleure, mme si ce choix entrane une

augmentation de la fonction objectif minimiser.

En acceptant de dtriorer la valeur de la solution courante, le minimum local peut tre vit

mais, en contre partie, des parcours rptitifs sont dplors.

Aussi, pour palier linconvnient majeur des mthodes de recherche locale, la recherche

tabou a pour but damliorer chaque tape, la valeur de la fonction objectif, en utilisant une

mmoire afin de conserver les informations sur les solutions dj visites.

Cette mmoire constitue la liste Tabou qui va servir interdire laccs aux dernires solutions

visites. Lorsquun optimum local est atteint, il y a interdiction de revenir sur le mme

chemin.

Un critre daspiration, est galement utilis pour lever linterdiction dutilisation dun

mouvement si ce dernier conduit une meilleure solution.

Plusieurs stratgies ont t proposes rcemment afin damliorer lefficacit de la mthode

tabou. Lintensification et la diversification de la recherche constituent deux dentre elles

[Widmer, 01].

- Lintensification consiste explorer en dtails une rgion de lespace de recherche juge

prometteuse. Sa mise en uvre consiste, le plus souvent, en un largissement temporaire

du voisinage de la solution courante dans le but de visiter un ensemble de solutions

partageant certaines proprits.

- La diversification a pour objectif de diriger la procdure de recherche vers des rgions

inexplores de lespace de recherche. La stratgie de diversification la plus simple

consiste redmarrer priodiquement le processus de recherche partir dune solution,

gnre alatoirement ou choisie judicieusement, dans une rgion non encore visite de

lensemble des solutions admissibles.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


32

Les domaines dapplication de la recherche tabou sont vastes et varis, ils passent de

lordonnancement la robotique, au problme du voyageur de commerce, llectronique

voire mme aux applications mdicales, En tenant compte des notations suivantes, les

tapes dvolution de lalgorithme sont prsentes dans la figure 1.6.

s0 : la solution initiale, s* : la meilleure solution actuelle, f(x) : la fonction minimiser, f(s*) : la valeur de la fonction minimiser pour obtenir la meilleure solution, T : la liste tabou.

Figure 1. 6 - Algorithme relatif au fonctionnement gnral de la mthode de recherche tabou

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


33

b - Les algorithmes volutionnistes : algorithmes gntiques Contrairement aux mthodes de recherche locale qui font intervenir une solution unique, les

mthodes volutives manipulent un groupe de solutions admissibles chacune des tapes du

processus de recherche. Lide centrale consiste utiliser rgulirement les proprits

collectives dun ensemble de solutions distinguables, appel population, dans le but de guider

efficacement la recherche vers de bonnes solutions dans lespace de recherche.

En rgle gnrale, la taille de la population reste constante tout au long du processus. Aprs

avoir gnr une population initiale de solutions, une mthode volutive tente damliorer la

qualit moyenne de la population courante en ayant recours des principes dvolution

naturelle [Widmer, 01].

Parmi les mthodes volutionnistes, nous citons les algorithmes gntiques.

Les Algorithmes Gntiques (A.G.) [Holland, 75] sont des algorithmes itratifs dont le but est

doptimiser une fonction prdfinie, appele fitness.

Pour raliser cet objectif, lalgorithme travaille sur un ensemble de points, appels population

dindividus. Chaque individu ou chromosome (chane binaire de longueur finie dans les

premires dfinitions) reprsente une solution possible du problme donn. Il est constitu

dlments, appels gnes, dont les valeurs sont appeles allles.

L'utilisation d'un algorithme gntique ncessite la dfinition, au pralable, d'un espace de

recherche dont les lments de base sont les chromosomes et d'une fonction dfinie sur cet

espace (fonction fitness) dont la valeur optimale est value en rapport avec les oprateurs de

croisement et de mutation choisis [Iyer, 04].

Cinq lments de base sont ncessaires pour lutilisation des algorithmes gntiques [Durand

et al, 94] :

- un principe de codage des lments de la population, qui consiste associer chacun des

points de lespace dtat une structure de donnes, la qualit de ce codage des donnes

conditionnant le succs des algorithmes gntiques; bien que le codage binaire ait t

trs utilis lorigine, les codages rels sont dsormais largement utiliss, notamment

dans les domaines applicatifs pour loptimisation de problmes variables relles,

- un mcanisme de gnration de la population initiale qui doit tre capable de produire

une population dindividus non homogne servant de base pour les gnrations futures;

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


34

le choix de la population initiale est important car il influence la rapidit de la

convergence vers loptimum global; dans le cas o lon ne dispose que de peu

dinformations sur le problme rsoudre, il est essentiel que la population initiale soit

rpartie sur tout le domaine de recherche,

- une fonction optimiser, appele fitness ou fonction dvaluation de lindividu,

- des oprateurs permettant de diversifier la population au cours des gnrations et

dexplorer lespace dtat; loprateur de croisement recompose les gnes dindividus

existant dans la population alors que loprateur de mutation garantit lexploration de

lespace dtat,

- des paramtres de dimensionnement, reprsents par la taille de la population, le nombre

total de gnrations, ou le critre darrt, ainsi que les probabilits dapplication des

oprateurs de croisement et de mutation.

Lenchanement de ces diffrents lments est reprsent dans la figure 1.6. Cette mthode

sera prsente plus en dtail dans le second chapitre de ce mmoire.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


35

Figure 1. 7 - Fonctionnement gnral dun algorithme gntique

c - Les algorithmes de recherche globale

Les algorithmes de colonies de fourmis Ces algorithmes sont ns la suite de constatations faites sur le comportement des fourmis qui

sont capables de trouver le chemin le plus court, du nid une source de nourriture, et de

sadapter aux changements de lenvironnement.

Les biologistes ont, ainsi, tudi comment les fourmis arrivent rsoudre collectivement des

problmes trop complexes pour un seul individu, notamment les problmes de choix lors de

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


36

lexploitation des sources de nourriture et ceci grce la phromone (substance leur

permettant de laisser une trace sur leur chemin), [Dorigo et al, 97].

Ces algorithmes ont donc pour but de reproduire le comportement naturel des fourmis pour

retrouver le meilleur chemin possible vers un objectif donn.

Lexemple prsent dans les figures 1.8, 1.9 et 1.10, montre la capacit de cet algorithme se

rapprocher de la solution optimale.

- Au dpart, les fourmis disposent dun chemin pour aller de leur nid, la fourmilire, la

source de nourriture, figure 1.8.

Figure 1. 8 - Dplacement des fourmis vers une source de nourriture

- Un obstacle est plac entre le nid et la source de nourriture, les fourmis vont alors

commencer par se sparer de part et dautre de lobstacle en dposant de la phromone

sur leur passage, figure 1.9. Les fourmis les plus rapidement arrives au nid, aprs avoir

visit la source de nourriture, sont celles qui ont emprunt les deux branches les plus

courtes laller et au retour. Ainsi la quantit de phromone prsente sur le plus court

trajet est plus importante que celle prsente sur le chemin le plus long.

Or, une piste prsentant une plus grande concentration en phromone, tant plus

attirante pour les fourmis, a donc une probabilit plus grande dtre emprunte [Tangour

et al, 09].

Figure 1. 9 - Dplacement des fourmis aprs placement d'un obstacle sur leur chemin

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


37

- Finalement la quantit de phromone sur le chemin le plus court fait que ce chemin finit

par tre emprunt par la plupart les fourmis, figure 1.10.

Figure 1. 10 - Choix du chemin le plus court par la plupart des fourmis

Les algorithmes doptimisation par essaim particulaire La mthode dOptimisation par Essaim Particulaire (OEP) a t propose en 1995 par James

Kennedy et Russel Eberhart [Kennedy et al, 95] qui cherchaient simuler la capacit des

oiseaux voler de faon synchrone et leur aptitude changer brusquement de direction, tout

en restant en formation optimale.

Le fonctionnement de lOEP fait quelle peut tre classe parmi les mthodes itratives

(approche progressive de la solution) et stochastiques (faisant appel au hasard) dans le but

damliorer la situation existante en se dplaant partiellement au hasard et partiellement

selon des rgles prdfinies, en vue datteindre la solution globale souhaite [Clerc et al, 08].

La mthode doptimisation par essaim particulaire, est une procdure de recherche base sur

une population dindividus, appels particules, qui changent leur position (tat) avec le temps.

Dans un systme dOEP, les particules se dplacent lintrieur dun espace de recherche.

Pendant le dplacement, chaque particule ajuste sa position selon sa propre exprience, et

selon l'exprience des particules voisines, se servant de sa meilleure position produite et de

celle de ses voisines. Ce comportement est semblable celui du comportement humain

consistant prendre des dcisions o les individus considrent leur exprience antrieure et

celle des personnes qui les entourent [Kennedy et al, 95]. LOEP peut ainsi combiner des

mthodes de recherche locale avec des mthodes de recherche globale (mtaheuristiques).

Mme si beaucoup de similitudes existent entre les mthodes volutionnaires et lOEP, cette

dernire se distingue par le fait qu'elle n'utilise pas l'oprateur de slection qui choisit les

individus gards dans la prochaine gnration.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


38

En effet, tous les membres de la population sont maintenus par le procd de recherche de

sorte que l'information soit toujours mise en commun entre les individus pour diriger la

recherche vers les meilleures positions trouves dans l'espace de recherche [Deroussi, 06].

Cette mthode est expose plus en dtails dans le troisime chapitre de ce mmoire.

I.8 - Position du problme La rsolution des problmes rencontrs pour la gestion de leur poste de production, constitue

une des principales proccupations des industriels. En effet, comment russir produire le

plus possible, le rapidement possible avec le moins de cot possible, le moins darrts

possible, le moins de personnel possible tout en respectant toutes les contraintes lies au

produit (prcdence, achvement, prissabilit, )?

Notre travail rentre dans ce cadre et consiste donc dvelopper des outils daide

lordonnancement permettant la gestion du poste de production et en particulier celui du

conditionnement au niveau des industries pharmaceutiques. Il sagit donc, de prendre en

considration les diffrentes contraintes relatives aux ressources et aux produits ncessaires

ainsi quau temps et ceci pour raliser une optimisation multi-objectifs reposant sur deux

objectifs principaux relatifs dune part la minimisation des cots de fabrication et aux cots

des temps engendrs par les oprations de nettoyage ainsi que les temps darrt et aux cots

de non utilisation des ressources, dautre part.

Pour cela, deux mthodes sont utilises et compares: les algorithmes gntiques et les

algorithmes doptimisation par essaim particulaire.

I.9 - Conclusion Aprs la prsentation des problmes dordonnancement et de leurs principales

caractrisations, diffrentes mthodes, exactes et approches, pouvant tre utilises pour la

rsolution de ces problmes sont introduites dans ce chapitre.

Parmi les mthodes exactes, nous avons distingu la programmations linaire, la

programmation dynamique et la mthode branch and bound.

Parmi les mthodes approches ou mtaheuristiques, nous avons prsent les mthodes de

recherche locale telles que le recuit simul ou la mthode de recherche tabou, et les mthodes

volutionnistes, telles que les algorithmes gntiques, les algorithmes de colonies de fourmis

ou les algorithmes doptimisation par essaim particulaire, rcemment proposs.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


39

La rsolution dun problme dordonnancement en industries pharmaceutiques par

lutilisation de la mthode des algorithmes gntiques est propose dans le prochain chapitre

et les rsultats obtenus seront compars avec ceux fournis par la mthode doptimisation par

essaim particulaire prsente dans le troisime chapitre.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011

Chapitre II Algorithmes gntiques pour la rsolution de problmes dordonnancement en industries pharmaceutiques

40

Chapitre II

Algorithmes gntiques pour la rsolution

de problmes dordonnancement

en industries pharmaceutiques

II.1 - Introduction

La rsolution de problmes doptimisation consiste, en rgle gnrale, dfinir une ou

plusieurs fonctions objectifs (fonctions cots) minimiser ou maximiser selon le type de

problme trait.

La dfinition du problme d'optimisation est souvent complte par la donne de contraintes

et toutes les solutions retenues doivent respecter ces contraintes, qui peuvent aussi tre vues

comme dfinissant l'espace de recherche [Clerc et al, 04].

Les mtaheuristiques permettent de trouver une ou plusieurs solutions proches de loptimum

pour des problmes d'optimisations, en tenant compte des fonctions objectifs dfinies. Le

principe d'une mtaheuristique est de minimiser ou de maximiser ces fonctions, de trouver un

minimum global un problme de minimisation et de ne pas rester bloqu sur un minimum

local.

Ainsi, les mtaheuristiques ont pour ambition commune de rsoudre au mieux les problmes

d'optimisation qualifis de difficiles.

Quelque soit la mthode utilise, le choix des critres optimiser continue poser de srieux

problmes. Dans une grande partie de la littrature, la rsolution des problmes

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


41

dordonnancement traite surtout le cas mono-objectif. Seulement, de nos jours, diffrents

objectifs peuvent tre pris en considration et grs simultanment pour une meilleure

optimisation [Chang et al, 07], [Saad et al, 06], [Tangour et al, 06].

Dans ce chapitre, un problme dordonnancement multi-objectifs dun atelier de

conditionnement de type flow-shop en industries pharmaceutiques est prsent. Les

diffrentes caractristiques et oprations le concernant sont introduites puis sa formulation et

sa rsolution par les algorithmes gntiques proposes.

II.2 - Ordonnancement en industries pharmaceutiques Pour pouvoir faire face la concurrence, les industries pharmaceutiques doivent maintenir un

taux de productivit en constante volution; des faiblesses peuvent toutefois apparatre au

niveau du systme de production et plus particulirement au niveau du poste de

conditionnement et engendrer des cots de production ainsi que des cots de non utilisation

relativement levs. Pour y pallier et rsoudre le problme dordonnancement au niveau de ce

poste, plusieurs mthodes doptimisation peuvent tre envisages, parmi lesquelles, on trouve

les algorithmes gntiques.

II.2.1 - Types de produits utiliss dans les industries pharmaceutiques

Pour obtenir la bote de mdicaments parvenant au consommateur, le produit passe par les

formes suivantes :

- les matires premires composes du principe actif (mlange ou compos extrait

dune substance vgtale, animale ou de synthse qui confre au mdicament son

action pharmacologique), de lexcipient (substance neutre dans laquelle est incorpor

un mdicament pour permettre son absorption) et parfois dun colorant,

- les produits semi-finis qui rsultent de la transformation des matires premires en

comprims ou en glules,

- les articles de conditionnement primaires, en contact direct avec le semi-fini, tels que

les bobines daluminium ou de PVC, et les articles de conditionnement secondaires

tels que les notices, les vignettes et les tuis en carton,

- les produits finis qui sont mis disposition du consommateur.

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


42

II.2.2 - Cheminement des produits au niveau des industries pharmaceutiques Les matires premires et les articles de conditionnement primaires et secondaires arrivent au

magasin et sont dposs dans une zone de rception, tiquets puis achemins vers une zone

de quarantaine en lattente dtre contrls par le service contrle qualit. Sils sont accepts,

les produits sont alors stocks dans une zone portant la mention accept avec une tiquette

avec la mme mention ; sinon, ils sont dposs dans une zone dite refus.

Suivant les plannings tablis, les matires premires et les articles de conditionnement sont

livrs par un magasinier au service production en vue dtre traits.

- Les matires premires, portant ltiquette accept, sont achemines vers le service

des formes solides.

- Les articles de conditionnement, portant ltiquette accept, sont, au besoin,

directement envoys au service conditionnement.

- Les produits semi-finis, rsultant de la transformation des matires premires au

niveau de latelier des formes solides, sont envoys, en fonction du planning, au

service conditionnement.

Aprs avoir t traits au service conditionnement, les produits finis rsultant de la

transformation des semi-finis et des articles de conditionnement, sont envoys au magasin, en

attendant dtre transmis aux particuliers (pharmaciens, dlgus mdicaux) ou aux hpitaux.

II.2.3 - Spcificits dun atelier de conditionnement

Un atelier de conditionnement de produits pharmaceutiques peut contenir une ou plusieurs

lignes de conditionnement automatique, qui sont exploites pour transformer les produits

semi-finis, en utilisant les articles de conditionnement, en produits finis.

Latelier tudi comporte :

o deux chanes de conditionnement automatique servant pour lemballage des comprims et glules,

o un tapis de conditionnement de produits, o une encartonneuse semi-automatique, o une ligne de vignettage plat des tuis, o un local de prparation, dans lequel on trouve une plieuse de notices et un local

doutillage,

tel-0

0577

101,

ver

sion

1 - 1

6 M

ar 2

011


43

o une laverie, o seffectuent le nettoyage du matriel et les tests dtanchit des blisters,

o une zone de pr-stockage de produits semi-finis et semi-conditionns.

II.2.4 - Lignes de conditionnement Au niveau de latelier considr, le conditionnement des comprims et des glules est effectu

essentiellement sur deux lignes de conditionnement.

Une ligne de conditionnement de comprims et de glules est constitue de quatre machines,

comme le montre la figure 2.1 : une blistreuse, une encartonneuse, une vignetteuse et une

fardeleuse [Boukef et al, 06].

o La blistreuse trate le film PVC en le passant sous une plaque chauffante, permettant de former de petites alvoles (thermoformage) qui sont alimentes par un chargeur

contenant les produits semi-finis. Une autre plaque chauffante a pour rle de sceller la

feuille daluminium au-dessus ; les blisters sont ensuite coups et envoys vers

lencartonneuse.

o Lencartonneuse reoit les quantits de blisters ncessaires selon le format et les introduit dans lemballage en mme temps que la notice.

o La vignetteuse reoit les blisters dans leurs botes et colle dessus une vignette imprime.

o La fardeleuse regroupe les produits finis en lots ; un oprateur humain se charge de remplir les caisses avec le nombre de produits finis, fix lavance.

Pour chacune des lignes d

Documents

l’ordonnancement d’ateliers job-shop flexibles