[PDF] Perfectionnement de métaheuristiques pour loptimisation continue

View - Download Perfectionnement de métaheuristiques pour loptimisation continue

Previous PDF

Next PDF

M´etaheuristiques

Strat

´egies pour l"optimisation

de la production de biens et de servicesMarc Sevaux

Num´ero d"ordre : 04/03

HABILITATION`ADIRIGER DESRECHERCHES

Pr ´epar´ee au Laboratoire d"Automatique, de M´ecanique d"informatique

Industrielles et Humaines du CNRS (UMR CNRS 8530)

dans l"

´equipe Syst`emes de Production

Marc Sevaux

M

´etaheuristiques

Strat´egies pour l"optimisation

de la production de biens et de services Soutenue le 1erJuillet 2004 devant le jury compos´e de : Pr

´esident Prof. Christian Prins

Rapporteurs Prof. Michel Gourgand

Prof. Jin-Kao Hao

Prof. Eric Taillard

Examinateurs Prof. St

´ephane Dauz`ere-P´er`es

Prof. Bernard Grabot

Directeur Prof. Christian Tahon

Table des mati`eresRemerciements5

I Curriculum Vitae7

1 Informations g´en´erales9

1.1 Etat Civil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Fonction actuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Prime d"encadrement doctorale et de recherche . . . . . . . . . . . . 9

1.4 Parcours et formation . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Enseignement12

2.1 Enseignements

`a l"UVHC . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Enseignements avant l"int

´egration`a l"UVHC . . . . . . . . . . . . . 15

2.3 Encadrements p

´edagogiques . . . . . . . . . . . . . . . . . . . . . . 16

2.4 Administration de l"enseignement . . . . . . . . . . . . . . . . . . . 18

3 Supervision de travaux d"´etudiants 2

eet 3ecycle 20

3.1 Th

`eses de doctorat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 M ´emoires de DEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3 Projets de DESS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.4 Projets IUP GEII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Administration et animation de la recherche 24

4.1 Animation de la recherche . . . . . . . . . . . . . . . . . . . . . . . . 24

4.2 Organisation de manifestations

`a Valenciennes . . . . . . . . . . . . 25

4.3 Organisation de manifestations en dehors de Valenciennes . . . . . 25

4.4 Organisation / pr

´esident de sessions . . . . . . . . . . . . . . . . . . 26

5 Visibilit´e, rayonnement et autres activit´es 27

5.1 Collaborations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.2 Appartenance

`a des soci´et´es et des groupes de recherche . . . . . . 28

5.3 Fonction d"

´edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.4 Evaluation de la recherche . . . . . . . . . . . . . . . . . . . . . . . . 31

6 Contrats, projets et financements33

6.1 Contrats industriels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6.2 Projets de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.3 Financements obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . 35

1

Table des mati`eres

7 Th´ematiques de recherche36

7.1 Planification de la production . . . . . . . . . . . . . . . . . . . . . . 38

7.2 Ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

7.3 Tourn

´ees de v´ehicules . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7.4 Autres approches ou probl

´ematiques . . . . . . . . . . . . . . . . . . 43

8 Liste des publications48

II Synth`ese scientifique55

1 Introduction g´en´erale57

1.1 Pourquoi les m

´etaheuristiques? . . . . . . . . . . . . . . . . . . . . . 57

1.2 Intensification et diversification . . . . . . . . . . . . . . . . . . . . . 57

1.3 Techniques de r

´esolution pratique . . . . . . . . . . . . . . . . . . . 58

2 M´ethodes de recherche locale59

2.1 M ´ethodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.2 Recuit simul

´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

2.3 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.4 Recherche

`a voisinages variables . . . . . . . . . . . . . . . . . . . . 66

2.5 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

2.6 Iterated local search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.7 Guided local search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

2.8 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3 M´etaheuristiques `a base de population 71

3.1 Algorithmes g

´en´etiques . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.2 Algorithmes de colonies de fourmis . . . . . . . . . . . . . . . . . . 75

