Problématiques d'ordonnancement et de planification pour un système de production de shampoings

Cédric Mocquillon

Description

Sous la direction de Vincent T'Kindt
Thèse soutenue le 16 janvier 2009: Tours
Les systèmes de production représentent un domaine privilégié d’application des techniques issues de la recherche opérationnelle. Organiser le flux de produit dans un tel système est une tâche complexe : le nombre de contraintes à prendre en compte est généralement élevé et les données peuvent s’avérer être incertaines (il est difficile de connaître précisément la quantité de produit qui sera vendu dans plusieurs semaines ou plusieurs mois). Pour pouvoir organiser efficacement le flux de produit, l’organisation du flux est scindé en trois phases distincts : la phase stratégique, la phase de planification et enfin la phase opérationnelle. Cette thèse porte sur l’étude des deux dernières phases pour un site de production de shampoings.
-Reordonnancement
Systems of production represent a privileged area of application of techniques from operational research. Organizing the product flow in such a system is a complex task : the number of constraints to take into account is generally high and the data can be uncertain (it is difficult to know precisely the amount of product that will be sold in several weeks or months). To be able to effectively organize the product flow, the organization is divided into three distinct phases : the strategic phase, the planning phase and operational phase. This thesis focuses on the last two phases for a shampoo production site.
Source: http://www.theses.fr/2009TOUR4034/document

Informations

• Publié par: Thesee
• Nombre de lectures: 54
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

