Problèmes d’ordonnancement

Pr. Cheikh Noufissa

cheikh.noufissa@gmail.com
 Définition
Ordonnancer : Accomplir un ensemble de tâches (opérations) qui sont
soumises à un nombre de contraintes , et cela via des ressources en vue
de la réalisation d’un objectif ( fonction objectif / économique)précis

Pr N. CHEIKH 2
 Introduction

La théorie d'ordonnancement est une branche de la recherche

opérationnelle, qui consiste à ordonner un ensemble d'opérations tout en
satisfaisant un ensemble de contraintes et en optimisant un ou plusieurs
objectives.

Pr N. CHEIKH 3
 Introduction

L'ordonnancement joue un rôle essentiel dans de nombreux secteurs d'activités :

 Informatique (ordonnancement de processus),

 Administration (établissement d'un emploi du temps, gestion des ressources

humaines),

 Industrie (gestion des ateliers de production),

 Construction (gestion des chantiers routiers),

 Logistique (gestion des livraisons et des stocks)

Pr N. CHEIKH 4
Domaines d’application

Pr N. CHEIKH 5
 Difficultés rencontrées en Ordonnancement

 Technologiques : une tâche ne peut débuter que lorsque d’autres sont achevées

 Commerciales : certaines tâches doivent être achevées pour une date fixée

 Matérielles : une machine ne peut traiter qu’une tâche à la fois

 Main d’œuvre :effectif limité

 Financières : budget limité

Pr N. CHEIKH 6
Formulation d’un Problème d’Ordonnancement

Tâches Ressources

Contraintes Objectifs

Pr N. CHEIKH 7
 Caractéristiques des Tâches

 Une tâche (Task) est dite morcelable si elle peut être exécutée par morceaux

 Une tâche non-morcelable (indivisible) qui doivent être exécutées en une seule fois et
ne peuvent pas être interrompues avant qu'elles ne soient complètement achevées.

 Les tâches sont regroupées en entités appelées Travaux ou Job

 Un atelier contient plusieurs machines distinctes et un ensemble des Job, chacun est
constitué d’un ensemble de tâches (opérations élémentaires), chacune d’elle doit
s’exécuter sur l’une des machines
Pr N. CHEIKH 8
 Les tâches
 Soit I={1,2,...,n} l’ensemble des tâches
 la durée d’exécution de la tâches i indépendamment des ressources disponibles pour son exécution.
 : Date de disponibilité (release date), date avant laquelle la tâche i ne peut pas commencer
 : Date échue (due date), date avant laquelle la tâche i doit être achevée
 : Date réelle de début d’exécution de la tâche i (se calcule pendant l’ordonnancement)
 Date réelle de fin d’exécution de la tâche i (se calcule pendant l’ordonnancement)

Caractéristiques
d’une tâche

Pr N. CHEIKH 9
 Les Ressources

On distingue deux types de ressources pouvant être requises pour l’exécution des tâches:

 Ressource renouvelable : après avoir été allouée à une tâche, elle peut être encore
disponible pour d’autres tâches (machines, personnel, fichiers, ...)

 Ressource consommable : après avoir été allouée à une tâche, elle n’est plus disponible
pour d’autres tâches (matières premières, argent, ...)

Pr N. CHEIKH 10
 Types de contraintes
 Contraintes de type potentiel:

 les contraintes de localisation temporelle (la tâche i ne doit pas commencer avant la date t ou
elle doit être achevée à la date t)

 Les contraintes de succession (la tâche j ne peut pas commencer avant que la tâche i ne soit
terminée)

 Contrainte de délai : j doit être terminée avant une certaine date

 Contraintes de type disjonctif : imposent la disjonction de deux intervalles de temps relatifs

(deux tâches i et j devant s’exécuter sur une même machine et qui ne peuvent pas être réalisées
simultanément)
Pr N. CHEIKH 11
 Types de contraintes
 Contraintes du temps alloué: les dates limites des tâches ou la durée totale du projet

 Contraintes du calendrier : horaires du travail

 Contraintes de ressources : liées à l’utilisation et la disponibilité des ressources

requises par les tâches

On note :

L’ensemble des tâches qui consomment la ressource k à l’instant t

Pr N. CHEIKH 12
 Fonction Objectif

La programmation des tâches se réalise de façon à optimiser un certain