3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4 M´etaheuristiques avanc´ees79

4.1 Algorithmes m

´em´etiques . . . . . . . . . . . . . . . . . . . . . . . . 79

4.2 Scatter search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.3 GA|PM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5 Compl´ements89

5.1 R ´eglages automatiques des param`etres . . . . . . . . . . . . . . . . 90

5.2 Robustesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.3 Optimisation multiobjectif . . . . . . . . . . . . . . . . . . . . . . . . 92

5.4 Optimisation continue . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6 Conclusions93

2

Table des mati`eres

7 Perspectives de recherche96

R´ef´erences99

III S´election de publications 109

1 European Journal of Operational Research (2003) 111

2 4OR (2004 `a paraˆıtre)112

3 Journal of Heuristics (2004 soumis)112

4 Computers and Operations Research (2004 `a paraˆıtre) 113

5 Naval Research Logistics (2003)113

3 4

Remerciements

La r ´edaction de ce manuscrit est l"aboutissement de plusieurs ann´ees de tra- vail. Ce travail lui-m ˆeme n"aurait puˆetre men´e sans l"aide de plusieurs personnes auxquelles je souhaite exprimer ma gratitude. Avant tout, je remercie les rapporteurs de cette dissertation, Michel Gourgand,

Jin-Kao Hao et Eric Taillard, qui ont s

ˆurement pass´e de longues heures`a relire et corriger ce document. Que les autres membres du jury soient aussi remerci

´es.

Mes remerciements vont

`a la direction du LAMIH pour son accueil, et aussi a l"ensemble de l"´equipe “Syst`emes de Production" et sa bonne ambiance, ainsi qu" `a Christian Tahon, son responsable, pour m"avoir fait confiance et donn´e une grande libert

´e d"action ces derni`eres ann´ees.

Je tiens

`a exprimer ma gratitude tout particuli`erement`a Christian Prins, qui a et´e mon professeur il y a de nombreuses ann´ees et qui a´eveill´e en moi le goˆut et la passion de la recherche. Je lui suis aussi reconnaissant pour les nombreuses dis- cussions productives, pour cette collaboration que nous avons entam

´ee depuis la

fin de ma th `ese et enfin, pour avoir transform´e au fil des ann´ees notre partenariat en amiti

´e sinc`ere.

Que St

´ephane Dauz`ere-P´er`es, mon directeur de th`ese soit aussi remerci´e cha- leureusement; sous sa direction de 1996 `a 1998, j"ai pu comprendre et apprendre le m ´etier de chercheur et une certaine´ethique de la recherche. Son amiti´e a heu- reusement d

´epass´e cette p´eriode.

´eslarechercheop´erationnelle

avec passion, Eric Pinson, Philippe Chr

´etienne, Jacques Carlier et Claude Berge

ainsi que les personnes qui ont su m"aider quand j"en avais besoin, Philippe Tho- min, Alain Gibaud, tout particli `erement Xavier Gandibleux et bien d"autres.

Je garde une place de choix pour Kenneth S

¨orensen, pour tout ce que nous

avons cr ´e´e et partag´e ensemble, pour notre amiti´e; le groupe EU/ME n"´etant que la partie

´emerg´ee de l"iceberg...

Enfin je tiens

`a terminer cette pr´eface en remerciant de tout coeur mon´epouse Sandrine et mes enfants, Victoria, Franc¸ois et Jean pour leur patience pendant mes nombreuses absences et pour leur amour sans limite.

Marc Sevaux

Valenciennes, Mai 2004

5 6

Premi`ere partie

Curriculum Vitae

8

1 Informations g´en´erales

1.1 Etat Civil

NOM, Pr´enom SEVAUX, Marc

Date et lieu

de naissanceN

