Introduction aux problèmes

d’ordonnancement
 Définitions (1)
◼ Les problèmes d’ordonnancement apparaissent dans des
domaines aussi variés que :
◼ Organisation opérationnelle du travail dans les usines
◼ Planification de grands projets
◼ Organisation d’activités de service

◼ Problème d’ordonnancement
◼ = Un travail, décrit sous forme de tâches interdépendantes dont il faut
coordonner l’exécution, en assurant une utilisation cohérente des
ressources nécessairement limitées, qu’elles mettent en jeu

◼ Un ordonnancement = une solution au problème

d’ordonnancement
2/59
Définitions (2)
◼ Exemples de
◼ Ressources : machine dans un atelier, vols dans un
aéroport, équipes dans un projet de construction, …

◼ Tâches : opé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 date de début au plus tôt et une
date de fin souhaitée

◼ Objectifs : minimisation de l’exécution de la dernière tâche,

minimisation du nombre de tâches en retard (leurs dates de
fin d’exécution dépassent leurs dates de fin souhaitée)
3/59
 Définitions (3)
◼ Le problème d’ordonnancement consiste à préciser pour
chaque tâche :
◼ Sur quelle ressource doit-elle passer ? (Problème d’affectation)
◼ Quand va-t-on commencer cette tâche ?

◼ Quand va-t-on la finir ?

Ces décisions sont prises tout en optimisant un objectif prédéfini

Remarque :
Les variables de décision diffèrent selon qu’elles concernent
des décisions
sur le temps (variables d’Ordonnancement)
OU sur les ressources (variables d’Affectation)

4/59
 Exemple (1)
◼ Entreprise produit des sacs à papier pour : ciment, charbon, la
nourriture des chiens, ..

◼ La Matière Première Basique : papier

◼ Le processus de production comprend trois étapes :

Impression du Logo (M1), Collage d’un côté du sac (M2), la couture
du sac (M3)

◼ Les ressources de production existent en un seul exemplaire. Leur

cadence est de 100 articles/heure indépendamment du type d’article.

◼ Chaque Ordre de fabrication est caractérisé par :

◼ Le type de sac à produire
◼ La quantité à produire
◼ La durée d’exécution

5/59
 Exemple (2)
Ordre 1: 1/10/12 Impression Collage Couture
Quantité
100 sacs de ciment
Date fin souhaitée
6/10/12

Ordre 2: 1/10/12
M1 M2 M3
Quantité
200 sacs charbon
Date fin souhaitée
4/10/12
M1 M2 M3
M1 M3
Ordre 3: 1/10/12
Quantité
300 sacs nourriture
Date fin souhaitée
5/10/12

M3
Question : Que devient la solution au problème d’ordonnancement dans le cas où
les ressources existent en plusieurs exemplaires comme c’est le cas ci-dessus? 6/59
Exemple (3)
◼ Si on suppose que :
◼ Une livraison en retard engendre une pénalité qui dépend de
l’importance de l’ordre (client) et de la durée du retard

Un objectif du système d’ordonnancement peut

consister à :
Minimiser la somme des pénalités

7/59
Définitions
◼ Les problèmes d’ordonnancement dans les ateliers
relèvent de la problématique de la régulation à court
terme de l’entreprise, et plus particulièrement de celle
du contrôle et de l’utilisation de la main d’œuvre et
des équipements productifs.

◼ La théorie de l’ordonnancement est une branche de

la recherche opérationnelle. Elle consiste en la
recherche des modèles mathématiques et la mise au
point de méthodes de résolution efficaces des
problèmes proposés.
8/59
 La place de l’ordonnancement dans le
processus de planification
Plan Industriel
Commercial
Contrôle vertical permettant
d’assurer la cohérence du
(PIC)
niveau inférieur avec le son
niveau supérieur
Plan Directeur
de Production (PDP)

Plan des Besoins

Matières (PBM)

Ordonnancement

9/59
 Séquence menant d’un plan à l’autre
(adapté de Nollet, Kélada et Diorio, édition 1986)

I. Le plan de production (ou plan intégré de production)

Mois
… Avril Mai Juin Juillet …
Quantité

Unités équivalentes (U.E.) 1 022 834 660 728

II. Le plan directeur de production

Semaine du …
15 avril 22 avril 29 avril 6 mai 13 mai 20 mai 27 mai 3 juin 10 juin …
produit
Fauteuil no. 124 ( 1 U.E.) 48 - - 48 - - 48 - -
Divan no. 112 (2 U.E.) - - 84 - - 69 - 50 -
Divan no. 223 (2 U. E) - 100 20 - 50 70 - - 50
Sofa modulaire no.441 120 - - - 120 - - - -
(3 U.E.)