objectif qui peut être généralement:

 L’utilisation efficace des ressources

 La minimisation d’un coût (coût de production)

 La minimisation de la durée totale (c'est la catégorie des objectifs les

plus étudiés en optimisation)

Pr N. CHEIKH 13
 Fonction Objectif

Les variable intervenant dans la fonction objectif:

Dans le cas de minimisation du temps totale d’exécution du projet

• La date de fin d’exécution de la tâche i

• date avant laquelle la tâche i doit être achevée

• Le retard

Pr N. CHEIKH 14
 Types d’ateliers
Selon la nature des contraintes de précédence entre les tâches d’un même Job (travail), on
distingue 3 types d’ateliers:
Flow-shop

Types d’atelier

Job-shop Open-shop
Pr N. CHEIKH 15
 Types d’ateliers
 Si les m (nombre d’opérations pour tous les Jobs) opérations élémentaires (tâches) des
travaux sont liées par le même ordre total, il s’agit d’un problème Flow-shop

Pr N. CHEIKH 16
 Types d’ateliers
 Si les opérations élémentaires (tâches) d’un travail (leur nombre n’est pas forcément
le même pour tous les Jobs) sont liées par un ordre total, non nécessairement
identique pour tous les travaux, il s’agit d’un problème Job-shop

Pr N. CHEIKH 17
 Types d’ateliers
 Si Le nombre d’opérations n’est pas forcément le même pour tous les jobs et l’ordre de
passage sur les machines est totalement libre, il s’agit d’un problème Open-shop.

Pr N. CHEIKH 18
 Exemple de
Problème
d’ordonnancement

Pr N. CHEIKH 19
 Résolution des problèmes d’ordonnancement

Les méthodes :
Gantt

Pert

MPM

Pr N. CHEIKH 20
 Résolution des problèmes d’ordonnancement

Les méthodes :
Gantt

Pert

MPM

Pr N. CHEIKH 21
 Diagramme de Gantt

1ère étape: Lister les tâches, estimer les durées et identifier l’ordre dans lequel les
tâches doivent être faites

Pr N. CHEIKH 22
 Diagramme de Gantt
2ème étape: Dessiner chaque tâche en faisant apparaître au fur et à mesure les contraintes d
précédence

Pr N. CHEIKH 23
 Diagramme de Gantt
2ème étape: Dessiner chaque tâche en faisant apparaître au fur et à mesure les contraintes d
précédence

Pr N. CHEIKH 24
 Diagramme de Gantt
2ème étape: Dessiner chaque tâche en faisant apparaître au fur et à mesure les contraintes d
précédence

Pr N. CHEIKH 25
 Diagramme de Gantt
2ème étape: Dessiner chaque tâche en faisant apparaître au fur et à mesure les contraintes d
précédence

Pr N. CHEIKH 26
Exemple

Pr N. CHEIKH 27
 Exemple
Jours

Repère 1 2 3 4 5 6 7 8 9 10 11

A
B
C
D
E
F
G
H
I

Pr N. CHEIKH 28
Pr N. CHEIKH 29
 Résolution des problèmes d’ordonnancement

Les méthodes :
Gantt

Pert

MPM

Pr N. CHEIKH 30
Réseaux Pert

Pr N. CHEIKH 31
 Réseaux Pert

Le PERT (Program of Evaluation and Review Technic /Technique d’élaboration et de

contrôle de projets) : Méthode américaine datée de 1958 Consiste à mettre en ordre
un ensemble de tâches en utilisant un graphe orienté sans boucles dont :

• Les sommets constituent des événement (Étapes de la réalisation des tâches)

• Les arcs représentent les tâches

• Les valuations des arcs sont les détails de l’exécution

Pr N. CHEIKH 32
Réseaux Pert

Pr N. CHEIKH 33
 Réseaux Pert

• L’étape 1 est l’étape de début de la tâche a

• L’étape 2 est l’étape de fin de la tâche a

Pr N. CHEIKH 34
Réseaux Pert

Pr N. CHEIKH 35
Réseaux Pert

Pr N. CHEIKH 36
 PERT – Règles de présentation du graphe

Exemple:
Soit le projet suivant: changer une roue crevée
A. Installer le cric et monter la voiture: 5minutes
B. Dévisser les écrous de la roue crevée : 3minutes
C. Ôter la roue crevée et installer la roue de secours: 1minute
D. Revisser les écrous de la nouvelle roue: 4minutes
E. Baisser la voiture enlever le cric: 3minutes

