Introduction aux problèmes d’ordonnancement · EDD (Earliest Due Date) : priorité à la tâche ayant la plus grande date de fin

12/11/2015

1

4.1. Notions d’ordonnancement

4.2. Définitions

4.3. Modélisation

4.4. Méthodes de résolution

4.5. Problèmes types

Chapitre 4: Introduction à

l’ordonnancement

IV.1. Notions d’ordonnancement (1)

Ordonnancer = Organiser dans le temps la réalisation d’un

ensemble d’activités compte tenu :

De contraintes temporelles (délais, échéances, enchainement)

De contraintes de ressources (disponibilité, utilisation)

Eléments d’un problème d’ordonnancement

Un ensemble d’activités (ou tâches)

Un ensemble de ressources

Des contraintes sur les activités et les ressources

Un (des) critères d’optimisation (le plus souvent)

Par exemple : minimiser la durée de réalisation des tâches, minimiser les retards,

etc.

2


3

Gestion de projets

Gestion de services

Gestion de ressources humaines

Emplois du temps

Gestion de production

Organisation d’ateliers


4

Ordonnancement

Obtention d’un plan prévisionnel défini pour un horizon temporel

Les données sont connues et fixes sur l’horizon temporel

Ordonnancement statique

Exécution du plan prévisionnel (lancement)

Nécessité d’un contrôle de l’exécution

Ajustements éventuels du plan prévisionnel

Pour absorber les aléas

Utilisation des marges du plan prévisionnel

Remise en cause du plan prévisionnel

Ordonnancement dynamique

12/11/2015

2

Exemple

5

IV.2. Définitions (1)

6

Une activité ou tâche :

Entité élémentaire d’un travail à réaliser

Formalisation

Tâches préemptive / Non préemptive

Une tâche est dite préemptive si sa réalisation peut être morcelée dans le temps

Plusieurs dates de début et de fin (par morceaux)


7

Chaque activité nécessite une (des) ressource(s)

Résoudre un problème d’ordonnancement :

Fixer les dates de début de chaque tâche

Remarque :

les ressources nécessaires à chaque activités peuvent ne pas être fixée un ensemble de ressources possibles

Résoudre un problème d’ordonnancement

Fixer les dates de début de chaque activité

Fixer la(es) ressource(s) pour chaque activité


8

Une ressource :

Un moyen technique ou humain permettant la réalisation d’une tâche

La quantité de chaque ressource est limitée

Formalisation

La quantité disponible peut varier dans le temps :

12/11/2015

3


9

Types de ressources

Renouvelables :

Après utilisation pour la réalisation d’une tâche, les ressources sont à nouveau

disponibles en même quantité

Consommables :

Chaque utilisation de ressource fait diminuer la quantité de ressource disponible

Pour les ressources renouvelables :

Ressources disjonctives

Une ressource disjonctive est non partageable. Elle ne peut réaliser qu’une seule tâche à

la fois

Ressources cumulatives

Une ressource cumulative peut être utilisée simultanément par plusieurs tâches


10

Différentes contraintes en ordonnancement

Commerciales :

certaines tâches doivent être réalisées pour une date donnée

Technologiques :

Certaines tâches ne peuvent débuter tant que d’autres ne sont pas achevées

Matérielles

Effectif limité pour le personnel, nombre de ressources matérielles limité

Financières :

Le budget est limité


Contrainte :

Exprimer des restrictions sur les valeurs possibles des variables du problème

Ici les variables sont les dates de début des tâches

Deux familles de contraintes en ordonnancement

Contraintes temporelles

Temps allouée pour la réalisation

Succession entre tâches

Contraintes de ressources

Capacité et disponibilité des ressources

Demande en ressources par tâche

11



Début au plus tôt (release date )

Fin au plus tard (due date )

Succession entre tâches

Simple, avec attente, avec chevauchement, avec délai maximal, sans délai

Contraintes de ressources (renouvelables)

Ressource disjonctive : (machine)

réalise 1 seule tâche à la fois

Ressource cumulative :

ressource ayant une capacité > 1 et pouvant accepter des demandes > 1

12

12/11/2015

4


Représentation d’un ordonnancement : Diagramme de Gantt

Abscisse : le temps

Ordonnée : les tâches en l’absence de contraintes de ressources

Exemple

13

F

E

D

C

B

A

5 10


Représentation d’un ordonnancement : Diagramme de Gantt

Abscisse : le temps

Ordonnée : les ressources

Exemple :

14

m3 A3 B3

m2 B1 A2

m1 A1 B2

5 10

IV.3. Modélisation (1)