(36) (1)
III. Le plan des besoins -matières
Semaine du …
15 avril 22 avril 29 avril 6 mai 13 mai 20 mai 27 mai 3 juin 10 juin …
composants
Panneau no. 2441 (90X90) - - - 120 - - - - -
Ressort no. 1322 - - 4 320 - - - - - -

IV. Le calendrier de fabrication / d’atelier

jour 6 mai 7 mai 8 mai …

opération matin après -midi matin après -midi matin après -midi
Coupe 400 120 200 350
no. 1 120 no. 2441 no. 1493 no.1122 Entretien

Ponçage 600 400 120 200 10

 C’est quoi l’ordonnancement ?
Planification dans le temps de l’exécution
d’un ensemble de tâches sur un
ensemble de ressources (en respectant
un ensemble de contraintes) afin
d’optimiser un ou plusieurs critères

M1

M2

M3

M4
11/59
 Domaines d’application
◼ Gestion de la production : ordonnancement
d’atelier (ordre d’exécution des tâches dans
l’atelier)
◼ Gestion de projet : ordonnancement des
activités, des tâches
◼ Gestion des emplois du temps : enseignement,
aéronautique

12/59
 Vocabulaire (1)
◼ Travail ou Job : le système de production doit assurer une liste de
travaux. Un travail peut être par exemple « usiner une pièce »,
« découper 10 bobines de papiers de 50 m et 20 cm de large »

◼ Opération ou Tâche : un Travail sera réalisé par une suite d’opérations

élémentaires (Tâches) s’enchaînant selon un ordre logique que l’on
appelle gamme (de fabrication ou d’usinage selon le type de travail
concerné)

◼ Exemple : le Travail « découper 10 bobines de papier » pourra donner

les Opérations :
◼ Sortir une bobine mère de 20 cm de large
◼ Placer la bobine sur une bobineuse
◼ Régler les couteaux
◼ Effectuer la découpe
13/59
 Vocabulaire (2)
◼ Gamme opératoire : un ensemble ordonné ou semi-
ordonné d’opérations. La gamme opératoire spécifie les
ressources affectées à l’opération

◼ Ressource : tout moyen technique ou humain nécessaire

pour la réalisation d’une opération (machines, outils,
opérateurs, …). Lorsqu’une ressource est disponible en
quantité limitée et est utilisée pour réaliser plusieurs
opérations, celle-ci peut représenter un «goulot
d’étranglement »
◼ Ressources consommables (exemple : énergie)
◼ Ressources renouvelables (exemples : machines, main d’œuvre)

14/59
 Vocabulaire (4)
◼ Affectation : affecter une opération à une ressource c’est
préciser pour une tâche la machine sur laquelle elle sera
exécutée (environnement multi-machines avec machines
assurant les mêmes fonctions)
◼ Séquencement : séquencer un ensemble d’opérations
c’est déterminer l’ordre dans lequel elles passeront sur
les machines
 Ordonnancement :
 Affectation
 & Séquencement + Attribution de dates de début à chaque
opération

15/59
 Données
◼ n : nombre de tâches indicées par i
◼ m : nombre de machines indicées par j
◼ pi : durée d’exécution de la tâche i
◼ pij : durée d’exécution de la tâche i sur la machine j
◼ ri : date de disponibilité de la tâche i (date de début au plus tôt,
release date)
◼ di : date de fin souhaitée de la tâche i (au delà de cette date
promise au client, on encourt des pénalités – due date-). Si on
parle de date d’achèvement c’est que cette date doit être
strictement respectée (– deadline-)
◼ wi : poids attribué à la tâche i ; il exprime le facteur
d’importance et de priorité (importance des clients, coût de
stockage)
16/59
 Variables(1)
◼ ti : date de début de la tâche i
◼ tij : date de début de la tâche i sur la machine j
◼ Ci = ti + pi : date de fin d’exécution de la tâche i (sur une seule
machine)
◼ Cij = tij + pij : date de fin d’exécution de la tâche i sur la machine
j ; dans ce cas Ci = Max (tij + pij) : date de fin d’exécution de la
tâche i sur les machines j « Completion time »
pi

ti Ci
17/59
 Variables(2)

◼ Fi = Ci - ri : durée de séjour dans le système (mesure les

encours) « Flow time »
◼ Li = Ci - di : écart de la tâche i « Lateness »
◼ Ti = max (Li, 0): retard de la tâche i
◼ Ui : indicateur de retard de la tâche i, Ui =1 si Ti>0, Ui=0
sinon;