Pr N. CHEIKH 37
 PERT – Règles de présentation du graphe

Un réseau possède toujours une et une seule étape de

début ainsi qu’une et une seule étape de fin.

A
respecter Toute tâche a au moins une étape de début et au moins
une étape de fin

On ne peut pas avoir deux tâches différentes qui ont à la

fois même étape de début et même étape de fin.

Pr N. CHEIKH 38
 PERT – Règles de présentation du graphe

• Lorsque deux tâches convergentes précèdent une ou plusieurs tâches en commun, et

que l’une de ces deux tâches convergentes précède également une tâche (ou plusieurs)
que l’autre tâche convergente ne précède pas, il est nécessaire d’avoir recours à une
tâche fictive.

Pr N. CHEIKH 39
 PERT – Règles de présentation du graphe

• L’intérêt de la tâche fictive est de préciser la dépendance chronologique qu’il existe

entre certaines tâches de manière qualitative (avant/après) mais pas de manière
quantitative: elle possède donc une durée qui est considérée comme nulle, et n’induit
aucun retard sur le délai final.

Pr N. CHEIKH 40
 PERT – Règles de présentation du graphe

• Une tâche fictive est représentée par une flèche à trait pointillé, sans aucune indication
de lettre (ou nom) et de durée.

Les tâches A et C sont convergentes et

précèdent la tâche D. C ne précède que D,
mais en revanche, A précède non seulement
D, mais aussi B. On précise alors cette dernière
condition à l’aide d’une tâche fictive.

Pr N. CHEIKH 41
PERT – Règles de présentation du graphe

Pr N. CHEIKH 42
 PERT – Règles de présentation du graphe

• Exemple tache fictive: Tache Antécédent

a
b
c a, b
d b

Pr N. CHEIKH 43
 PERT – Règles de présentation du graphe

• Exemple tache fictive: Tache Antécédent

a
b
c a, b
d b

Pr N. CHEIKH 44
PERT – Exemple

Pr N. CHEIKH 45
 PERT – Etude d’un Exemple
On considère l’exemple suivant: Tâche Durée Antécédent

A 3
B 1 A
C 5 A
D 6 B
E 4 B
F 2 C, I, D
G 9 E, F
H 5
I 8 H
J 2 H
K 3 I
L 7 J, K
Pr N. CHEIKH 46
PERT – Règles de présentation du graphe

Etude d’un exemple:

Par la simple déduction on en déduit les valeurs de la colonne tâche(s) successeur(s):

Pr N. CHEIKH 47
PERT – Etude d’un Exemple

Pr N. CHEIKH 48
 PERT – Etude d’un Exemple

Calcul des dates au plus tôt:

 Pour une étape donnée, cette information détermine à quelle date minimum depuis
le début du projet sera atteinte, au plus tôt, l’étape considérée.

 Pour ce faire on se base sur l’estimation de la durée des tâches. On part de l’étape du
début, pour laquelle la date au plus tôt est initialisée à 0, et on parcourt le réseau en
suivant l’agencement des tâches déterminé auparavant.

Pr N. CHEIKH 49
 PERT – Etude d’un Exemple

Calcul des dates au plus tôt:

Deux méthodes de calcul existent:

• 1 tâche (un seul chemin pour atteindre l’étape)

• Plusieurs tâches
(plusieurs chemins possibles pour atteindre l’étape)

Pr N. CHEIKH 50
 PERT – Etude d’un Exemple

Etude d’un exemple:

On détermine que le projet pourra au mieux être finalisé en l’espace de 24 jours
ouvrés:

Pr N. CHEIKH 51
 PERT – Etude d’un Exemple

Calcul des dates au plus tard:

 Pour une étape donnée, cette information détermine à quelle date maximum, depuis le début
du projet doit être atteinte, au plus tard, l’étape considérée, afin que le délai de l’ensemble du
projet ne soit pas modifié.

 Pour ce faire on se base sur l’estimation de la durée des tâches. On part de l’étape du fin, pour
laquelle la date au plus tard à la même valeur que la date au plus tôt déterminée
précédemment , et on parcourt le réseau en suivant l’agencement inverse des tâches.

Pr N. CHEIKH 52
 PERT – Etude d’un Exemple

Calcul des dates au plus tard:

Deux méthodes de calcul existent:

• 1 tâche (un seul chemin pour atteindre l’étape)