15

Graphe X : ensemble de sommets Date de début ( Activités)

1 sommet par activité

1 sommet : Début du projet (S) + 1 sommet Fin du projet (F)

A : ensembles d’arcs Inégalités de potentiels

Exemple : Problème avec 3 tâches telles que :

Donner les contraintes temporelles

Donner le graphe associé

Succession simple :


16

Contraintes :

Graphe

Graphe potentiels-tâches:

Nom des sommets

Nom des activités:

Pourquoi ?:

12/11/2015

5


17

Hypothèse : Ressources renouvelables

Contraintes de ressources disjonctives

2 tâches utilisant la même ressource disjonctive ne peuvent être réalisées

simultanément

Expression sous la forme d’inégalités de potentiels

Arcs « disjonctifs » dans le graphe potentiels-tâches

ou:

ou:


Illustration des contraintes disjonctives

soit une ressource disponible en quantité

soit 3 activités nécessitant cette ressource avec les quantités :

Il y a 3 paires de tâches en conflit :

D’où les contraintes :

18

Paires de disjonction


19

Contraintes de ressources cumulatives

Généralisation des contraintes de ressources disjonctives

Si alors les tâches de ne peuvent s’exécuter

simultanément

Remarque : vérifier cette contrainte à chaque instant


Illustration des contraintes cumulatives

soit une ressource disponible en quantité

soit 4 activités nécessitant cette ressource avec les quantités :

Ensembles minimaux de tâches en conflit pour la ressource

Attention : non minimal

20

Ensembles critiques

12/11/2015

6


21

Illustration des contraintes cumulatives (suite)

Pour chaque ensemble critique

Un ensemble de contraintes de succession

Ces 2 ensembles critiques =

paires de disjonction

Exercice (1)

Soit le problème d’ordonnancement suivant :

8 tâches telles que : T1 < T2; T3 < T4 < T5; T6 < T7 < T8; T4 < T2

Durées respectives : (3, 4, 2, 2, 4, 6, 4, 1)

Question 1. Donner le graphe potentiels tâches correspondant

Question 2. Quelle est la durée minimale de l’ordonnancement ?

22

Exercice (2)

Ajouter des contraintes de ressources

M1 : T4 et T8; ressource disjonctive

M2 : T2, T5, T7; ressource disjonctive

M3 : T1, T3 et T6; ressource cumulative de capacité 3, utilisation (2, 1, 1)

Question 3. Donner le graphe disjonctif correspondant

23

Exercice (3)

Soit une solution pour le partage des ressources

Sur M1 : T4 < T8

Sur M2 : T7 < T5 ; T2 < T5; T7 < T2

Sur M3 : T3 < T1

Question 4. Représenter cette solution sur le graphe

Question 5. Donner la durée de l’ordonnancement

24

12/11/2015

7

Exercice (4)

Question 6. Donner le diagramme de Gantt

25

m3

m2

m1

2 4 6 8 10 12 14 16 18 20

Exercice (6)

Soit une autre solution pour le partage des ressources

Sur M1 : T8 < T4

Sur M2: T5 < T7; T7 < T2; T5 < T2

Sur M3 : T3 < T1

Représenter cette solution par un graphe

Faire le diagramme de Gantt

Quelle est la nouvelle durée de l’ordonnancement ?

26

Exercice (7)

27

m3

m2

m1

2 4 6 8 10 12 14 16 18 20

IV.3. Modélisation … le retour (1)

Modèle de programmation linéaire

Données

Objectif


28

12/11/2015

8


Modèle de Programmation Linéaire

Données complémentaires :

Contraintes de ressources disjonctives :

Domaine des variables

29


Fonctions objectifs classiques

Makespan

Retards

Retard algébrique

Retard vrai

30


Modèle de programmation linéaire

Variables continues (PL) : méthode du Simplexe

Problème « simple » en termes de complexité

Ici :

Variables discrètes

Variables mixtes

Problèmes difficiles en termes de complexité

PL en Nombres Entiers (PLNE)

PLNE en 0/1

PL variables mixtes

31

IV.4. Méthodes de résolution (1)

Cas des problèmes « faciles »

Il existe un algorithme en temps polynomial pour le résoudre

Exemple : Ordonnancement de projet / Plus court chemin, ….

Cas des problèmes « difficiles »

Méthodes exactes obtention de la solution optimale

Temps de calcul exponentiel dans le pire cas

Méthodes approchées obtention d’une solution (qualité ?)

Heuristiques

Méta-Heuristiques

32

12/11/2015

9