18/59
Variables(3)

ri di Ti=Li
pi Ui=1

ti Ci
Li

Fi

19/59
 Diagramme de Gantt
− Le "Diagramme de Gantt", du nom de Henry L. Gantt (1917), permet
de représenter les besoins en ressources en fonction du temps, par
l’intermédiaire d’une liste de tâches représentées par des barres
horizontales. Ce diagramme est très classique dans la gestion de
projets

− Dans un diagramme de Gantt, les lignes correspondent aux

machines et les colonnes correspondent aux unités de temps
(minutes, heures, semaines, etc.). L’exécution d’une tâche sur une
machine donnée est représentée par une barre horizontale, tracée
sur la ligne correspondante à la machine en question, de longueur
proportionnelle à sa durée d’exécution sur la même machine

20/59
 Diagramme de Gantt : exemple
Tâches A B C D E F
- 6 Tâches à effectuer :
Durée 10 4 1 1 2 6,5
pi

− L’atelier dispose de 3 machines identiques

− Exemple de diagramme de Gantt :

M1 B A

M2 E D

M3 C F

0 14 temps
Question : Déterminer le temps minimal d’exécution des 6 tâches ! 21/59
 Codification des problèmes
d’ordonnancement

− Il existe une très grande variété de problèmes d’ordonnancement. Pour

leur identification et leur classification nous adoptons la notation
proposée par Graham et al. 1979 : codification par trois champs : ||

  
description des ressources : critère d’optimisation
nombre de ressource, type
de ressource, etc.

caractéristique des tâches :

précédence, dates d’arrivée,
etc.
22/59
 Les types d’atelier : 

Une classification des problèmes d’ordonnancement peut

se faire : selon le nombre de machines et l’ordre
d’utilisation des machines pour fabriquer un produit

23/59
 Les types d’atelier : 
Une machine (1)
chaque travail est constitué d’une seule opération

24
 Les types d’atelier : 
Machine parallèles
• machines identiques (Pm) : la vitesse d’exécution est la même pour les m
machines et pour tous les travaux ;
• machines uniformes (Qm) : chaque machine a une vitesse d’exécution propre
et constante. La vitesse d’exécution est la même pour tous les travaux d’une
même machine ;
• machines indépendantes (Rm) : la vitesse d’exécution est différente pour
chaque machine et pour chaque travail.

25
 Les types d’atelier : 
Flow shop (Fm) : le cheminement des travaux est unique : les n
travaux utilisent les m machines dans l’ordre 1, 2, ..., m (ligne de
production)

26
 Les types d’atelier : 
Job shop (Jm) : les séquences opératoires relatives aux différents
travaux peuvent être distinctes et sont propres à chaque travail

27
 Les types d’atelier : 
◼ Open shop (Om) :
◼ Il existe m machines.
◼ Chaque travail doit être traité de nouveau sur
chaque machine. Cependant, certains de ces
temps de traitement peuvent être zéro.
◼ Il n'y a aucune restriction en ce qui concerne
le cheminement de chaque travail par
l'environnement de machine (pas de gamme
précise pour chaque travail)

28
 Les types d’atelier : 
◼ Flexible Flow Shop (FFc) :
◼ Généralisation du problème flow shop et
machines parallèles
◼ Au lieu de m machines en série, on dispose
de c étages en série. A chaque étage, on a
des machines identiques en parallèle
◼ Chaque travail doit passer à l’étage 1, puis
étage 2 et ainsi de suite

29
Les types d’atelier : FF3
Étage 1 Étage 2 Étage 3

M1 M2 M3
M1 M2 M3
M1 M3
M3
30
Principales contraintes :
◼ Date d’arrivée : rj
◼ Si rj apprait dans le champ , la tâche j ne
peut pas commencer avant rj, sinon elle
peut commencer à tout instant
◼ La date de fin souhaitée dj, n’apparaît pas
dans le champ , la fonction objectif
indique si existe ou non des dates de fin
souhaitée

31
Principales contraintes :
◼ Préemption : prmp
◼ On peut interrompre l’exécution d’une
tâche et commencer une autre tâche,
quand on reprend la tâche interrompue, on
termine son exécution (le travail restant)
◼ Précédence : prec
◼ Les contraintes de précédence appraîssent
surtout dans les problèmes à une machine
ou machines parallèles