• Plusieurs tâches
(plusieurs chemins possibles pour atteindre l’étape)

Pr N. CHEIKH 53
 PERT – Etude d’un Exemple

Le calcul des dates au plus tard donne le graphe suivant:

Pr N. CHEIKH 54
 PERT – Etude d’un Exemple

On en déduit le réseau PERT correspondant:

Pr N. CHEIKH 55
 PERT – Etude d’un Exemple

Détermination du chemin critique:

Le chemin critique indique quelles sont les tâches à

successivement observer au cours de la mise en œuvre du projet
afin de surveiller les éventuels retards. Le but est de détecter les
dérives et d’agir alors rapidement en conséquence afin de
minimiser leur impact sur la durée de l’ensemble du projet.

Pr N. CHEIKH 56
 Résolution des problèmes d’ordonnancement

Les méthodes :
Gantt

Pert

MPM

Pr N. CHEIKH 57
 MPM

• La Méthode des Potentiels et antécédents Métra (MPM) est, comme le

PERT, une technique d'ordonnancement basée sur la théorie des graphes,
visant à optimiser la planification des tâches d'un projet.

• Elle aurait été mise au point en 1958 par un chercheur français, Bernard
Roy, au sein de la société de conseil Métra, dans le cadre du projet de
construction du paquebot "France".

Pr N. CHEIKH 58
 MPM

• Bien que le PERT se soit d'abord imposé en matière de gestion de projet, la MPM
tend, depuis les années 1980, à le supplanter. Cette méthode s'avère, en effet,
beaucoup plus souple et mieux adaptée à une automatisation du traitement des
données (notamment en terme de représentation graphique et d'algorithme de
calcul).

• L'utilisation de la MPM permet, notamment, de déterminer la durée minimum

nécessaire pour mener à bien un projet et les dates auxquelles peuvent ou
doivent débuter les différentes tâches nécessaires à sa réalisation pour que cette
durée minimum soit respectée.

Pr N. CHEIKH 59
 Construction du réseau MPM

• Soit l'exemple suivant:

Taches Durée Antériorités Niveaux

A 2 - N1
B 4 - N1
C 4 A N2
D 5 A, B N2
E 6 C, D N3

Pr N. CHEIKH 60
 Construction du réseau MPM

• Soit l'exemple suivant:

Taches Durée Antériorités Niveaux

A 2 - N1
B 4 - N1
C 4 A N2
D 5 A, B N2
E 6 C, D N3

Pr N. CHEIKH 61
 Taches Durée Ant Niv

Construction du réseau MPM A 2 - N1

B 4 - N1
C 4 A N2
D 5 A, B N2
E 6 C, D N3
0 2 2 2 5
A C
4

2 9 9 6 15 15
E FIN
5
0 0 4 4 4
B D

Date au Date au
plu tôt plus tard
LEGENDE:
Les tâches B, E et D sont des tâches critiques Nom tâche
Pr N. CHEIKH 62
Calcul des marges

Pr N. CHEIKH 63
 Calcul des Marges

•On appelle "marge" d'une tâche le retard qu'il est possible de tolérer dans la
réalisation de celle-ci, sans que la durée optimale prévue du projet global en soit
affectée
•Il est possible de calculer deux types de marges :
 la marge totale
 la marge libre.

Pr N. CHEIKH 64
 Calcul des Marges

Marge totale
• La marge totale d'une tâche indique le retard maximal que l'on peut admettre dans sa
réalisation (sous réserve qu'elle ait commencé à sa date au plus tôt) sans allonger la
durée optimale du projet.

Pr N. CHEIKH 65
 Calcul des Marges

Marge libre
• La marge libre d'une tâche indique le retard que l'on peut admettre dans sa réalisation
(sous réserve qu'elle ait commencé à sa date au plus tôt) sans modifier les date au plus
tôt des tâches suivantes et sans allonger la durée optimale du projet.

Pr N. CHEIKH 66
 Calcul des Marges

Marge libre
Lorsque plusieurs arcs partent d'un même sommet (c'est-à-dire lorsque la réalisation de la
tâche conditionne le début de plusieurs autres tâches indépendantes) il convient de faire ce
calcul pour toutes les tâches succédant à la tâche en question et de retenir comme "marge
libre" de la tâche en question la valeur minimale des marges ainsi déterminées :

Pr N. CHEIKH 67