Introduction aux probl mes
dordonnancement
Niveau : 4 me ann e G nie Industriel
Rihab MECHMECH
2021-2022
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Sch mas de classification
Param tres et notations
Exemples
Complexit des probl mes
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Sch mas de classification
Param tres et notations
Exemples
Complexit des probl mes
Quest ce que lordonnancement ?
Ordonnancer : disposer quelque
chose dans un certain ordre,
selon une certaine organisation.
Proposer une solution au
probl me dordonnancement
Quest ce que lordonnancement ?
D finitions
Le probl me dordonnancement consiste organiser dans le temps la r alisation dun
contraintes
ensemble de t ches,
dencha nements, ...) et de contraintes portant sur lutilisation et la disponibilit des ressources
requises.
compte tenu de contraintes
temporelles
(d lais,
Le probl me dordonnancement consiste ordonner la r alisation des diff rentes activit s
compte tenu de contraintes temporelles, de s quencement, de ressources disponibles en
quantit limit .
Le probl me dordonnancement consiste en une programmation pr visionnelle d taill e des
ressources mobilis es dans lex cution des op rations n cessaires la production l mentaire
de biens sur un horizon tr s court.
Le probl me dordonnancement consiste en un travail, d crit sous formes de t ches
interd pendantes dont il faut coordonner lex cution, en assurant une utilisation coh rente des
ressources n cessairement limit es, quelles mettent en jeu.
Exemples dapplication de lordonnancement
" Projets:
" Lordonnancement des m gaprojets.
" Chantiers de constructions, etc.
" Ateliers:
" Ateliers simples (menuiserie avec une seule machine)
" Ateliers complexes (ateliers de production: plusieurs produits / machines, etc.)
" Administration:
" Gestion des ressources humaines.
" Emplois du temps.
" Gestions des pauses (centres dappel)
"
Informatique:
" Ex cution des processus.
" Partage des ressources entre les processus.
" Partage des plateformes de calcul (cloud)
" A ronautique:
" Gestion des vols dans un a roport.
Lordonnancement dans la production/ dateliers
Lordonnancement en production (manufacturi re, de biens, de service) est pr sent comme
un probl me o il faut r aliser le d clenchement et le contr le de l'avancement d'un ensemble
de commandes travers les diff rents centres composant le syst me.
tapes de lordonnancement dans la production
" La planification : qui vise d terminer les diff rentes op rations r aliser,
les dates
correspondantes, et les moyens mat riels et humains y affecter.
" Lex cution : qui consiste la mise en Suvre des diff rentes op rations d finies dans la
phase de planification.
" Le contr le : qui consiste effectuer une comparaison entre planification et ex cution, soit
au niveau des co ts, soit au niveau des dates de r alisation.
Processus d cisionnel
Long terme
Moyen terme
Strat gique
(O aller)
Tactique
(Comment y aller)
la direction g n rale de
Elles sont prises par
l'entreprise. Elles concernent
les orientations
g n rales de l'entreprise. Elles ont une implication
l'avenir de
sur
l'entreprise. Elles comportent un risque important.
le long terme et engagent
Elles sont prises par les cadres de haut niveau.
Elles ont une implication sur le moyen terme et
des cons quences importantes pour lentreprise.
Elles comportent un risque moyen
Court terme
Op rationnel
les responsables de
Elles sont prises par
lentreprise ou les employ s. Elles ont une port e
limit e et comportent un risque mineur.
(y aller)
Advertisement
Lordonnancement dans le processus d cisionnel
F/S
Source
(Approvisionnement)
Make
(Production)
Deliver
(Distribution)
Client
Quels fournisseurs?
Combien dusines? Combien dentrep ts? O les localiser?
Quel niveau de sp cialisation?
Quelle capacit de stockage?
(PIC) : Comment Planifier de la Supply Chain
Comment allouer la production? La production: Fabrication sur
stock, sur command, etc.
La capacit ? Flux et op rations g rer ?
Le choix dun PSL (un contrat de 2 3 ans par exp)
Pilotage pr cis des flux:
Choix dun moyen de transport (d cisions de transport)
Choix dun chemin de livraison: O ? Combien ?
Ordonnancement, tourn es de v hicules, etc.
Long terme
Moyen terme
Court terme
Tr s Court
terme
Hi rarchie de planification: place de lordonnancement dans le processus
de planification
PIC (plan industriel et
commercial)
PDP(plan directeur de
production)
Calcul des besoins
nets
Ordonnancement
Ex cution
" Un ensemble de t ches.
" Un environnement de ressources pour effectuer les t ches.
" Des contraintes sur les t ches et les ressources.
" Un crit re doptimisation.
Terminologie
T ches ou op ration:
Cest une intervention caract ris e par une dur e propre estim e par les m thodes.
Un ensemble dop rations de transformation dans un atelier, atterrissage dans un
a roport, tapes dans un projet de construction,&.
Chaque t che peut tre caract ris e par :
" Un degr de priorit .
" Une dur e.
" Une date de d but au plus t t.
" Une date de fin souhait e / Un d lai: une contrainte technique ou commerciale
traduisant la fin souhait e dune t che.
" Nature de la t che (ex: t che qui ne sex cute que sur une ressource bien d termin e).
Terminologie
Travail ou Job :
le syst me de production doit assurer une liste dop rations l mentaires (t ches)
sencha nant selon un ordre logique que lon appelle gamme (de fabrication ou dusinage
selon le type de travail concern ). Un travail peut tre par exemple usiner une pi ce ,
d couper 10 bobines de papiers de 50 m et 20 cm de large
Exemple : le Travail d couper 10 bobines de papier pourra donner les t ches :
1. Sortir une bobine m re de 20 cm de large.
2. Placer la bobine sur une bobineuse.
3. R gler les couteaux.
4. Effectuer la d coupe.
Terminologie
Ressources:
machine dans un atelier, vols dans un a roport, quipes dans un projet de construction, etc.
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.
On distingue les ressources:
" Renouvelables: si elle est nouveau disponible en m me quantit apr s avoir t utilis e
par une ou plusieurs t ches (les hommes, les machines, etc.).
Dans le cas contraire,
consommable (mati re premi re, budget, etc.)
" Consommables: elle est
consommation globale (ou cumul) au cours du temps est limit e.
On distingue aussi les ressources,
" Disjonctives (ou non partageables) qui ne peuvent ex cuter quune t che la fois
(machine-outil, robot manipulateur).
" Cumulatives (ou partageables) qui peuvent tre utilis es par plusieurs t ches
simultan ment ( quipes douvriers, poste de travail).
la
;
Terminologie
Objectifs:
Quelle est la fonction optimiser ?
Exemples : minimiser le temps
Temps dattente devant une chaise (social?)
" Nombre de t ches en retards / retard maximal.
" La date de fin de la derni re t che ex cut e.
" Moyenne des dates de n dex cution des t ches.
Exemple: minimiser lutilisation des ressources
" Ordonnancement conomique : utiliser le nombre minimal de ressources.
" R seau: Optimiser lutilisation de la bande passante.
" Probl me de transport : minimiser les distances parcourues.
R capitulatif
Objectifs de lordonnancement
" Optimiser lutilisation des moyens n cessaires et les rendre disponibles.
" Lancer les travaux aux moments choisis.
" Contr ler lavancement et la fin des t ches et prendre en compte les carts ventuels.
" Pr voir la chronologie du d roulement des t ches.
D finition:
Lordonnancement est
la planification chronologique de l'ex cution de plusieurs t ches
(s quencement) sur un ensemble de ressources (affectation aux ressources disponibles
pour le cas multi ressource)
tout en respectant les contraintes existantes (capacit des
ressources, temporelles, etc.) afin d'optimiser un ou plusieurs objectifs/crit res.
Plan du cours
Advertisement
1
2
3
4
5
Introduction et probl matique g n rale
Sch mas de classification
Param tres et notations
Exemples
Complexit des probl mes
Sch mas de classification
Plusieurs probl mes dordonnancement peuvent tre tudi s. Afin de d finir et de classifier les
probl mes existants, nous suivons les sch mas de classification propos s par (Graham et al,
1979). Le sch ma propos consiste en une classification en trois champs comme suit:
5 |5 |5
O :
5 : environnement ressources (nombre, type, etc.).
5 : les caract ristiques des t ches (pr c dence, date darriv e, etc).
5 : le (ou les) crit re(s) optimiser.
5 |5 |5
Une classification tr s r pandue des ateliers, du point de vue ordonnancement, est bas e sur
les diff rentes configurations (le nombre et lordre) des machines et par cons quent, sur la
valeur de 5 choisie . Les probl mes les plus connus sont ceux:
" Probl mes machine unique
" Probl mes machines parall les
" Probl mes dateliers:
" Ateliers cheminement unique (Flow Shop).
" Ateliers cheminements multiples (Job Shop).
" Ateliers cheminements libres (Open Shop).
" Autres configurations.
5 |5 |5
Probl mes machine unique:
Dans ce cas, lensemble des t ches r aliser est fait par une seule machine. Les t ches
sont compos es dune seule op ration qui n cessite la m me machine. Lune des situations
int ressantes o on peut rencontrer ce genre de configurations est le cas o on est devant un
influence lensemble du
syst me de production comprenant une machine goulot qui
processus. L tude peut alors tre restreinte l tude de cette machine.
5 |5 |5
Probl mes machines parall les :
Dans ce cas, on dispose dun ensemble de machines pour r aliser les travaux. Les travaux
se composent dune seule op ration et un travail exige une seule machine. Toute t che peut
tre ex cut e indiff remment sur une des machines mises en parall le. Lordonnancement
seffectue 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.
5 |5 |5
Probl mes machines parall les :
Dans ce cas, on dispose dun ensemble de machines pour r aliser les travaux. Les travaux
se composent dune seule op ration et un travail exige une seule machine. Toute t che peut
tre ex cut e indiff remment sur une des machines mises en parall le. Lordonnancement
seffectue 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.
On distingue trois types de machines:
Machines identiques 5C5Z : la dur e dex cution est la m me pour les toutes les machines
et pour toutes les t ches.
Machines uniformes 5D5Z : chaque machine a une vitesse dex cution propre et constante.
"5Y5N 5Q5b5_ 5R 5Q25R5e 5P5b5a5V5\5[ 5c5V5a5R5`5`5R 5Q5R 5a5_5N5V5a5R5Z5R5[5a 5Q5R 5Y5N 5Z5N5P5V5[5R" est le m me pour
Le rapport
tous les travaux dune m me machine.
Machines ind pendantes 5E5Z : la vitesse dex cution est diff rente pour chaque machine
et pour chaque travail.
5 |5 |5
Probl mes dateliers Flow Shop (56 = 5m) :
Cest un atelier s quentiel, lin aire ou aussi dit cheminement unique o les tapes de
transformation sont identiques pour tous les produits fabriqu s . Chaque Job est constitu
dun ensemble de t ches qui doivent sex cuter sur les m mes machines dans le m me
ordre et une seule fois.
5 |5 |5
Probl mes dateliers Flow Shop (56 = 5m) :
Cest un atelier s quentiel, lin aire ou aussi dit cheminement unique o les tapes de
transformation sont identiques pour tous les produits fabriqu s . Chaque Job est constitu
dun ensemble de t ches qui doivent sex cuter sur les m mes machines dans le m me
ordre et une seule fois.
Parmi les caract ristiques des probl mes de cette cat gorie :
Il existe au minimum n! diff rentes solutions o n est le nombre de travaux r aliser.
"
" Le probl me est NP-difficile lexception des versions avec deux machines et certains
cas particuliers avec trois machines.
" Une grande productivit mais une faible flexibilit .
5 |5 |5
Probl mes dateliers Job Shop (56 = 5q) :
Cest un atelier cheminements multiples traitant une vari t de produits individuels dont la
production requiert divers types de machines dans des s quences vari es (Les s quences
op ratoires relatives aux diff rents travaux peuvent tre distinctes et sont propres chaque
travail) :
" Le nombre dop rations nest pas forc ment le m me pour tous les jobs.
" Chaque job a son propre ordre de passage sur les machines.
Probl mes dateliers Job Shop (56 = 5q) :
5 |5 |5
Probl mes dateliers Open Shop (56 = 5v) :
Cest un atelier cheminements libres o :
" Le nombre dop rations nest pas forc ment le m me pour tous les jobs.
" Lordre de passage sur les machines est totalement libre.
Probl mes dateliers Flow Shop Hybride :
5 |5 |5
Exemple: Un flow-shop hybride 3- tages d finit donc l'organisation ordonnancer (trois
ensembles de ressources existantes en plusieurs exemplaires sont utilis s en s quence).
Flow Shop 3 tages
Probl mes dateliers Flow Shop Hybride :
5 |5 |5
S
t
o
c
k
s
5 |5 |5
Traduit la relation (si elle existe) entre les diff rents t ches consid r es. Parmi les relations les
Advertisement
plus fr quentes on distingue:
" La pr emption des t ches: on interrompe lex cution dune t che et on commence une
autre t che, quand on reprend la t che interrompue, on termine lex cution du travail
restant.
" La pr c dence entre les t ches.
" Obligation au niveau des dates de d but au plus t t des t ches (je ne peux pas commencer
la t che en question avant sa date de d but).
" Obligation au niveau de la date de fin souhait e.
Indisponibilit de la machine (Breakdown):
"
certaines p riodes (maintenance pr ventive).
la machine peut tre indisponible pendant
" Sans attente (no-wait) : le ph nom ne de sans attente peut appara tre dans un probl me de
flow shop ou flow shop flexible Le travail ne peut pas attendre entre deux machines
successives; Exemple : bloc op ratoire, un patient doit passer directement de la salle
dop ration la salle de r veil sans attente.
5 |5 |5
Pour comparer 2 ordonnancements, il faut d finir des indicateurs de performance et des
crit res de mesure. Les objectifs que lon cherche atteindre sont :
" Des crit res li s au temps : minimisation de la dur e totale dach vement, les encours, les
retards,&.
" Des crit res li s aux ressources : quilibrage des charges,&
" Des crit res li s aux co ts : co ts de lancement, co ts de stockage,&
Exemples de crit res li s au temps :
5 |5 |5
" Temps de circulation (flowtime) : cest le temps quune pi ce donn e passe par le syst me
depuis son d marrage sur la premi re machine jusqu sa sortie du syst me.
" Temps moyen de traitement : Il est calcul comme tant la moyenne arithm tique des temps
de circulation pour n jobs.
" Temps global (makespan): cest le temps n cessaire pour compl ter lensemble de toutes
les n t ches.
" Retard alg brique (tardiness): Le retard dune t che
Comment mesurer les diff rents param tres / objectifs ?
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Sch mas de classification
Param tres et notations
Exemples
Complexit des probl mes
Notations
" 5[ t ches, chaque t che est indic es par 5V
" 5Z machines, chaque machine est indic es par 5W
" 5_5V (release date) : une date de d but au plus t t
" 5]5V : une dur e de la t che 5V
" 5]5V5W (processing time): une dur e de la t che 5V sur la machine 5W
" 5Q5V (due date) : une date de fin souhait e ((au del de cette date promise au client, on
encourt des p nalit s due date-).
" 5d5V (weight) : un poids relatif (il peut traduire limportance ou poids des clients).
Notations : objectifs et mesures de la performance
Les crit res doptimisation sexpriment en fonction des dates de fin des t ches (ou jobs):
"
"
5a5V: date de d but de la t che i
5a5V5W: date de d but de la t che i sur la machine j
" 565V = 5a5V + 5]5V: date de fin dex cution de la t che i (sur une seule machine)
" 565V5W = 5a5V5W + 5]5V5W: date de fin dex cution de la t che i sur la machine j et donc,
565V = Max 5a5V5W + 5]5V5W : date de fin dex cution de la t che i sur les machines j (Completion time)
" 565Z5N5e = max (565V) : la dur e totale de lordonnancement.
" 595V = 565V 5_5V (flow time) :la dur e du s jour dans latelier (mesure les encours)
" 5?5V = 565V 5Q5V (lateness) : le retard alg brique.
" 5G5V = max (0, 565V 5Q5V ) (tardiness) : le retard absolu.
" La p nalit unitaire de retard 5H5V = 0 si 565V d 5Q5V , 5H5V = 1 sinon.
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Sch mas de classification
Param tres et notations
Exemples
Complexit du probl me
Diagramme de Gantt
Le diagramme de Gantt, couramment utilis en gestion de projet, est l'un des outils les plus
efficaces pour repr senter visuellement l' tat d'avancement des diff rentes activit s (t ches)
qui constituent un projet. La colonne de gauche du diagramme num re toutes les t ches
effectuer, tandis que la ligne d'en-t te repr sente les unit s de temps les plus adapt es au
projet (jours, semaines, mois etc.). Chaque t che est mat rialis e par une barre horizontale,
dont la position et la longueur repr sentent la date de d but, la dur e et la date de fin.
M3
M2
M1
1
6
3
4
2
5
Diagramme de Gantt
Ce diagramme permet donc de visualiser d'un seul coup d'Sil :
" Les diff rentes t ches envisager
" La date de d but et la date de fin de chaque t che
" La dur e escompt e de chaque t che
" Le chevauchement ventuel des t ches, et la dur e de ce
chevauchement
" La date de d but et la date de fin du projet dans son ensemble
Codification
1|5C5_5R5P|565Z5N5e
Minimisation du makespan sur une seule machine
avec des contraintes de pr c dence
1|5C5_5Z5]|565Z5N5e
Minimisation du makespan sur une seule machine
avec des contraintes de pr emption
Advertisement
5C5Z || 565V
5D5Z || 565V
Minimisation de la somme des encours sur m
machines parall les identiques
Minimisation de la somme des encours sur m
machines parall les uniformes
1||565Z5N5e
" Un probl me 1 seule machine
" Objectif: minimiser le makespan 565Z5N5e
5V
5]5V
1
3
2
4
3
7
M1
1
2
3
4
2
4
0 3 7 14 16
565Z5N5e = 16
1|5_5V|565Z5N5e
" Un probl me 1 seule machine
" Objectif: minimiser le makespan 565Z5N5e sous contrainte de disponibilit
565Z5N5e = 18
M1
1
2
5V
5]5V
5_5V
1
3
0
3
2
4
5
3
7
3
4
2
9
4
0 3 5 9 16
18
M1
1
3
2
4
0 3 10 14 16
565Z5N5e = 16
5C2 |5_5V|565Z5N5e
" Un probl me 2 machines parall les.
" Objectif: minimiser le makespan 565Z5N5e sous contrainte de disponibilit
5V
5]5V
5_5V
1
2
1
2
2
0
3
4
0
565Z5N5e = 5
M1
M2
3
0 4
1
2
0 1 3 5
Comment avoir lordonnancement optimal ?
" R gles de priorit
" Algorithmes
" Heuristiques
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Sch mas de classification
Param tres et notations
Exemples
Complexit des probl mes
Complexit
Un m me probl me peut g n ralement tre r solu par plusieurs algorithmes :
il faut comparer entre ces algorithmes
La comparaison se base sur le temps de calcul et sur lespace m moire requis par
lalgorithme
565\5Z5]5Y5R5e5V5a 5R5[ 5
565\5Z5]5Y5R5e5V5a 5R5[ 5