|
Dedicaces
ÈÓã
Çááå
ÇáÑÍãÇä
ÇáÑÍíã
A mon père Ahmed et A ma mère
Najwa
Auxquels je dois ce que je suis. Que dieu vous
protège.
A mon frère Fathi & A ma soeur
Hend
Qu'ils trouvent dans ce mémoire l'expression de mes
remerciements les plus sincères.
Meriem
Dedicaces
Je dédie ce travail :
A mes chers parents Samir et Amel
Ceux qui ont toujours veillé à mon bien
être : Pour leur soutien, leur patience, leurs conseils
Et leurs encouragements continus.
Que ma réussite leur soit un prix de
reconnaissance.
A mes chers frères Amir et Mohamed
Pour leurs encouragements, leurs conseils et leur
assistance morale.
A mon oncle Majid,
ma tante Zaineb
et mes cousins
Nader et Nahed
Pour leur soutien tout au long mes études
supérieurs, leurs encouragements et leurs conseils
A mon cher mari
Brahim
pour son aide, son soutien morale, ses conseils et ses sacrifices
le long
de ma formation.
A toute la famille
Zghidi .
A toute la famille
Ben Jamâa.
A tous mes amis et à ceux qui m'ont apporté leur
aide afin de mener à bien ce travail.
Imen
REMERCIEMENTS
C'est avec un grand plaisir que nous réservons
ces lignes en signe de gratitude et de reconnaissance à tous ceux qui
ont contribué de prés ou de loin à l'élaboration de
ce travail.
Tout d'abord, nous adressons nos plus vifs
remerciement à monsieur Anis Allouche pour son aide, sa grande
assistance et ses conseils judicieux qui ont conduit à la bonne
réalisation de ce travail.
Nous tenons à témoigner nos profondes
reconnaissances envers nos professeurs et enseignants pour la qualité
de la formation et l'encadrement dont ils nous ont fait
bénéficie
Notre gratitude et nos remerciements s'adressent aussi
à tous les membres du jury qui ont bien voulu accepter d'évaluer
ce travail.
SOMMAIRE
REMERCIEMENTS
3
SOMMAIRE
3
LISTE DES FIGURES :
3
INTRODUCTION
GÉNÉRALE :
3
CHAPITRE 1
3
ORDONNANCEMENT DE LA
PRODUCTION
3
1.1
INTRODUCTION :
3
1.2 DÉFINITION :
3
1.3 LA NOTION DE TÂCHE :
3
1.4 LA NOTION DE RESSOURCE :
3
1.5 TYPOLOGIE DES CONTRAINTES :
3
1.5.1 Contraintes de type potentiel :
3
1.5.2 Contraintes de type
cumulatif :
3
1.5.3 Contraintes de type
disjonctif :
3
1.6 LA NOTION D'OBJECTIFS ET DE
CRITÈRES :
3
1.7 LES POLITIQUES D'ORDONNANCEMENT :
3
1.8 LES TÂCHES D'ORDONNANCEMENT :
3
1.8.1 Ordonnancement statique :
3
1.8.2 Ordonnancement dynamique :
3
1.8.3 Ordonnancement
réactif :
3
1.9 CONCLUSION :
3
CHAPITRE 2
3
LES DIFFERENTES PROBLEME
D'ORDONNACEMENT
3
2.1 INTRODUCTION :
3
2. 2 LES PROBLÈMES D'ORDONNANCEMENT
D'ATELIER :
3
2.2.1 Ordonnancement à une
machine :
3
2.1.3 Ordonnancement à machines
parallèles :
3
2.1.4 ordonnancement en atelier sériel
(flow shop) :
3
2.1.5 Atelier général (job
shop) :
3
2.1.6 Atelier ouvert (open shop) :
3
2.2 L'ORDONNANCEMENT DU PROJET :
3
2.2.1 Le réseaux de PERT :
3
2.2.2 Le diagramme de GANTT :
3
2.3 CONCLUSION :
3
CHAPITRE 3
3
LES METHODES DE RESOLUTION DU PROBLEME
D'ORDONNACEMENT
3
3.1 INTRODUCTION :
3
3.2 LES ALGORITHMES EXACTES :
3
3.2.1 Programmation linéaire :
3
3.2.2 Programmation linéaire en nombre
entier :
3
3.2.3 Méthode de séparation et
d'évaluation ( branch&bound):
3
3.2.4 Programmation dynamique :
3
3.3 LES ALGORITHMES APPROCHÉS :
3
3.3.1 Heuristiques :
3
3.3.2 Métaheurestique :
3
3.4 CONCLUSION :
3
CHAPITRE 4
3
ETUDE DE CAS
3
4.1 DESCRIPTION DU PROBLÈME :
3
4.2 FORMULATION DU PROBLÈME :
3
4.3 EXEMPLE NUMÉRIQUE :
3
4.4 CONCLUSION :
3
CONCLUSION
GÉNÉRALE :
3
BIBLIOGRAPHIE
3
Liste des figures :
FIGURE 1 : STRUCTURE D'OBJECTIFS
[GRABOT 98]
3
FIGURE 2: UNE VISION AUTOMATICIENNE
D'UN ORDONNANCEMENT RÉACTIF
3
FIGURE 3 : ORDONNANCEMENT
À UNE MACHINE
3
FIGURE 4 : ORDONNANCEMENT
À MACHINES PARALLÈLES
3
FIGURE 5: PROBLÈME DE FLOW
SHOP
3
FIGURE 6 : JOB SHOP À 4
TRAVAUX ET 6 MACHINES
3
FIGURE 7: UNE TYPOLOGIE DES
PROBLÈMES D'ORDONNANCEMENT (D'APRÈS [BILLAUT99])
3
Introduction
générale :
Les problèmes d'ordonnancement jouent un rôle
important dans l'industrie manufacturière, dans le secteur des
services et dans notre vie quotidienne. En effet, comment organiser nos
rendez-vous afin de ne jamais arriver en retard, comment, lors d'un repas de
Ramadhan, gérer nos préparions pour pouvoir disposer de tous les
plats simultanément ou comment programmer tous les travaux d'une usine
pour optimiser l'occupation des machines et respecter les
échéances.
La résolution des problèmes d'ordonnancement
occupe la communauté scientifique vue leur complexité.
Les approches traditionnelles pour les résoudre
consistent à appliquer des techniques d'optimisation combinatoires
à une formulation analytique.
On étudie dans ce mémoire le problème de
« car- sequencing ».
Nous intéressons ainsi à une usine moderne de
voiture qui est composée de trois ateliers majeurs : l'atelier en
métal où le corps de la voiture est assemblé, l'atelier de
peinture où la voiture est peinte, et la chaîne de montage
où les équipements et les options de chaque véhicule sont
réglés. Le problème de
« car-sequencing » consiste à
déterminer l'ordre dans lequel une série de véhicules
devrait traverser ces trois ateliers.
Notre intérêt est porté sur l'atelier de
peinture. Dans ce contexte, notre objectif est de présenter une
méthode qui permet de minimiser le changement du couleur de la
peinture dans la séquence, dont la quelle on doit déterminer la
position de chaque voiture. Notons que une voiture peut avoir «
p » positions avant et après sa position initial.
Il faut citer que notre étude est essentiellement
appuie sur une seule machine qui peint les voitures qui sont de même
type, alors pour résoudre ce problème nous allons faire appel
à la programmation mathématique en nombre entier.
Il faut déterminer les variables nécessaires et
les contraintes qui permettent de résoudre le problème.
Notre travail est composé de quatre chapitres :
Le premier chapitre s'articule autour de l'ordonnancement de
la production .Nous présentons les définitions et les
différents concepts d'ordonnancement.
Dans le deuxième et le troisième chapitre nous
étudions les différents problèmes d'ordonnancement et les
méthodes de la résolution de ces problèmes.
Une illustration numérique sera présentée
dans le quatrième chapitre.
Dans ce contexte, nous utilisons la programmation
mathématique en nombre entier pour la résolution du
problème de « car -sequencing ».
CHAPITRE 1
ORDONNANCEMENT DE LA
PRODUCTION
1.1
1.7.1 Contraintes de type potentiel
Contraintes de type cumulatif
1.7.3 Contraintes de type
disjonctif
Les tâches de l'ordonnancement : un point
de vue technique
1.8.1Ordonnancement statique
1.8.2 Ordonnancement dynamique
1.8.3 Ordonnancement réactif
Chapitre2 :
2.1 Introduction
2.2 Les problèmes d'ordonnancement
d'atelier
2.2.1 Problème à une seule
machine
2.2.2Problème à machines
parallèles
2.2.3 Flow shop
2.2.4Job shop
2.2.5Open shop
2.4 Les problèmes d'ordonnancement de
projet
2.4.1 Réseau de PERT
2.4.2 Diagramme de GANTT
Chapitre 3 : Les méthodes de
résolution des problèmes d'ordonnancement :
3.1 Introduction
3.2 Les algorithmes exactes :
3.2.1 Programmation
linéaire
Modélisation
Résolution, méthode de simplexe
Dualité et analyse de sensibilité
3.2.2 Programmation linéaire en nombre
entière
3.2.3
Méthode de séparation et d'évaluation
3.2.4Programmation dynamique
3.3 Les algorithmes approchés :
Heuristique
3.3.2Mètaheurestique
Chapitre 1 :
Introduction :
La théorie d'ordonnancement est une branche de la
recherche opérationnelle, elle joue un rôle essentiel dans de
nombreux secteurs d'activités à savoir :
a) la conception (de bâtiment, de
produit, de systèmes ....)
b) l'administration (gestion d'emplois de temps, gestion
de personnelle ...) c) l'industrie (gestion de
production)
d) l'informatique (ordonnancement de
processus, ordonnancement de réseaux).
L'ordonnancement s'agit généralement d'organiser
dans le temps l'exécution des tâches soumises à des
contraintes de temps et de ressources, tout en satisfaisant au mieux un ou
plusieurs objectifs.
La fonction d'ordonnancement consiste à :
· Gérer les commandes enregistrées de
façon à prévoir les meilleurs délais et les
respecter.
· Gérer les stocks de façons à
optimiser leur niveau.
· Gérer les moyens en personnel et en
matériel, de façon à optimiser leur utilisation, à
éviter leur inoccupation comme leur sursaturation et minimiser les en
cours de fabrication.
1.2.1 Définition :
En gestion de production comme en gestion de projet,
l'ordonnancement joue un rôle privilégié, s'inscrivant dans
des niveaux de décisions à la fois tactique et
opérationnelle [Esquirol &Lopez 99, Giard 91].
L'ordonnancement est la programmation dans le temps de
l'exécution d'une série de tâches (ou activités,
opérations) sur un ensemble de ressources physiques (humains et
techniques).
Plusieurs définitions du problème
d'ordonnancement sont citées dans la littérature, nous indiquons
celle proposée dans [Esquirol&Lopez 99] :
« Le problème d'ordonnancement consiste
à organiser dans le temps la réalisation de tâches, compte
tenu de contraintes temporelles (délai, contraintes d'enchainement...)
et des contraintes portant sur l'utilisation et la disponibilité de
ressources requises. »
Le problème d'ordonnancement est défini comme
tout problème qui répond aux trois conditions suivantes :
§ Le mode de réalisation d'un projet :
Le projet peut prendre différentes natures comme :
construction d'un ensemble d'immeuble, d'un navire, d'un ouvrage d'art ;
production d'atelier de fabrication... ; élaboration d'emplois du
temps pour une session de congrès. Ce sont quelques exemples permettent
de mesurer l'intérêt de l'ordonnancement.
§ Le projet étudié est décomposable
en tâches :
La réalisation globale d'un projet nécessite
l'exécution de nombreuses opérations
élémentaires.
A titre d'exemple, la fabrication d'une voiture
nécessite pour chaque pièce, des opérations diverses
d'usinage, de fonderie puis de montages successifs jusqu'à la sortie
d'usine.
Une analyse plus ou moins détaillée
déterminera l'importance des tâches ; selon les cas, une
tâche sera une opération élémentaire ou un groupe
d'opérations élémentaires.
§ L'exécution des tâches est soumise
à des contraintes :
On désigne par contrainte la formulation
mathématique de certaines exigences imposées par :
° La main d'oeuvre : l'effectif de chaque
catégorie de main d'oeuvre disponible est limité.
° La technologie : une tâche ne peut
débuter que lorsque certaines autres ont été
réalisées.
°Le matériel : une machine ne peut
affecter qu'une tâche à la fois.
° Les fournisseurs : on ne peut commencer
certaines tâches que lorsque des livraisons ont été
effectuées.
° Les engagements commerciaux : certaines
tâches doivent être terminées avant un délai
fixé.
1.3 2.2 La notion de
tâche :
Une tâche i est une
entité élémentaire localisée dans le temps par une
date de début et une date de fin, dont la réalisation
nécessite une durée opératoire pi,
et qui consomme un moyen selon une certaine
intensité.
Selon le problème, les tâches peuvent êtres
exécutées par morceaux on parle alors de problèmes
préemptifs et dans ce cas la durée
pi d'une tâche ne peut être
déterminée qu'une fois l'ordonnancement est construit ;ou
doivent être exécutées sans interruption on parle alors de
problèmes non préemptifs.
Lorsque les tâches ne sont soumises à aucune
contrainte de cohérence, elles sont dites indépendantes.
1.4 2.3 La notion de
ressource :
La ressource est un moyen technique ou humain destiné
à être utilisé pour la réalisation d'une tâche
et disponible en quantité limitée.
Dans ce contexte on peut distinguer plusieurs types de
ressources à savoir :
Une ressource est renouvelable si après avoir
été allouée à une ou plusieurs tâches elle
est à nouveau disponible en même quantité (les hommes, les
machines, l'équipement en général) ; la
quantité de ressource utilisable à chaque instant est
limitée.
Dans le cas contraire, elle est consommable (matières
premières, budget) ; la consommation globale (ou cumul) au cours du
temps est limitée.
Une ressource est doublement contrainte lorsque son
utilisation instantanée et sa consommation globale sont limitées
(l'argent est un bon exemple).
Quelle que soit renouvelable ou consommable, la
disponibilité d'une ressource peut varier au cours du temps. Sa courbe
de disponibilité est en général connue a priori sauf dans
les cas où elle dépend du placement de certaines tâches
génératrices.
On distingue par ailleurs principalement dans le cas des
ressources renouvelables les ressources disjonctives qui ne peuvent
exécuter qu'une tâche à la fois (machine-outil, robot
manipulateur) et les ressources cumulatives qui peuvent être
utilisées par plusieurs tâches simultanément mais en
nombre limité (équipe d'ouvriers, poste de travail).
1.52.4 Typologie des
contraintes :
La notion générique de contrainte est relative
à un ensemble de variables de décision, elle exprime une
restriction sur les domaines de valeur de variables ; on peut distinguer
trois types de contraintes à savoir :
§ Contraintes de type potentiel ;
§ Contraintes de type cumulatif ;
§ Contraintes de type disjonctif ;
1.5.1 Contraintes de type
potentiel :
Nous regroupons sous ce vocable les contraintes temporelles
qui sont de deux sortes :
ü Contraintes de localisation temporelle : exprime
la localisation des tâches dans le temps.
Une tâche i ne peut être
débutée avant une date fixée l ;
par exemple ; une livraison ou une décision
administrative.
ti = l
ou une tâche i doit être
terminée avant une date fixée
l ; par exemple ; un
engagement commerciale.
ti =
l
ou enfin, une tâche i doit
être impérativement terminée à une date
fixée l sans avance ni retard .Cette
contrainte est la combinaison des deux contraintes
précédentes.
ti = l
ti =
l
ce qui implique : ti=l
ü Contraintes de succession temporelle :
Elles expriment la relation d'antériorité entre
les tâches, une telle tâche ne peut commencer avant la fin d'une
autre ; par exemple ; on ne coule pas des fondations si le
terrassement n'est pas fini.
Considérons deux tâches i
et j dont les époques de début
sont respectivement
ti et tj .Dire qu'il existe une
contrainte de succession entre les tâches i et
j consiste à limiter soit
inférieurement soit supérieurement l'intervalle de temps qui peut
s'écouler entre ti et tj, l'intervalle de temps
qui sépare ti et tj va être donc
borné inférieurement par une quantité que nous noterons
a, a pour indice i et
j pour monter qu'elle est liée au
couple ij pris dans cet ordre.
tj -ti =
aij
Les contraintes de type « potentiel » que nous
avons définies sont importantes car elles interviennent dans tout
problème d'ordonnancement.
1.5.2 Contraintes de type
cumulatif :
L'intervention des divers moyens (main d'oeuvre,
matériels ...) impose à l'ordonnancement des exigeons
différentes des contraintes de type potentiel.
Les matériels ou les machines alloués au projet
à ordonnancer ont des capacités fixées par leurs
performances.
D'une façon moins stricte, la main d'oeuvre disponible
est en général limitée .ces limitations se traduisent par
des contraintes cumulatives.
1.5.3 Contraintes de type
disjonctif :
Elles expriment le fait que deux tâches ne peuvent avoir
lieu en même temps sans que l'on puisse dire laquelle doit être
effectuée avant l'autre.
Considérons deux tâches
i et j, et supposons que
leur exécution nécessite l'emploie d'un matériel unique
(une grue, une machine -outil ...).les deux tâches ne pourront donc
être réalisées en même temps ; en d'autres
termes, les intervalles de temps : (ti,
ti+di) et (tj, tj+dj) ne
peuvent pas avoir une partie commune.
Les deux tâches iet
j seront dites en disjonction .Une telle contrainte
peut être formulée à l'aide de deux
inégalités de potentiel :
tj -ti
=di
ti-tj=dj
1.62.5 La notion d'objectifs et
de critères :
Les objectifs des entreprises sont diversifiés et le
processus d'ordonnancement est devenu de plus en plus multicritère. Les
critères que doivent satisfaire un ordonnancement sont variés.
D'une manière générale, on distingue
plusieurs classes d'objectifs concernant un ordonnancement [Esquirol&Lopez
99] :
§ Les objectifs liés au temps : on trouve par
exemple la minimisation du temps total d'exécution(C max), du
temps moyen d'achèvement, des durées totales de réglage ou
des retards par rapports aux dates de livraisons (L max ou T
max)
§ Les objectifs liés aux ressources :
maximiser la charge d'une ressource ou minimiser le nombre des ressources
nécessaires pour réaliser un ensemble des tâches.
§ Les objectifs liés au coût :
minimiser les coûts de lancement, de production, de stockage, de
transport, etc.
§ Les objectifs liés à une énergie
ou un débit.
Un critère est dit régulier si on ne peut pas le
dégrader en avançant l'exécution d'une tâche.
Les critères liés au temps Cmax ou L
max, sont par exemple réguliers par contre la plupart des
critères liés aux coûts ou aux ressources ne sont pas
réguliers.
La figure (1) suivante représente une structure
d'objectif qui permet de gérer les objectifs globaux de l'entreprise
Satisfaire les objectifs
Satisfaire les objectifs externes
Satisfaire les objectifs internes
Respecter
la qualité
Optimiser une
opération
Respecter les dates
de livraison
Respecter
la quantité
Optimiser le procédé
de fabrication
Maximiser
l'utilisation
d'une machine
Maximiser
la disponibilité
d'une machine
Optimiser
le flux
Maximiser les
performances
d'une machine
Minimiser
les stocks
Minimiser le
temps d'attente
Minimiser le
temps de cycle
Optimiser
l'utilisation
des ressources
Éviter les
rebuts
Éviter les
retouches
Minimiser le
niveau d'en- cours
Minimiser les temps
de préparation
Équilibrer la charge
des ressources
Minimiser le stock
de produits finis
Minimiser le stock de
matières premières
Figure 1 : Structure d'objectifs [Grabot 98]
1.7 2.6 Les politiques
d'ordonnancement :
On désigne par politique d'ordonnancement du processus
la règle de sélection de la prochaine tâche
exécutable (éligible ou activable).
On distingue plusieurs règles ou politiques
d'ordonnancement dans les systèmes temps réel comme par exemple
[Rus 93] :
§ Cyclique : tous les processus
s'exécutent périodiquement dans le cadre d'une
période commune et de façon non interruptible.
§ Echéance monotone : les
processus sont exécutés de façon préemptible avec
des priorités basées sur des échéances fixes.
§ Taux monotone : l'ordonnancement
est préemptif et les processus ont des poirotés basées sur
des taux d'utilisation du processus ou sur des périodes.
§ Échéance précoce en
premier : (EDF : earliest deadline
first)
Ordonnancement préemptif, où l'affectation
dynamique des priorités aux processus est basée sur la
proximité des échéances courantes.
§ Plus petit délais restant en
premier : ordonnancement préemptif, où les
processus sont assignés dynamiquement avec des priorités
basées sur l'entité du temps restant entre le temps
nécessaire pour compléter le travaille et l'heure (date)
d'échéance (urgence découlant du temps restant avant
échéances).
1.82.7 Les tâches
d'ordonnancement :
L'ordonnancement de tâches dans un atelier de production
est une fonction-clé de la gestion de production faisant le lien entre
les décisions stratégiques et tactiques (planification) et les
décisions opérationnelles (conduites en temps réel,
supervision) (Blondel ,1999 ; Lopez, Haudot, Esquirol, & Sicard,
1996).
Il est caractérisé principalement par deux
aspects :
ü La complexité de production : par exemple,
de nombreuses tâches sont en compétition sur plusieurs ressources
à capacités limitées.
ü Des contraintes impératives
d'antériorités entre les tâches mais aussi des contraintes
de synchronisation entre flux qui prend une dimension encore plus forte et
plus complexe dans le cadre d'une chaîne logistiques
intégrée (concept :fournisseur-atelier-client)
D'un point de vue technique, les tâches d'ordonnancement
en gestion de production peuvent être classées en trois grandes
catégories :
§ Ordonnancement statique
§ Ordonnancement dynamique
§ Ordonnancement réactif
1.8.1 Ordonnancement
statique :
L'ordonnancement statique(ou prévisionnel) est la
situation d'ordonnancement la plus classique en gestion de production.
Dans cette situation, un ensemble des tâches issu d'un
programme de production doit être ordonnancé sur un horizon.
Les tâches, les contraintes et les données
opératoires sont supposées connues et ne sont soumises à
aucune variation.
1.8.2 Ordonnancement
dynamique :
Dans cette situation, certaines tâches sont
déjà planifiées ou même ordonnancées sur les
ressources mais d'autres arrivent au fur et à mesure.
L'objectif ici est d'ordonnancer les tâches sans avoir
une vision claire sur tout l'horizon de planification et tout en respectant des
objectifs de planification (respecter les délais, limiter les en-cours
et les stocks) et /ou des objectifs de production (maximiser la
productivité, équilibrer la charge).
L'objectif n'est pas de construire réellement un
ordonnancement optimal mais plutôt de trouver des heuristiques
d'ordonnancement tout à la fois robustes aux variations (puisque
l'horizon est incertain) et adaptées à la configuration du
système étudié et aux objectifs à satisfaire
[Pierreval & Mebarki, 1997].
L'ordonnancement dynamique permet la prise en compte des
données réelles de l'atelier et surtout la prise en compte des
aléas par des modèles probabilistes, voici quelques exemples des
aléas
|
Catégories exemples
|
|
Aléas portant sur les activités
|
ü Ajout ou retrait d'activité
ü Augmentation ou diminution de la durée
opérateur de certaines activités
ü Augmentation ou diminution des quantités des
ressources nécessaires pour l'exécution de certaines
activités
ü Modification de la date de disponibilité de
certaines activités
ü Modification de la date échue de certaines
activités
|
|
Aléas portant sur les ressources
|
ü Augmentation ou diminution du nombre de ressources
disponibles (achat de nouvelles machines, licenciement)
ü Augmentation ou diminution de la capacité d'une
ressource durant une période de temps (panne de machine ou retour de
machine qui était en maintenance
|
|
Aléas temporelle
|
ü Modification de l'ordre d'exécution d'un
ensemble d'activités (ajout ou retrait de précédences de
disjonction)
|
1.8.3
Ordonnancement réactif :
Dans ce contexte, un ordonnancement a été
déjà réalisé et commencé d'être mis en
oeuvre, mais des perturbations (une commande urgente doit être
traitée, un opérateur est absent, une machine est en panne, des
composantes nécessaires à la réalisation d'une tâche
n'ont pas été livrées) imposent de revoir une partie de
cet ordonnancement, cette situation est très fréquente dans
l'industrie.
Le responsable de production est en charge de
réordonnancement; son objectif est alors d'absorber ces
perturbations.
Il existe actuellement peu de méthodes de
résolution adoptées à ce type de problème.
Les méthodes de
résolution proposées reposent principalement sur la
définition de l'ordonnancement statique des marges facilitant le
réordonnancement.
Le plus souvent, c'est l'opérateur qui construit une
solution en utilisant un outil standard de représentation de planning,
il est alors important de bien visualiser les implications dues aux
changements.
L'opérateur doit pouvoir répondre aux questions
suivantes : quelles sont toutes les implications liées à un
changement ? Quel est le degré de perturbation admissible ? Il
s'agit de bien définir quel est le problème, en particulier
à quel niveau d'abstraction il est situé : très
localement (modification local de l'ordonnancement) ou plus globalement (remise
en question profonde).
Un ordonnancement réactif pouvant être
assimilé à un système bouclé, ainsi que le
représente la figure (2), inspirée de [Artigues et al. 02]
Ordonnancement réactif
Modèle
Décider
Suivre
Décision
événement
Système d'activités
Figure (8): Une vision automaticienne d'un
ordonnancement réactif
Figure 2: Une vision
automaticienne d'un ordonnancement réactif
En se référant à la figure (2)
l'ordonnancement réactif est assimilé à la
réalisation de quatre fonctions : suivre, décider, prévoir
et adapter. Les deux premières sont des fonctions indispensables
à la réactivité : la fonction suivre permet de mettre
à jour, au fur et à mesure la réception des
événements, les modèles utilisés par la
deuxième fonction sont pour l'élaboration des décisions
d'ordonnancement. Les deux dernières sont des fonctions non
obligatoires, utilisées lorsqu'on cherche à anticiper les
événements, pour prévoir un ensemble de décisions
d'ordonnancement, et éventuellement l'adapter si cela s'avère
nécessaire (par exemple à l'occurrence d'un
événement contingent).
1.9 Conclusion :
Dans
ce chapitre, nous avons définit l'ordonnancement, quelques notions de
base d'ordonnancement tel que la notion de tâche, de ressource, les
politiques d'ordonnancement, ses contraintes et ses objectifs.
Dans le chapitre suivant, nous présenterons les
différents problèmes de l'ordonnancement.
CHAPITRE 2
LES DIFFERENTES PROBLEME
D'ORDONNACEMENT
2.1
Introduction :
Un problème d'ordonnancement d'atelier consiste
à trouver une séquence de passage d'un certain nombre de
tâche ou travaux à exécuter sur différentes machines
de façon à satisfaire des contraintes technologiques et à
optimiser un ou plusieurs critères de performances .il s'agit de
prévoir le travail à exécuter , de façon à
coordonner l'utilisation des matières premières et des moyens de
production à utiliser , c'est-à-dire à faire en sorte que
tout soit prêt au moment voulu .
Résoudre un problème d'ordonnancement, c'est
donc définir où et à quel moment précis, un certain
nombre de tâches doivent être réalisé
2. 2 Les problèmes
d'ordonnancement d'atelier :
2.22.1 Ordonnancement
à une machine :
Dans ce cas, l'ensemble des tâches à
réaliser est fait par une seule machine. Les tâches alors sont
composées d'une seule opération qui nécessite la
même machine. L'une des situations intéressantes où on peut
rencontrer ce genre de configuration est le cas où on est devant un
système de production comprenant une machine qui influence l'ensemble du
processus. L'étude peut alors être restreinte à
l'étude de cette machine.
Travaux en attente Machine
Travaux
terminés
Figure 3 :
ordonnancement à une machine
2.12.3 Ordonnancement
à machines parallèles :
Dans ce cas, on dispose d'un ensemble de machines identiques
pour réaliser les travaux. Les travaux se composent d'une seule
opération et un travail exige une seule machine .chaque tâche peut
être traitée par n'importe quelle machine. L'ordonnancement
s'effectue en deux phases : la première phase consiste à
affecter les travaux aux machines et la deuxième phase consiste à
établir la séquence de réalisation sur chaque machine.
Travaux en attente travaux terminés
Machines
Figure 4 : ordonnancement à machines
parallèles
2.12.4 ordonnancement en atelier
sériel (flow shop) :
Dans un système de flow shop, chaque tâche doit
passer par toutes les machines dans le même ordre. On dit que toutes les
tâches ont la même gamme opératoire. Toutes les tâches
ont le même ordre de traitement c'est-à-dire elles doivent
être traitées par la machine 1 puis par la machine 2 ...
Ceci n'implique cependant pas que sur chaque machine l'ordre
de passage des tâches soit identique.si c'est le cas, on parle de flow
shop de permutation.
o Chaque tâche i est
composée de m opérations Oij (j = 1; ...; m),
où Oi doit être effectuée sur Mj .
o Relations de précédences :
Oi1 <Oi2<
......<Oim i = 1; ...; n
o Le problème revient donc à trouver l'ordre
Pj des tâches pour chaque
machine j.
o Critère Cmax. (le temps
d'achèvement de la dernière tâche)
Bernard
Travaux en
attente Travaux
terminés
Machines
Figure 5: problème de flow
shop
2.12.5 Atelier
général (job shop) :
Dans un système de job shop, le sous-ensemble de
machines qui vont traiter les tâches et /ou l'ordre de traitement
sont arbitraires, mais doivent être spécifiés a priori.
MACHINE 3
MACHINE 2
MACHINE6
MACHINE4
MACHINE6
MACHINE5
Travail
fini
Travail en attente
Figure 6 : job shop à 4 travaux et
6 machines
Le problème d'ordonnancement de type job shop à
deux jobs, avec la prise en compte de contraintes de disponibilité des
machines se définit de la manière suivante :
o Un ensemble de m machines doit réaliser deux travaux
J1, J2.
o Chaque travail Ji est composé d'une séquence
linéaire de n opérations {Oi1, Oi2, ...,
Oin}.
o Chaque machine ne peut réaliser qu'une
opération à la fois et chaque opération Oij
nécessite une seule machine à la fois, durant pij
unités de temps.
2.12.6 5 Atelier ouvert (open
shop) :
Dans un système d'open shop, chaque tâche doit
passer par toutes les machines mais l'ordre de traitement n'est pas
donné.
o Chaque tâche i est composée de m
opérations Oij (j = 1; ... ; m), où Oij
doit être effectuée sur
Mj.
o Pas de relation de précédence.
o Le problème revient donc à trouver les ordres
des tâches (ordres des
opérations appartenant à une même
tâche) et les ordres des machines
(ordre des opérations effectuées sur la
même machine).
On peut synthétiser et généraliser cette
typologie ainsi que l'illustre la figure ( 7 ) proposée par [BILLAUT
99] :
Machines parallèles avec affectation
générale
Machines parallèles
Machine unique
Machine non
ensemble de
Dupliquée
machine
commun
Flow shop hybride
travaux
travaux travaux
mona-opération
mona-opération mona-opération
Flow shop avec affectation générale
Flow shop
machine non
ensemble de
dupliquée
machine commun
gamme unique gamme unique
gamme unique
Job shop avec affectation générale
Job shop
Machine non
Job shop généralisée
dupliquée
ensemble de
machine commun
avec gamme
avec
gamme
avec gamme
Open shop avec affectation généralisée
Open shop
Open shop généralisée
machine non
ensemble de
dupliquée
machine commun
Figure
7:Une typologie des problèmes d'ordonnancement (d'après
[Billaut99])
2.2 4L'ordonnancement du projet
:
Parmi les outils d'ordonnancement du projet on peut
citer :
§ Le réseau de PERT
§ Le diagramme de GANTT
Les objectifs de ces deux méthodes sont :
Ø Programmer les moyens humains et matériels
selon l'estimation des
charges futures.
Ø Coordonner les tâches.
Ø Déterminer les délais.
Ø Contrôler l'avancement des travaux.
2.24.1 Le réseaux de
PERT :
Le programme Evaluation and Review Technic (technique
d'évaluation et de contrôle de programme) est une méthode
découverte par Willar Frazard en 1958.
Elle permet à l'USA NAVY de gagner 2 ans sur la
fabrication des fusées polars (projet établit inialement sur 7
ans).
L'objet de la méthode de PERT est la planification dans
le temps d'un certain nombre des tâches (par exemple ; les
interventions des divers corps de métier participant dans un chantier)
liées entre elles par des contraintes de précédence.
Le premier pas de cette méthode consiste à
construire un graphe (graphe PERT) dontles arcs sont traduits ainsi :
b est successeur de a si seulement s'il
existe dans le graphe un chemin dont le premier arc est a et le dernier est
b.
Alors pour la construction de réseaux PERT, il
faut :
· La tâche est
représentée par un vecteur encadré des
noeuds. la longueur du vecteur n'est pas proportionnelle au temps, elle
dépend du tracé général du réseau :
ü La lettre définit l'opération
codée.
ü Le chiffre correspond à sa durée (minute,
heure, jour, mois).
ü La flèche indique le sens de
l'exécution.
2
1
A3
Les noeuds sont numérotés
et symbolisent les étapes
ü Le graphe établit la succession, la
simultanéité, la convergence des tâches en vue de la
réalisation de l'objectif final.
o Présentation des
tâches
Les tâches
successives :
3
1
2
A B
L'une ne peut commencer avant que la
précédente ne soit terminée.
Les tâches convergentes :
Plusieurs tâches peuvent être
exécutées en même temps, elles partent du même
noeud.
4
3
5
o Limites et Marges d'un réseau
PERT :
La marge totale :
La marge totale d'une tâche correspond au retard que
l'on peut prendre à sa mise en route ou au cours de son exécution
sans que cela change la durée totale du projet, mais qui remet en cause
le calendrier des tâches qui suivent.
Marge total=Date au plus tard - Date au plus
tôt
Tâche
M.T
Début Fin Fin
Au plus
au plus au plus
Début au tard tôt
tard
plus tôt M.T
La marge libre :
La marge libre correspond au retard qu'une tâche peut
prendre sans que cela change le calendrier des tâches qui suivent.
Marge libre =Date au plus
tôt tâche suivante - Date fin au tôt
Tâche suivant
Tâche t
Date Début
au plus tôt
M.L de t
Date fin
au plu tôt
La méthode consiste à représenter des
graphes partiels puis à les assembler.
Quand les tâches deviennent trop nombreuses ou trop
complexes, on fait alors appel à l'informatique.
2.24.2 Le diagramme de GANTT :
Le diagramme de GANTT est un tableau d'ordonnancement qui
permet de visualiser à la fois la répartition et l'enchainement
des tâches dans le temps ainsi que la simultanéité de
certaine opérations.
L'objectif de cette méthode est de placer les
tâches en fonction des contraintes de fabrication, des aléas et
des marges.
Le diagramme de GANTT permet de visualiser
graphiquement l'enclenchement des tâches suivant l'axe de temps, de
contrôler l'avancement des travaux, de prévoir la distribution du
travail par machine, section, atelier et de visualiser l'évolution
d'un projet.
En tenant compte des contraintes
d'antériorités, des gammes opératoires, des délais
à respecter, des capacités des postes de charge et des personnels
nécessaires
Comme pour le graphique PERT, sa construction passe par
plusieurs étapes :
§ Etape 1 : la
détermination des tâches et leurs durées.
§ Etape2 : la
détermination de l'enchainement des différentes opérations
et le repérage des tâches qui peuvent être menées en
même temps.
§
§ Etape3 : la
représentation graphique du tableau à laide d'un logiciel tel que
le traitement du texte, le tableur ou le logiciel de gestion de projet.
|
temps
tâche
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
8
|
10
|
11
|
12
|
13
|
|
A
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
E
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
FIGURE
8 : diagramme de GANTT
ü Chaque colonne représente une unité de
temps.
Les durées d'exécution prévues des
tâches sont représentées par un trait épais.
(4 unités de temps pour C).
ü Les contraintes de succession se lisent
immédiatement.
o Les tâches B et C succèdent la tâche
A.
o D succède B.
ü Le déroulement d'exécution des
tâches figure en pointillé, au fur et à mesure des
contrôles. On est à la fin de la sixième unité de
temps, B est en avance d'une unité et C est en retard d'une
unité.
ü On peut alors déterminer le chemin
critique : qui est formé d'une succession des tâches, sur
le chemin le plus long en termes de durée. Il est appelé chemin
critique car tout retard pris sur l'une des tâches de ce chemin
entraîne du retard dans l'achèvement du projet. (Chemin critique :
A, B, D, E).
2.3 Conclusion :
Dans ce chapitre, on s'est intéressé aux
problèmes d'ordonnancement qui se rencontrent dans le milieu
industriel : il s'agit de répartir un ensemble de travaux sur des
machines dans un atelier de production, les éléments essentiels
des modèles d'ordonnancement sont les machines et les tâches.
Pour présenter ces problèmes on peut utiliser
une seule machine ou des machines parallèles fournissant les mêmes
fonctions c'est le cas de « flow shop », « open
shop »et « job shop ».
On peut trouver aussi des problèmes d'ordonnancement
concernant la gestion de projet qui sont représentés par un
diagramme de GANTT ou par le graphe de PERT.
CHAPITRE 3
LES METHODES DE RESOLUTION
DU PROBLEME D'ORDONNACEMENT
3.1 Introduction :
Plusieurs auteurs [Mac Cathy & Liu 93, ESSWEIN 03]
partitionnent les méthodes de résolution en 3 classes : les
méthodes optimales efficaces, les méthodes
énumératives et les méthodes heuristiques.
· Les méthodes optimales
énumératives sont aussi des algorithmes exactes elles fournissent
en pratique sur des problèmes de taille moyenne, des solutions optimales
en un temps raisonnable .Dans cette classe, on peut distinguer :
ü Les procédures par séparation et
évaluation progressive (SEP)
(Branch&Bound) qui énumèrent par une recherche arborescente
un ensemble de solution en éliminant les branches de l'arbre de
recherche montrées non-optimales (utilisation de bornes
inférieure et supérieure du critère)
ü Les méthodes de programmation linéaires
(PL) modélisant les critères et les contraintes comme des
fonctions linéaires de variables mixtes (réelle, entier).
ü Les méthodes basées sur la programmation
dynamique (PD) qui se décomposent en sous problème, que l'on
résout optimalement à rebours, en tenant compte du
sous-problème précèdent.
· Les méthodes heuristiques sont souvent
utilisées pour traiter des problèmes que les méthodes
optimales sont incapables de les résoudre en un temps acceptable .Elles
produisent généralement une solution faisable de bonne
qualité en un temps relativement court. La qualité d'une
heuristique doit être évaluée sur plusieurs jeux d'instance
de taille variable afin de mesurer d'une part la déviation moyenne du
critère par rapport à sa valeur optimal et d'autre part
l'évolution du temps de calcul en fonction de la taille ou de la
structure du problème. Ces heuristiques sont classifiées en trois
grands types :
ü les algorithmes gloutons dans lesquels les
décisions d'ordonnancement sont prises progressivement, à temps
croissant, au fur et à mesure que les ressources se libèrent,
grâce à des règles de priorité simples de type
SPT(Shortest Processing Time), EDD(Earliest Due Date), etc. ; et pour lesquels
on ne remet jamais en cause une décision qui a été
prise.
ü les méthodes de recherche locale (tabou, recuit
simulé, algorithmes génétiques, etc.) qui, partant d'une
solution initiale, définissent un voisinage, qui est ensuite
exploré pour trouver des solutions meilleures ; (en s'autorisant parfois
à dégrader la solution courante pour augmenter la chance
d'obtenir une solution meilleure).
ü les méthodes de recherche arborescente
tronquée, proches des PSE, excepté que l'arbre de recherche est
volontairement restreint, quitte à perdre des solutions optimales, afin
de gagner en temps de calcul.
3.2 Les algorithmes exactes :
3.2.1 Programmation
linéaire :
a)Modélisation :
L'objectif de la méthode de programmation
linéaire est minimiser ou (maximiser) une fonction linéaire de n
variables réelles non négatives (les coefficients sont
notées cj) sur un ensemble de même
inégalités linéaires.
Max (ou min) z =
 i = 1,....., r
 i= r+1,....., s
 i= s+1,....., m