´e le 25 mai 1969`a Brest (29)

Nationalit

´e Franc¸aise

Etat civil Mari

´e, trois enfants

Service militaire effectu

´e en 1995-1996, en tant qu"officier du corps tech- nique et administratif du service de sant

´e des arm´ees.

1.2 Fonction actuelle

Poste Maˆıtre de conf´erences (classe normale) en 61 esection du CNU

Adresse

professionnelleUniversit

´e de Valenciennes et du Hainaut-Cambr´esis

UMR CNRS 8530, LAMIH / SP

Le Mont Houy, B

ˆatiment Jonas 2

F-59313 Valenciennes Cedex 9

France

T

´el´ephone 03 27 51 13 26

Fax 03 27 51 13 10

EmailMarc.Sevaux@univ-valenciennes.fr

Urlhttp ://www.univ-valenciennes.fr/sp/sevaux/

Facult

´e de rattachementInstitut universitaire de technologie D´epartement Organisation et G´enie de la Production (OGP) d´elocalis´e`a Cambrai

Laboratoire

de rattachementLAMIH/SP : Laboratoire d"Automatique, de M

´ecanique,

d"Informatique industrielles et Humaines - UMR CNRS

8530 - Equipe Syst

`emes de Production

1.3 Prime d"encadrement doctorale et de recherche

Titulaire de la prime d"encadrement doctorale et de recherche (PEDR) depuis 2003. 9

1 Informations g´en´erales

1.4 Parcours et formation

Depuis Sept. 99Maˆıtre de conf´erences en 61esection`a l"universit´e de Valen- ciennes et du Hainaut-Cambr ´esis. Titulaire d"un poste`a l"Institut Univer- sitaire de Technologie, au d ´epartement Organisation et G´enie de la Produc- tion, d

´elocalis´e`a Cambrai.

D´ec. 98 - Aoˆut 99Ing´enieur de recherche (contrat`a dur´ee d´etermin´ee de 9 mois)

aud Charg ´e de la r´edaction d"un cahier des charges pour la cr´eation d"une plate- forme logistique (voir section 6.2).

1996 - 1998Universit´e Pierre et Marie Curie, Paris

Doctoratde l"Universit´e Pierre et Marie Curie (Paris VI). Sp ´ecialit´eInformatique et Recherche Op´erationnelle.

Laboratoire

d"accueilEcole des Mines de Nantes, d´epartement Automatique et Productique.

Soutenance le 11 D

´ecembre 1998`a l"universit´e Pierre et Marie Curie (Paris VI).

SujetEtude de deux probl`emes d"optimisation

en planification et ordonnancement. Pr´esident du JuryP. Chr´etienne (Professeur, Universit´e P. et M. Curie, Pa- ris). RapporteursY. Crama (Professeur, Universit´e de Li`ege, Belgique),

J.B. Lasserre (Directeur de Recherche, LAAS/CNRS,

Toulouse)

ExaminateursM.-C. Portmann (Professeur, Ecole des Mines de

Nancy), C. Prins, (Ma

ˆıtre Assistant, HDR, Ecole des

Mines de Nantes), S. Dauz