32
Principales contraintes :
◼ Temps de setup dépendant de la séquence : sjk
◼ Représente le temps de setup entre le travail j et le travail k
◼ s0k : représente le temps de setup du travail k, si k est le
premier travail dans la séquence
◼ sj0 : représente le temps de nettoyage après l’exécution du
travail j, si j est le dernier travail dans la séquence
◼ Si le temps de setup entre j et k dépend de la machine,
ainsi, on ajoute l’indice i : sijk
◼ Si sjk n’apparaît pas dans le champ , alors le temps de setup
=0 ou bien ne dépend pas de la séquence dans tel cas, on
l’ajoute à la durée opératoire

33
Principales contraintes :
◼ Indisponibilité (Breakdown): brkdwn
◼ La machine peut être indisponible pendant
certaines périodes (maintenance
préventive)
◼ La période d’indisponibilité est supposée
fixe

34
Principales contraintes :
◼ Restriction d’éligibilité des machines : Mj
◼ Mj peut apparaître dans le champ  dans le cas où
on a m machines parallèles par exemple
◼ Dans ce cas, toutes les machines ne sont pas
capable d’exécuter un travail j,
◼ Mj désigne dans ce cas l’ensemble des machines
capables d’exécuter le travail j

35
Principales contraintes :
◼ Blocage : block
◼ le phénomène de blocage apparaît dans le cas
d’un problème de flow shop où la capacité de
stockage des tampons entre les machines est
limitée
◼ supposons que le tampon est à sa capacité
maximale, dans ce cas, la machine en amont est
bloquée, le dernier travail qu’elle a exécuté doit
être bloqué dans cette machine et cette dernière
est incapable d’exécuter un autre travail

36
Principales contraintes :
◼ Sans attente (no-wait) : nwt
◼ 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 d’opération à la salle de
réveil sans attente.

37
Principales contraintes :
◼ Recirculation : rcrc
◼ le phénomène recirculation peut apparaître dans
le problème de job shop
◼ Un travail peut visiter une machine plus qu’une
fois.

38
 Critères d’optimisation : 

Pour comparer 2 ordonnancements, il faut définir des

indicateurs de performance et des critères de mesure
 Les objectifs que l’on cherche à atteindre sont :

• Des critères liés au temps : minimisation de la durée

totale d’achè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,…

39
 Critères d’optimisation : 

− Les variables intervenant le plus souvent dans l’expression de la

fonction économique sont : Ci, Li, Ti et Ui

− Minimiser la durée totale (ou maximiser la productivité) : la durée

totale de l’ordonnancement notée Cmax (schedule lenght ou
makespan) est égale à la date d’achèvement du travail le plus tardif :
Cmax = max(Ci). Minimiser la durée totale, revient à minimiser Cmax
c’est-à-dire min(max(Ci)).

Critère retenu : Cmax

40
 Exemple 1
◼ Problèmes à une seule machine
◼ Makespan Cmax
◼ Objectif : minimiser la durée totale de l’ordonnancement
◼ Cmax = Max(Ci)
◼ Exemple : 4 tâches à ordonnancer
◼ Séquence  = ABCD :

A B C D
valeur Cmax = 12 pi 5 2 2 3

A B C D

12 temps

41
 Exemple 2
− Problème 1 ri Cmax

A B C D
• Exemple : 4 tâches à ordonnancer
pi 5 2 2 3
ri 0 9 2 8

42
 Exemple 2
− Problème 1 ri Cmax A B C D
• Exemple : 4 tâches à ordonnancer pi 5 2 2 3
ri 0 9 2 8
• Séquence ABCD : valeur Cmax = 16

A B C D

0 5 9 11 13 16 temps
• Séquence ACDB valeur Cmax = 13

A C D B

0 5 7 8 11 13 temps

43
 Critères d’optimisation : 

− Minimiser les encours : les encours sont déterminés par le temps de

présence des travaux dans l’atelier : Fi = Ci − ri. Le premier critère est
de minimiser la somme de ces temps (total flow time) Fi, ou de
manière équivalente le temps moyen de présence dans l’atelier (mean
flow time) 1/n  Fi. Lorsqu’on tient compte des coûts d’immobilisation,
on attache un poids wi au temps de présence, le critère devient
1/n  wiFi.

Critères retenus : Ci ou wiCi

44
 Critères d’optimisation : 

− Minimiser les retards : dans beaucoup de problèmes, il faut respecter

au mieux les délais, c’est-à-dire les dates au plus tard di. Les critères
retenus sont le retard vrai (maximum tardiness) : Tmax = max (Ti) et le
retard moyen (mean tardiness) 1/n  Ti ou le retard algébrique
(maximum lateness) : Lmax = max (Li).
− Parfois, les pénalités des retards sont indépendantes des retards, on
retiendra alors le nombre de travaux en retard Ui (comme pour le cas
de la minimisation des encours, parfois on associe un poids wi pour
chaque travail).