S.c.q xj =0
j=1, p
xj j=p+1, q
xj =0
j=q+1, n
§ La forme standard d'un problème linéaire
est comme la suivante :
max (ou min) z= c1 x1 + c2
x2 +...cn xn
a11 x1
+ a12 x2 +...+a1n xn
=b1
a21x+a22x2+...+a2nxn=b2
s.c.q
am1 x1 + am2
x2+...amn xn =bm
x1, x2,
...,xn=0
3.2.2 Programmation
linéaire en nombre entier :
Dans la programmation linéaire en nombre entier PLNE
chaque variable est restreinte aux valeurs entières, en
général les coefficients aij sont aussi entiers, et
donc on peut se limiter à des constantes bj
entières.
Max (ou min) z =
S .c  i=1,...,n
xj=0 , entier j=1,...,n
Les variables binaires peuvent se voir comme des variables
entières soumises à la contrainte d'appartenir à
l'intervalle [0 ,1].En effet, la contrainte :
Xj=0, 1
est évidemment équivalente à :
Xj=0 et Xj =1 et Xj entier
Plusieurs problèmes d'ordonnancement, tel que notre
problème de « car -sequencing », peuvent être
formulées sous la forme de programmation linéaire en nombre
entier PLNE.
3.2.3 Méthode de séparation et
d'évaluation ( branch&bound):
La méthode de branch and bound consiste à
énumérer des solutions d'une manière intelligente en ce
sens que, en utilisant certaines propriétés du problème en
question, cette technique arrive à éliminer des solutions
partielles qui ne mènent pas à la solution que l'on recherche.
De ce fait, on arrive souvent à obtenir la solution
recherchée en des temps raisonnables .Bien entendu, dans le pire de cas
on retombe toujours sur l'élimination explicite de toutes les solutions
du problème
Idée :
§ Diviser pour conquérir.
§ Utilisation de bornes sur le coût optimal pour
éviter d'explorer certaines parties de l'ensemble des solutions
admissibles.
Branchement
Soit F l'ensemble des solutions admissibles d'un
problème :
min cTx
s.c. x F
§ On partitionne F en une collection finie de
sous-ensembles F1,...,Fk.
§ On résout séparément les
problèmes :
min cTx
s.
ce problème sera appelé Fi
également.
F
Représentation
FK
F1
F2
....... ..........
§ A priori, les sous-problèmes peuvent être
aussi difficiles que le problème original.
§ Dans ce cas, on applique le même
système.
§ On partitionne le/les sous-problèmes.
F
F1
F2
FK
.......
F22
F21
F2m
F212
F21n
F211
.......
Bornement :
§ On suppose que pour chaque
sous-problème :
min cTx
s.c. x
Fi
on peut calculer efficacement une borne inférieure b(Fi) sur
le coût optimal, i.e.
b(Fi)
=minx Fi cTx
§ Typiquement, on utilise la relaxation linéaire
pour obtenir cette borne.
Les règles de séparation et
évaluation :
1) On dit qu'un sommet de l'arbre qu'il est inutile de
séparer est stérilisé, il y a plusieurs
possibilités pour cela :
§ Le sommet est associé à une solution
réalisable candidate (séparer ne l'améliorera pas).
§ Le sommet est associé à un sous -
problème non -réalisable.
§ La valeur z optimale du sous-problème
associée est inférieure (pour un problème max) à la
borne inférieure courante.
2) Un sous -problème peut être
éliminé directement si :
§ Le sous- problème est réalisable.
§ La borne inférieure courante est
supérieure à la valeur z du sous-problème.
3.2.4 Programmation
dynamique :
La programmation dynamique est l'une des grandes paradigmes de
l'algorithmique, elle s'applique généralement à des
problèmes d'optimisation pour les quels le calcul de la solution
optimale fait appel à la résolution de sous-problème
similaire au problème initial.
Ces sous - problèmes naissent souvent des
différentes choix que l'on peut effectuer pour construire une
solution.
Une approche de programmation dynamique sera efficace si un
même sous-problème apparait à plusieurs reprises lors de
l'analyse.
Cette méthode consiste à éliminer les
recalcules dans un programme récursif en stock, on envisage la
programmation dynamique lorsque :
ü La subdivision n'est pas facile à
déterminer de façon optimale.
ü Les sous-problèmes ne sont pas
indépendants.
La programmation dynamique est une méthode dont les
calculs se fait de bas en haut : on commence par résoudre les plus
petits sous -problèmes, en combinant leur solution, on obtient les
solutions des sous-problèmes de plus en plus grand.
La conception d'un algorithme de programmation dynamique peut
être planifiée dans une séquence de quatre
étapes :
ü Décomposer le problème de décision
global en phases. chaque phase est relative à, la prise d'une
décision, on donne à chaque phase un numéro k qui est un
nombre indiquant le nombre de phase (ou décision) qui restent à
faire (à prendre).
ü Au début de chaque phase il doit être
possible d'énumérer tous les états possibles du
système, c'est-à-dire de décrire toutes les situations
où pourrait être le système.
ü A chaque phase il ya n décisions
possibles : les décisions ou politiques sont
désignées par xj (j= 1, ..., n).
ü Associer à chaque décision pour une phase
k un résultat qui mesure la « valeur » de la
décision. Les politiques possibles ne sont pas nécessairement les
mêmes à chaque phase. d'autre part les politiques possibles
à une phase dépendent de l'état initial du système,
et donc ne sont pas possibles pour chaque état.
L'ensemble des notations qui sont utilisées dans la
formulation et la résolution des problèmes de programmation
dynamique sont :
K : numéro de phase indiquant le nombre de
phases restant jusqu'à la fin de l'horizon (ou fin de solution du
problème)
S : état du système (de la nature) au
début d'une phase
xj : la jème politique ou
décision à prendre
dk (s, xj) : effet total
(résultat) de la politique xj prise à la phase k étant
donné l'état s du système
fk(s, xj) effet total (direct et indirect) pour les k
dernières phases étant donné que :
§ L'état au début de la phase k est s.
§ La politique xj est adoptée pour la phase k.
§ Une fois cette politique xi choisie et qu'il en
résulte un état pour le début de la phase k-1, des
politiques optimales sont choisies pour les k-1 phases suivantes.
3.3 Les algorithmes
approchés :
3.3.1 Heuristiques :
Une heuristique est une technique qui améliore
l'efficacité d'un processus de recherche, en sacrifiant
éventuellement l'exactitude ou l'optimalité de la solution. Pour
des problèmes d'optimisation où la recherche d'une solution
exacte (optimale) est difficile (coût exponentiel), on peut se contenter
d'une solution satisfaisante donnée par une heuristique avec un
coût plus faible. Certaines heuristiques sont polyvalentes (elles donnent
d'assez bons résultats pour une large gamme de
problèmes) alors que d'autres sont spécifiques à chaque
type de problème.
3.3.2
Métaheurestique :
Les métaheurestiques sont apparues dans les
années 1980 et forment une famille d'algorithme d'optimisation dont le
but est la résolution des problèmes d'optimisation difficile.
Les métaheurestiques sont des algorithmes
d'optimisation progressant vers un optimum par échantillonnage d'une
fonction objectif dont le but est la résolution des problèmes
d'optimisation difficiles, on utilise le terme META-heuristiques car ces
algorithmes regroupent en réalité plusieurs heuristiques.
3.4 Conclusion :
Dans ce chapitre on a étudié les
différentes méthodes de la résolution des problèmes
d'ordonnancement.
On distingue deux algorithmes : algorithmes exactes et
algorithmes approchés, chaque algorithme contient différentes
méthodes comme PL ,PLEN , programmation dynamique ...
(algorithmes exacte) et heuristique , Métaheurestique ( algorithme
approchés) .
L'existence de plusieurs méthodes a pour but la
résolution des problèmes d'ordonnancement d'une manière
pertinente.
CHAPITRE 4
ETUDE DE CAS
4.1 Description du
problème :
Le problème du « car -sequencing
»est un problème d'ordonnancement d'atelier.
Il consiste à organiser dans le temps le fonctionnement
d'un atelier pour utiliser au mieux les ressources humaines et
matérielles disponibles dans le but de produire les quantités
désirées à la date voulue.
Supposons qu'on a n voitures de
différentes couleurs placées dans un ordre d'assemblage de 1
à n.
L'objectif est de trouver une permutation optimale des
voitures qui permet de minimiser le changement du couleur des voitures.
C'est à mentionner qu'on n'est pas libre de placer une
voiture dans n'importe quelle position dans la séquence. En effet si une
voiture sera placée après sa position initiale, elle risque
d'être livrée en retard.
Par contre, si une voiture sera placée avant sa
position initiale, elle risque d'être stockée pendant une longue
période et dans ce cas là son coût de stockage peut
être très élevé.
C'est pour ces raisons on peut changer la position de chaque
voiture au maximum p positions avant sa position
initiale jusqu'à p positions après sa
position initiale.
Supposons qu'on a 10 voitures placées dans un ordre
d'assemblage de
1,2,3...10 ;les voitures ont différentes couleurs:
les voitures 1,5 et 9 sont rouges
R les
voitures 2,6 et 10 sont noires N
les voitures 3 et 7 sont vertes V
es voitures 4 et
8 sont jaunes J
d'où on a les voitures colorées
placées dans cet ordre 1 2 3 4 5 6 7 8 9 10
R N V J R N V J R N .
Supposons qu'on peut changer la position de chaque voiture au
maximum 3 positions avant sa position initiale jusqu'à 3 positions
après sa position initiale. On remarque
qu'il y a 9 changements du couleur de la peinture dans cette séquence.
Si on va placer les voitures dans cet ordre
RRRNNNVVJJ on aura seulement 3 changements au lieu de 9 mais on n'a pas
respecté la contrainte de position. Par exemple la voiture rouge R
placée à la position initiale 9 elle est maintenant à la
position 3.la contrainte de position n'est pas vérifiée puisqu'on
a changé la position de la voiture rouge R plus que 3 positions avant
sa position initiale. si on va placer les voitures dans cet
ordre 1 5 3 4 2 6 7 8 9 10 RRVJNNVJRN on aura 6 changements du
couleur .Ce changement satisfait la contrainte de position mais il n'est pas
optimal.
Si on va placer les voitures dans cet ordre 2 1 5 3
7 4 8 6 10 9 N RRVVJJNNR on aura seulement 5
changements du couleur et on respecte la contrainte de position. C'est la
permutation optimale.
4.2 Formulation du
problème :
Le problème du « car-sequencing »
peut être formulé à l'aide de la programmation
linéaire en nombre entier PLNE.
La notation suivante sera utilisée pour
présenter cette formulation :
Paramètre :
n:nombre total des voitures.
p : La position d'une voiture peut
être changée au maximum p positions
avant sa position initiale jusqu'à p positions après sa position
initiale .Supposons que la position initiale d'une voiture est i alors cette
voiture peut place dans les position [i-p,i+p]
Fi : une
fonction qui nous informe sur la couleur de la
voiture numéro i.
Indice :
k: indice de la position de la voiture dans
la séquence. k=1...n
i, j : indice du numéro de la voiture.
i=1...n , j=1...n
Variables de décision :
xik: variable binaire qui prend la
valeur 1si seulement si la position k dans la séquence est
occupée par la voiture numéro i et 0 si autrement :
Xik 1 si la position k est
occupée par la voiture n° i .
0 autrement.
Cij : une variable binaire
qui prend la valeur 1 si deux voitures adjacentes i et j ont une couleur
différente.
0 si non
Cij 1 si la couleur de la voiture i est
différente de la couleur de la
voiture j et  .
0 autrement .
Avec l: la position de la voiture
numéro i.
k : la position de la
voiture numéro j.
En utilisant cette notation le problème peut être
formulé comme suit :
Min z = (1)
S /c   k=1 ....n (2)
  i= 1....n (3)
 =1  i=1....n (4)