Méthode exacte par séparation et évaluation

Principe (problème de minimisation)

Partir de l’ensemble de solutions

Séparer cet ensemble en 2 sous-ensembles

Evaluer chaque ensemble borne inférieure (meilleur cas)

Pour chaque sous-ensemble : différents tests

Test d’admissibilité : contient-il des solutions ?

Test de résolution : contient une seule solution (admissible) ? : a-t-elle un

meilleure cout que celle déjà mémorisée ?

Test de dominance : cout supérieur au cout de la solution mémorisée ?

33

Branch and Bound


Exemple de Branch and Bound (B&B)

34

Méthode arborescente

Evaluation : relâcher des

contraintes (ie. entiers

réels) et résoudre un PL


Méthodes approchées

Heuristiques gloutonnes

Parfois appelées méthodes de listes (en ordonnancement)

Principe

Instanciation progressive des variables

Ne jamais remettre en cause les choix effectués

Doit garantir l’admissibilité de la solution obtenue

Se donner un ordre de priorité sur les variables (et les valeurs)

Les contraintes satisfaites lors d’une étape de résolution ne peuvent être remises

en cause lors d’étapes suivantes

Pas de garantie d’optimalité

35


Exemple d’heuristique gloutonne en ordonnancement

Objectif : minimisation du Makespan

1. Se placer à la date t (= minimum des dates de début au plus tôt)

2. Construire l’ensemble E des tâches pouvant être réalisées à t

3. Sélectionner la tâche i de plus grande priorité

4. Placer la tâche i au plus tôt sur la ressource k qui la réalise (en respectant les

contraintes de partage de ressources et de précédence)

5. Recommencer en 3 tant qu’il reste des tâches dans E

6. Recommencer en 2 en mettant à jour t (prochain minimum des dates de début

au plus tôt)

36

12/11/2015

10


Quelques règles de priorité en ordonnancement

EDD (Earliest Due Date) : priorité à la tâche ayant la plus grande date de fin

SPT (Shortest Processing Time) : priorité à la tâche ayant la plus petite durée

LPT (Longest Processing Time) : priorité à la tâche ayant la plus grande durée

Différentes règles de priorité différentes solutions

Priorités statiques / dynamiques

37

Exercice (1)

Soit le problème d’ordonnancement suivant

38

Exercice (2)

Question 1. Calculer la durée minimale de l’ordonnancement (sans prendre en

compte les contraintes de ressource)

Question 2. Donner les dates de début au plus tôt et au plus tard

Question 3. Appliquer une heuristique gloutonne en classant les tâches par dates

de début au plus tard croissantes

Question 4. Donner le diagramme de Gantt associé et donner la valeur du

Cmax de la solution obtenue.

Question 5. A-t-on l’optimum ? Une borne supérieure ? Une borne inférieure ?

39

R2

R1

10 20 30 40 50


Performance d’une méthode approchée (en minimisation)

Qualité de la solution trouvée

Une solution avec une valeur

Borne supérieure de l’optimum

Comparaison avec

Valeur optimale

Borne inférieure

Une méthode approchée ne peut pas trouver mieux qu’une méthode exacte

40

12/11/2015

11


Performance d’une méthode approchée

Temps de calcul

Une méthode approchée est plus rapide qu’une méthode exacte

Solutions réalisables

Tester si les solutions retournées respectent les contraintes du problème !

Evaluation a posteriori

Evaluation statistique

A effectuer sur plusieurs jeux de données de tailles différentes

41

IV.5. Problèmes d’ordonnancement types (1)

Classification des problèmes d’ordonnancement

3 paramètres :

L’organisation des ressources

Les caractéristiques des tâches

Les objectifs

Organisation des ressources

Machine unique

Machines parallèles

Type atelier (organisation du passage de produits sur les machines)

Flow shop

Job shop

Open shop

Général

42


43

M1

M2

Mk

Entrée

Atelier

Sortie

Atelier M1 M2

M3

M4

M1 M2 M3 M4


Caractéristiques des tâches

Préemptives ou non

Forme des contraintes de précédence (chaine, ….)

Contraintes de dates de disponibilité

Contraintes de dates dues

…..

Objectifs considérés

Makespan

Retard

Avance

etc

44

12/11/2015

12


Problème à 1 machine

1 machine (disjonctive)

Ensemble de n tâches

Exemple : étude d’une machine goulet

Un problème trivial

Minimiser le makespan : tout ordre entre les tâche donne la même durée

Exemple :

45

1 2 3 4 5

2 5 11 16 17


Problème à 1 machine avec dates dues

Problème facile :