UNIVERSITÉ
FRANÇOIS-RABELAIS
DE TOURS
École Doctorale : Santé, Sciences et Technologies
Équipe Ordonnancement et Conduite du Laboratoire d’Informatique de Tours
THÈSE présentée par :
Cédric MOCQUILLON
soutenue le : 16 Janvier 2009
pour obtenir le grade de : Docteur de l’université François - Rabelais
Discipline : Informatique
PROBLEMATIQUES D’ORDONNANCEMENT ET DE
PLANIFICATION POUR UN SYTEME DE PRODUCTION DE
SHAMPOINGS
THÈSE dirigée par :
T’Kindt Vincent Professeur, Université François-Rabelais de Tours
RAPPORTEURS :
Dauzère-Pérès Stéphane Professeur, Ecole des Mines de Saint Etienne
Gourgand Michel Professeur, Université Blaise Pascal de Clermont-Ferrand
JURY :
Aloulou Mohamed Ali Maitre de conférence, Université Paris Dauphine
Dauzère-Pérès Stéphane Professeur, Ecole des Mines de Saint Etienne
Gourgand Michel Professeur, Université Blaise Pascal de Clermont-Ferrand
Hoogeveen Han Maitre de conférence, Université d’Utrecht
Lenté Christophe dece, Université François-Rabelais de Tours
Penz Bernard Professeur, Institut national polytechnique de Grenoble
T’Kindt Vincent Université François-Rabelais de ToursRemerciements
Je tiens ici à remercier mes encadrant de thèse : Vincent et Christophe pour m’avoir
soutenu au long de ces trois années et surtout pour m’avoir permis de réaliser cette thèse
dans les meilleures conditions possibles tant d’un point de vue scientifique que d’un point
de vue plus matériel. Je tiens également à remercier les membres de mon jury de thèse
et tout particulièrement Mr Dauzères-Pérès et Mr Gourgand d’avoir accepté d’être mes
rapporteurs.
Enfin, je remercie Mr Mathis de m’avoir permis tout en finançant ma thèse de doctorat
de travailler sur des problématiques originales de transport par approche multi-agents.
A titre plus personnel, je remercie Hélène et Ben pour les soirées passées ensemble, les
débats passionnés que nous avons eu et pour leur ouverture d’esprit.
Merci également à Steph pour m’avoir obligé à retirer mes «oeillères». Il est pour moi
un exemple de chercheur passionné. A titre plus personnel je le remercie pour ses efforts
en cuisine même s’il n’est toujours pas entré dans le top 10! Merci enfin de m’avoir imposé
d’être dans ton équipage! Arittake no yume wo kakiatsume!
Bon courage à vous trois pour vos soutenances respectives!
Merci enfin à Karine de m’avoir soutenu tout au long de ces trois années, même dans
les moments les plus difficiles. Merci à elle d’avoir assisté à mes nombreuses répétitions de
soutenance, d’avoir relu mon manuscrit et tout simplement d’avoir été là. Enfin et surtout,
merci, merci à elle d’avoir supporté Steph!
3REMERCIEMENTS
4Résumé
Les systèmes de production représentent un domaine privilégié d’application des tech-
niques issues de la recherche opérationnelle.
Organiser le flux de produit dans un tel système est une tâche complexe : le nombre de
contraintes à prendre en compte est généralement élevé et les données peuvent s’avérer être
incertaines (il est difficile de connaître précisément la quantité de produit qui sera vendu
dans plusieurs semaines ou plusieurs mois). Pour pouvoir organiser efficacement le flux de
produit, l’organisation du flux est scindé en trois phases distincts : la phase stratégique,
la phase de planification et enfin la phase opérationnelle. Cette thèse porte sur l’étude des
deux dernières phases pour un site de production de shampoings.
Le premier chapitre porte sur les rappels de la théorie de la complexité, il aborde
également les différentes méthodes utilisées en recherche opérationnelle pour la résolution
de problèmes combinatoires.
Le second chapitre présente l’organisation du site de production. Après avoir détaillé
le fonctionnement des différents services du site de production, nous présentons les problé-
matiques de planification et d’ordonnancement de la société.
Le troisième chapitre présente les méthodes de résolution que nous avons mis en place
pour résoudre le problème de planification de la société. Dans un premier temps, nous
présentons la modélisation mathématique du problème de planification. Cette première
phase permet de bien identifier l’ensemble des données et contraintes à respecter et per-
met également de construire un programme linéaire en nombres mixtes. Nous présentons
ensuite l’heuristique que nous avons développée. Cette heuristique est basée sur un algo-
rithme glouton à priorité dynamique. La priorité est déterminée par la résolution d’un sous
problème appelé « problème de déploiement ». Nous démontrons que ce sous problème
peut se ramener à la recherche d’un flot maximum à coût minimum avec borne supérieure
de capacité et est donc résolu polynomialement. Nous concluons ce troisième chapitre par
une comparaison entre l’heuristique développée et la résolution du programme linéaire en
nombres mixtes par le solveur commercial ILOG Cplex.
Le quatrième et dernier chapitre porte sur les problématiques d’ordonnancement court
terme et très court terme du site de production. Dans un premier temps, nous présentons
une modélisation mathématique du problème d’ordonnancement court terme de la société.
La problématique d’ordonnancement court terme est résolue par une adaptation de
l’heuristique présentée lors du précédent chapitre. Les problématiques d’ordonnancement à
très court terme de la société sont modélisées par des problèmes de réordonnancement. Un
ensembled’algorithmessontprésentés,permettantderésoudrepolynomialementdifférentes
5RÉSUMÉ
versions du problème d’ordonnancement très court terme.
Mots clés : Recherche Opérationnelle, Planification de la production, Ordonnancement,
Réordonnancement
6RÉSUMÉ
7RÉSUMÉ
8Abstract
Systems of production represent a privileged area of application of techniques from ope-
rational research. Organizing the product flow in such a system is a complex task : the
number of constraints to take into account is generally high and the data can be uncertain
(it is difficult to know precisely the amount of product that will be sold in several weeks
or months). To be able to effectively organize the product flow, the organization is divided
into three distinct phases : the strategic phase, the planning phase and operational phase.
This thesis focuses on the last two phases for a shampoo production site.
The first chapter deals with reminders of the theory of complexity; it also addresses
the various methods used in operational research to solve combinatorial problems.
The second chapter presents the organization of the production site. We first detailed
the functioning of the different departments of the production site. We secondly present
the problems of planning and scheduling of company.
The third chapter presents the methods that we have developed to solve the production
planning problem of the company. In a first step, we present the mathematical model of
the production planning problem.
This first phase allows us to identify all data and constraints that we have to answer
and also helps us to build a mixed integer programming model. We then present the
heuristic that we have developed. This heuristic is based on a greedy algorithm with a
dynamic priority. The priority is determined by solving a problem known as « deployment
problem ». We demonstrate that this sub-problem can be reduced to look for a maximum
flow at minimum cost with an upper bound of capacity and is therefore a polynomial
problem. We conclude this third chapter by a comparison between the heuristic resolution
and the mixed integer programming model solved by ILOG Cplex.
The fourth and last chapter focuses on the short-term and very short-term scheduling
problems of the production site. In a first step, we present a mathematical model of the
short term scheduling problem. This problem is solved by an adaptation of the heuristic
previously presented. The scheduling problems in the very short term of company are
modeled by rescheduling problems. A set of algorithms are presented, to solve different
versions of very short term scheduling problem.
Keywords : Operation Research, Production Planning, Scheduling, Rescheduling
9ABSTRACT
10