Cii = 0
 i=1 ...n (5)
xil +xjk -cij= 1
 i? j / Fi? Fj et |l-k| =1  i, j, l, k = 1...n (6)
Cij  {0,1}  i=1...n , j=1...n (7)
Xik  {0,1}  k=1 ...n (8)
Dans cette formulation, l'objectif (1) est la minimisation
du changement du couleur des voitures.
La contrainte (2) impose qu'une seule voiture i doit
être placée dans une seule position k.
La contrainte (3) impose qu'une seule position k doit
être occupée par une seule voiture i.
La contrainte (4) impose que chaque voiture peut être
placée p positions avant sa position initiale jusqu'à p positions
après sa position initiale.
La contrainte (5) affirme que chaque même voiture a la
même couleur.
La contrainte(6) indique que les deux voitures adjacentes ne
doivent pas avoir la même couleur.
4.3 Exemple
numérique :
Supposons qu'on a 4 voitures de différentes couleurs
placées dans un ordre, l'ordre d'assemblage est de 1, 2, 3,4 :
Les voitures 1 et 3 sont rouges R
Les voitures 2et 4 sont noires N.
ce problème peut être formulé sous la
forme de programmation linéaire en nombre entier PLNE :
min c12+c13+c14+c23+c24+c34
subject to
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
x11+x21+x31+x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34+x44=1
x11+x12=1
x21+x22+x23=1
x32+x33+x34=1
x43+x44=1
c11=0
c22=0
c33=0
c44=0
x11+x22-c12<=1
x22+x33-c23<=1
x33+x44-c34<=1
x12+x21-c12<=1
x12+x23-c12<=1
x22+x13-c12<=1
x14+x23-c12<=1
x13+x24-c12<=1
x32+x21-c23<=1
x32+x23-c23<=1
x34+x23-c23<=1
x33+x24-c23<=1
x22+x31-c23<=1
x32+x41-c34<=1
x32+x43-c34<=1
x42+x33-c34<=1
x34+x43-c34<=1
x31+x42-c34<=1
end
int x11 int x21 int x31 int x41 int c11 int c22
int c34
int x12 int x22 int x 32 int x42 int c12 int c23
int c 44
int x13 int x23 int x33 int x43 int c13 int c
24
int x14 int x24 int x34 int x44 int c14 int c
33
On résout ce problème à l'aide du
logiciel Lindo.voici la sortie Lindo
OBJECTIVE FUNCTION VALUE
1) 1.000000
VARIABLE VALUE REDUCED COST
X11 1.000000 0.000000
X12 0.000000 0.000000
X13 0.000000 0.000000
X14 0.000000 0.000000
X21 0.000000 0.000000
X22 0.000000 0.000000
X23 1.000000 0.000000
X24 0.000000 0.000000
X31 0.000000 0.000000
X32 1.000000 0.000000
X33 0.000000 0.000000
X34 0.000000 0.000000
X41 0.000000 0.000000
X42 0.000000 0.000000
X43 0.000000 0.000000
X44 1.000000 0.000000
C11 0.000000 0.000000
C12 0.000000 1.000000
C13 0.000000 1.000000
C14 0.000000 1.000000
2 0.000000 0.000000
3 1.000000 1.000000
4 0.000000 1.000000
C33 0.000000 0.000000
C34 0.000000 1.000000
C44 0.000000 0.000000
La permutation optimale de ces voitures est RRNN d'où
on obtient seulement un changement du couleur au lieu de trois.
En effet, on a x11=1 ce qui implique que la
première voiture rouge reste a la même position 1.
X23 =1 ce qui implique que la voiture noire
numéro 2 est placée a la position 3.
X32=1 signifie que la voiture rouge numéro 3
est placée a la position 2.
X44=1 signifie que la voiture noire numéro 4
reste a la même position 4.
C23=1 ce qui implique que la couleur de la voiture
numéro 2(rouge) est différent de la couleur de la voiture
numéro 3(noire).
c11,
c12,c13,c14,c22,c24,c44.c34.c33
sont nuls d'où il ya un seul changement du couleur.
4.4 Conclusion :
Dans ce chapitre on a utilisé la programmation
linéaire en nombre entier PLNE pour résoudre le problème
de « car-seqeuncing ».
L'objectif de ce problème est la minimisation du
changement du couleur des voitures qui vont être passées dans un
atelier de peinture.
On a aussi présenté un exemple numérique
sur le logiciel lindo.
Conclusion
générale :
Ce mémoire contient quatre chapitres. Dans les trois premiers
chapitres on a étudié la partie théorique. En effet, on a
définit l'ordonnancement, la notion de tâche, de ressource, les
politiques d'ordonnancement, ses contraintes et ses objectifs. En outre, on a
cité les problèmes d'ordonnancement et les méthodes de la
résolution de ces problèmes.
Dans le dernier chapitre, on a étudié la partie
pratique, en effet on a travaillé sur un problème
d'ordonnancement d'atelier : le problème du « car
sequensing » C'est un problème à une seule machine,
fait dans un atelier de peinture. Son objectif est de chercher la permutation
optimale des voitures qui permet de minimiser le changement du couleur des
voitures. Ce problème est formulé sous la forme de programmation
linéaire en nombre entier et on l'a résolu par le logiciel
Lindo.
Bientôt, on voudra étudier ce problème du
« car sequencing »en utilisant deux machines parallèles,
et /ou en augmentant le nombre des voitures à permuter et/ou en ajoutant
autres contraintes tel que les contraintes du coût.
BIBLIOGRAPHIE
Sites web :
· www.eleves.ens.fr.
· www.inf.puic-rio.br.
· www.encyclopedie-enligne.com.
Livres et publication :
· Arsac, J. (2000). initiation a la programme avec
SCHEME. TECHNIP.
· Dibon, M. l. (1970). ordonnancement et potentiels
mèthodes MPM. HERMAN ,PARIS.
· Esch, L. (2006). Mathèmatique pour
économiste et gestionnaires. De Boek universitè.
· Lambert, P. (1977). la fonction d'ordonnancement.
Paris: R 2 èdition.
· P.Lopez, P. e. (1991). L'ordonnacement. PARIS:
Economica.
· Rasenberg, M. e. (1980). Combinatorics 79.
Elservies.
· Tabot, H. (2007). programmation linèaire en
nombre entier. Laboratoir A2SI .
Articles:
· Thomas, N. N. (s.d.). L'ordonnancement , la clè
d'une gestion efficace des ressources . equipe TRIO-Laboratoir LORIA à
nancy .
· Werra, D. d. (2003). Recherche opérationnelle
pour ingénieurs (Vol. 385). PPUR presse polytechnique.
· M.Haoeur, A. e. (s.d.). une nouvelle heurestique pour
le problème d'ordonnancement à machine parallèle avec
dates de disponibilitè et temps de latence .
· N Ghazi, M. B. (s.d.). Etude du problème
d'ordonnancement d'Open-shop. November 2007 . Laboratoire de Commande des
Processus (LCP), 2. Département Génie Industriel, Ecole Nationale
Polytechnique d'Alger.
· TALBI, E.-D. (2004). Sélection et réglage
de paramètres pour l'optimisation de logiciels. 'Institut National
Polytechnique de Toulouse , FARNCE.
· Abdelilah CHIGUER, S. I. (2005 définition de la
séquence de production pour une ligne d'assemblage d'automobiles .
Toronto, Ontario, Centre de Recherche sur les Technologies de l'Organisation
Réseau (CENTOR).
· LEMLOUMA, T. (s.d.). Une étude d'approches
heuristiques pour l'ordonnancement des jobs dans le "flowshop". France,
Montbonnot - 38334 Saint Ismier Cedex.
· Matthias Prandtstetter, G. R. (2005). A Variable
Neighborhood Search Approach for Solving the Car Sequencing Problem. Institute
of Computer Graphics and Algorithms,Vienna University of Technology, Vienna,
Austria.
· Guillaume Pinot, N. (2 avril 2008). HEUR heurestiques
pour le meilleur des cas dans un ordonnancement de groupes .
7eConférence de modélisation et simulation - MOSIM'08, Paris -
France.
| 