Minimiser le retard (algébrique)

Il existe une heuristique gloutonne permettant d’obtenir la solution optimale :

Trier les tâches par dates dues croissantes (EDD) - Jackson

Exemple : Appliquer la règle EDD et donner la valeur de (2)

46

M

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17


Problème à 1 machine avec dates dues et minimisation de la

somme pondérée des retards

Objectif : avec et

Illustration d’une méthode exacte (Branch and Bound)

Construire un ordonnancement par la fin (vis à vis de l’objectif à atteindre)

Etat initial : aucune décision d’ordonnancement

Séparation :

o placer une opération en dernier ( n branches)

Evaluation :

o valeur de la fonction objectif pour les opérations déjà placées

47


Exemple :

48 48

12/11/2015

13


Problème de Flow Shop

Ensemble de produits (travaux ou job) : n

Ensemble de machines : m

Chaque Job : m opérations

L’ordre de passage sur les ressources est identique pour tous les jobs

Variante : Flow Shop Hybride : plusieurs machines / niveau

49

M1 M2 M3 M4

M1 M2

M3

M4

M5

M6

M7


Exemple d’un problème de Flow Shop facile

2 machines – Minimisation du makespan (durée totale)

Heuristique conduisant à la solution optimale (Johnson)

Pour M1 : Faire passer les opérations le plus vite possible pour limiter le temps

d’inactivité de M2 SPT sur M1

Pour M2, prendre l’ordre LPT pour éviter que M2 attende trop que M1 transfère

des opérations

50

M1 M2


Heuristique de Johnson

Faire deux ensembles d’opérations

Trier les opérations de avec SPT sur

Trier les opérations de avec LPT sur

Ordre total :

Identique sur M1 et M2 flow shop de permutation

Résoudre l’exemple et donner le diagramme de Gantt

51


Problème de Job Shop

Ensemble de produits (travaux ou job) : n


Chaque Job : m’ opérations : ordre de passage quelconque

Exemple

52

M1 M2

M3

J1

J2

J3

12/11/2015

14


Problème de Flox Shop ou Job Shop

Quelques cas particuliers faciles

Voir la littérature en ordonnancement

Sinon problèmes difficiles

Problème d’Open Shop

Ensemble de travaux : n


Chaque job passe sur une ensemble de machines dans un ordre quelconque

non spécifié

53


Exemple

Soit un problème de job shop

Appliquer l’heuristique suivante :

Classer les tâches par date de début

croissante (en cas d’égalité classer

les tâches par durée croissante)

Placer au plus tôt sur la ressource

demandé

Ordre des tâches :

Diagramme de Gantt :

54

0 *

1

7

4

2

8

5

3

9

6

m1 m2 m3

m1

m3 m2

m3 m1 m2

10 35

250

0

0

15 16 12

11 12

21

10 20 30 40 50 60 70 800 90 100 110 120

M1

M2

M3


Donner le séquencement obtenu sur les ressources

Donner les dates de début au plus tôt / au plus tard et le chemin critique

55

0 *

1

7

4

2

8

5

3

9

6

m1 m2 m3

m1

m3 m2

m3 m1 m2

10 35

250

0

0

15 16 12

11 12

21

Exercice (1)

Soit un atelier réalisant 3 types de papier peint différents. Chaque type de papier est fabriqué sous forme d’un rouleau de papier continu qui passe sur plusieurs machines (chacune imprimant une couleur différente)

L’ordre de passage (et la durée) sur les machines dépend du type de papier.

Type 1 : Machine 1 (bleu, 45) puis Machine 3 (jaune, 10)

Type 2 : Machine 2 (vert, 10), Machine 1 (bleu, 20) puis Machine 3 (jaune, 34)

Type 3 : Machine 2 (vert, 17) puis Machine 3 (jaune, 28)

Une machine ne peut traiter qu’un seul type de papier à la fois et qu’un type de papier ne peut passer que sur une machine à la fois

On souhaite réaliser ces 3 types de produits avec une durée minimale

Quel est le problème d’ordonnancement ?

Donner un modèle linéaire

Donner un modèle de graphe

Proposer une méthode de résolution

56

12/11/2015

15

Exercice (2)

Modèle de PLNE

57

Exercice (3)

Modèle de Graphe

58

Exercice (4)

Résolution

Solution 99 - Type 1 : 44, 89 / Type 2 : 0, 10, 55 / Type 3 : 10, 27

59

Documents

Introduction aux problèmes d’ordonnancement · EDD (Earliest Due Date) : priorité à la tâche ayant la plus grande date de fin