Critères retenus : Lmax ou Ti ou Ui ou wiUi

45
 Codification des problèmes
d’ordonnancement
minimisation du retard maximal sur
1 prec Lmax une seule machine avec des
contraintes de précédence

minimisation de la somme des

Pm C i
encours sur m machines parallèles
identiques

minimisation du makespan, dans

F r , prmp C
3 i max un atelier de type flow shop à 3
machines avec dates d’arrivée des
travaux où la préemption est
permise

46
Codification exemple
◼ FFc| ri| wiTi : Flexible Flow Shop, les
tâches sont caractérisées par des dates
d’arrivée et des dates de fin souhaitées,
l’objectif est de minimiser la somme des
retards pondérés.

47
Complexité
◼ Un algorithme répond à un problème. Il est composé
d'un ensemble d'étapes simples nécessaires à la
résolution, dont le nombre varie en fonction du
nombre d'éléments à traiter.
◼ D'autre part, plusieurs algorithmes peuvent répondre
à un même problème.
◼ Pour savoir quelle méthode est plus efficace il faut
les comparer.

48
 Notion de complexité
− Soient deux algorithmes à comparer en termes
d’efficacité. La mesure des temps d’exécution demande
trop de travail (programmation, préparation d’un jeu de
données). De plus, ces temps dépendent de l’ordinateur
et du langage (C, Java, Pascal, etc.) et on ne sait pas
comment ils varient avec la taille des données.

− Pour rendre les comparaisons indépendantes du matériel,

et pour déterminer l’efficacité d’un algorithme, nous
évaluerons, en fonction de la taille d’un énoncé, le nombre
d’opérations élémentaires nécessité par cet algorithme
dans le cas le plus défavorable

complexité 49
Complexité
◼ La théorie de la complexité s'attache à connaître la
difficulté (ou la complexité) d'une réponse
par algorithme à un problème, dit algorithmique,
posé de façon mathématique.
◼ La théorie de la complexité cherche à évaluer les
ressources – temps et espace mémoire – mobilisées
pour obtenir algorithmiquement la réponse

50
 Notion de complexité
− Algorithme polynomial : un algorithme dont le nombre d’opérations est
un polynôme de n. Exemples : n2, nlogn

− Algorithme non polynomial : un algorithme dont le nombre d’opérations

n’est pas borné par un polynôme de n. Exemples : 2 n, n!

S’il existe un algorithme polynomial pour la résolution d’un problème,

alors le problème est dit "polynomial" (P) sinon le problème est dit
"NP-complet" (NPC)

51
 Notion de complexité

− Le problème du voyageur de commerce, qui consiste à trouver un

plus court circuit passant une seule fois par chacun des sommets d'un
graphe connexe fini, est NP-complet

52
 Complexité des problèmes
d’ordonnancement
− Les problèmes d’ordonnancement de la production sont des problèmes
combinatoires extrêmement difficiles et il n’existe pas de méthodes
universelles permettant de résoudre efficacement tous les cas

− Exemples de problèmes NP-difficiles :

F2 C i 1 ri C i P2 Cmax 1 di T i

− Exemples de problèmes polynomiaux :

F2 Cmax J2 Cmax

53
 Hiérarchie de complexité
◼ Souvent un algorithme résolvant un problème
d’ordonnancement, peut résoudre un autre
problème d’ordonnancement
◼ Exemple : 1| |Cj est un cas spécifique de 1| |wjCj ,
ainsi la procédure de résolution de 1| |wjCj peut être
utilisée pour la résolution de 1| |Cj
◼ On dit que 1| |Cj réduit 1| |wjCj noté :

1| |Cj  1| |wjCj
◼ En se basant sur ce concept :

1| |Cj  1| |wjCj  Pm| |wjCj  Qm|prec |wjCj

54
 Hiérarchie de complexité

◼ Il est intéressant de savoir lorsqu’on modifie un

élément (,,) dans un problème
d’ordonnancement, comment ça influe sur sa
complexité

55
Hiérarchie de complexité selon 

[Pinedo, 2008]

56
Hiérarchie de complexité selon 

[Pinedo, 2008]

57
Hiérarchie de complexité selon 

[Pinedo, 2008]
58
Hiérarchie de complexité
◼ la hiérarchie de complexité des
problèmes :

59
Hiérarchie de complexité

[Pinedo, 2008]
60