`ere-P´er`es (Maˆıtre Assistant, HDR, Ecole des Mines de Nantes,Directeur de th`ese).

Etude de deux probl

`emes d"optimisation en planification et ordonnance- ment (probl `eme de planification de la production en temps continu et pro- bl `eme g´en´eral d"ordonnancement`a une machine). R´esolution par l"utilisa- tion de techniques de recherche op

´erationnelle. Validation par le d´evelop-

pement de logiciels prototypes. 10

1.4 Parcours et formation

1994 - 1995Universit´e Pierre et Marie Curie, Paris

Diplˆome d"Etudes Approfondiesde l"Universit´e Pierre et Marie Curie (Pa- ris VI). Sp ´ecialit´e Informatique et Recherche Op´erationnelle

Mention Bien

ResponsablePh. Chr´etienne (Professeur, Universit´e Pierre et Marie

Curie, Paris)

Sujet de DEALes probl`emes d"ordonnancement avec d´elais de com- munication EncadrementC. Picouleau (Maˆıtre de Conf´erences, CNAM, Paris).

1992 - 1994Institut de Math´ematiques Appliqu´ees (IMA), Angers

Dipl

ˆomes

obtenusDEUG, Licence, Maˆıtrise Sp ´ecialit´e Math´ematiques Appliqu´ees et Sciences Sociales 11

2 Enseignement

2 Enseignement

2.1 Enseignements `a l"UVHC

R´ecapitulatif des heures enseign´ees `a l"UVHC

Le tableau ci-dessous r

´esume les heures d"enseignement depuis le recrute- ment `a l"universit´e de Valenciennes et du Hainaut-Cambr´esis. Le descriptif des mati `eres enseign´ees est pr´esent´e apr`es le tableau. Dans ce tableau, sont reprises les heures de cours magistraux (CM), de travaux dirig

´es (TD) et de travaux pra-

tiques (TP), ainsi que l" ´equivalence en heures TD (EqTD). L"IUT permet aussi de comptabiliser certaines heures pour des t

ˆaches administratives (Responsabilit´e

des projets, Relations internationales), ainsi que des heures pour l"encadrement des stages et des projets. Ann

´ee 2003-2004 Niveau CM TD TP EqTD

Recherche Op´erationnelle IUT 2 et APPC 20h 2×40h - 110h

Informatique IUT 1 15h 2×20h 62.5h

Responsabilit

´e de relations Internationales 10h 6.67h

Heures de stages et projets entrant dans le d

´ecompte du service 13h

Total ann´ee 2003-2004192.17h

Ann´ee 2002-2003 Niveau CM TD TP EqTD

Recherche Op´erationnelle IUT 2 et APPC 20h 2×40h - 110h

Informatique IUT 1 15h 2×14h 12h 58.5h

Math ´ematiques de la d´ecision ISTV Master Info. 1 12h - - 18h

Responsabilit

´e des projets15h 10h

Heures de stages et projets entrant dans le d

´ecompte du service 29h

Total ann´ee 2002-2003225.5h

Ann´ee 2001-2002 Niveau CM TD TP EqTD

Recherche Op´erationnelle IUT 2 et APPC 20h 2×40h - 110h

Informatique IUT 1 15h 1×24h 20h 59.83h

Programmation lin

´eaire EIGIP 2 - 1×18h - 18h

Responsabilit

´e des projets15h 10h

Heures de stages et projets entrant dans le d

´ecompte du service 19.5h

Total ann´ee 2001-2002217.33h

Ann´ee 2000-2001 Niveau CM TD TP EqTD

Recherche Op´erationnelle IUT 2 et APPC 20h 3×40h - 150h

Informatique IUT 1 - 1×25h - 25h

Programmation lin

´eaire EIGIP 2 - 1×18h - 18h

Heures de stages et projets entrant dans le d

´ecompte du service 27h

Total ann´ee 2000-2001220h

Ann´ee 1999-2000 Niveau CM TD TP EqTD

Qualit´e IUT 1 30h 1×30h - 75h

Recherche Op

´erationnelle IUT 2 - 1×40h - 40h

Informatique IUT 1 - 1×25h 2×25h 58.3h

Heures de stages et projets entrant dans le d

´ecompte du service 19.5h

Total ann´ee 1999-2000192.83h

12

2.1 Enseignements `a l"UVHC

Descriptif des interventions `a l"UVHC

La ligne “# heures" correspond aux heures affect

´ees`a ce module pour les

etudiants. Pour les heures d"intervention me concernant, se reporter au tableau.

M17 - Alg`ebre et recherche op´erationnelle

# heures CM 20h, TD 40h.

Public IUT OGP 2 et APPC

Lieu IUT OGP Cambrai

Ann´ee(s) depuis 1999

Responsabilit

´e responsable du module depuis 2000

-Objectifs du cours :Donner`a l"´etudiant les principaux outils de la re- cherche op ´erationnelle pour lui permettre d"optimiser les fonctions de production et de logistique principales en entreprise. Acqu

´erir les con-

nais sances de base en alg `ebre pour une poursuite d"´etude´eventuelle. -Contenu du cours :Alg`ebre lin´eaire (bases de l"alg`ebre, inversion de ma- trices); introduction `a la recherche op´erationnelle (historique, princi- pales d ´efinitions et termes de la recherche op´erationnelle); th´eorie des graphes; algorithmique des graphes (plus courts chemins, flot maxi- mum, probl `emes de transport); notions de programmation lin´eaire (mod ´elisa tion math´ematique, propri´et´es et th´eorie de la programma- tion lin ´eaire); r´esolution graphique et alg´ebrique; applications indus- trielles de la recherche op

´erationnelle (gestion de production, ordon-

nancement, MRP, logistique); cas particuliers de la programmation li- n´eaire (matrice de contraintes totalement unimodulaires); langages de mod ´elisation ( apprentissage par l"exemple, principaux mod`eles ren- contr ´es en industrie de production, r´esolution de cas industriels avec Xpress-IVE de Dash Associates); mise en place d"un challenge depuis

2001 pour les

´el`eves avec points de bonification pour les meilleurs r

´esultats obtenus.

-Notation :une note de TD refl´etant le travail pratique en continu, un de- voir maison, deux devoirs surveill

´es d"une heure, un devoir final de

deux heures.

M9 - Informatique

# heures CM 15h, TD 24h, TP 20h.

Public IUT OGP 1

Lieu IUT OGP Cambrai

Ann´ee(s) depuis 1999

Responsabilit

´e responsable du module depuis 2001

-Objectifs du cours :Donner aux´etudiants les moyens d"utiliser l"informa- tique de mani `ere avanc´ee. Enseigner les bases de la programmation structur

´ee.

-Contenu du cours :Introduction`a l"informatique et`a la bureautique (trai- tement de texte, tableur); introduction `a la programmation structur´ee 13

2 Enseignement

(arbres programmatiques, langagestructur´e de4eg´en´eration, concepts fonctions, proc ´edures); construction de macros´evolu´ees en VBA; con- ception objet; algorithmique g

´en´erale; mise en place de projets infor-

matiques (depuis 2001) pour la construction d"application VBA com- pl `etes et utiles`a un technicien OGP (un projet guid´e, un projet libre);

´ecup´eration

de donn ´ees,´ecriture dans des feuilles de calcul, manipulation des ob- jets Excel en VBA). -Notation :deux devoirs surveill´es d"une heure, un interrogation indivi- duelle sur ordinateur, deux notes de projets.

MD - Math´ematiques de la d´ecision

# heures CM 12h, TD 18h, TP 6h.

Public Master Informatique 1

Lieu ISTV Valenciennes

Ann´ee(s) 2002-2003

Responsabilit

´e responsable du module

-Objectifs du cours :Enseigner`a l"´etudiant les outils math´ematiques n´eces- saires `a la r´esolution de probl`emes dans le cadre de l"aide`a la d´ecision. -Contenu du cours :Introduction g´en´erale`a la programmation math´emati- que (r ´esolution lin´eaire, r´esolution enti`ere, branch and bound en pro-quotesdbs_dbs11.pdfusesText_17

[PDF] exercice corrigé mmc pdf

[PDF] exercice corrigé modulation d'amplitude pdf

[PDF] exercice corrigé moment de force

[PDF] exercice corrigé mouvement d un projectile pdf

[PDF] exercice corrigé mouvement d'un projectile

[PDF] exercice corrigé offre et demande

[PDF] exercice corrigé onduleur monophasé

[PDF] exercice corrigé onduleur triphasé

[PDF] exercice corrigé p2 bts cgo

[PDF] exercice corrigé peps

[PDF] exercice corrigé perceptron monocouche

[PDF] exercice corrigé pic 16f877

[PDF] exercice corrigé pont tout thyristor

[PDF] exercice corrigé portique isostatique

[PDF] exercice corrigé poutre hyperstatique