Introduction aux problèmes d’ordonnancement

Terminologie

Travail ou Job : ➔ le système de production doit assurer une liste 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é). 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 qu’une tâche à la fois (machine-outil, robot manipulateur). • Cumulatives (ou partageables) qui peuvent être utilisées par plusieurs tâches simultanément (équipes d’ouvriers, poste de travail).

la

;

Terminologie

Objectifs: Quelle est la fonction à optimiser ?

Exemples : « minimiser le temps » Temps d’attente 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 fin d’exécution des tâches.

Exemple: « minimiser l’utilisation des ressources » • Ordonnancement économique : utiliser le nombre minimal de ressources. • Réseau: Optimiser l’utilisation de la bande passante. • Problème de transport : minimiser les distances parcourues.

Récapitulatif

Objectifs de l’ordonnancement

• Optimiser l’utilisation des moyens nécessaires et les rendre disponibles.

• Lancer les travaux aux moments choisis.

• Contrôler l’avancement 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:

L’ordonnancement 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

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 d’ordonnancement 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:

𝛼|𝛽|𝛾

Où:

𝛼: environnement ressources (nombre, type, etc.).

𝛽: les caractéristiques des tâches (précédence, date d’arrivée, etc).

𝛾: le (ou les) critère(s) à optimiser.

𝛼|𝛽|𝛾

Une classification très répandue des ateliers, du point de vue ordonnancement, est basée sur

les différentes configurations (le nombre et l’ordre) des machines et par conséquent, sur la

valeur de 𝛼 choisie . Les problèmes les plus connus sont ceux:

• Problèmes à machine unique

• Problèmes à machines parallèles

• Problèmes d’ateliers:

• Ateliers à cheminement unique (Flow Shop).

• Ateliers à cheminements multiples (Job Shop).

• Ateliers à cheminements libres (Open Shop).

• Autres configurations.

𝛼|𝛽|𝛾

Problèmes à machine unique: Dans ce cas, l’ensemble des tâches à réaliser est fait par une seule machine. Les tâches 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 configurations est le cas où on est devant un influence l’ensemble du système de production comprenant une machine goulot qui processus. L’étude peut alors être restreinte à l’étude de cette machine.

𝛼|𝛽|𝛾

Problèmes à machines parallèles : Dans ce cas, on dispose d’un ensemble de machines pour réaliser les travaux. Les travaux se composent d’une 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. 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.

𝛼|𝛽|𝛾

Problèmes à machines parallèles : Dans ce cas, on dispose d’un ensemble de machines pour réaliser les travaux. Les travaux se composent d’une 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. 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.

On distingue trois types de machines: ➢ Machines identiques 𝑃𝑚 : la durée d’exécution est la même pour les toutes les machines

et pour toutes les tâches.

➢ Machines uniformes 𝑄𝑚 : chaque machine a une vitesse d’exécution propre et constante. "𝑙𝑎 𝑑𝑢𝑟é𝑒 𝑑′𝑒𝑥é𝑐𝑢𝑡𝑖𝑜𝑛 𝑣𝑖𝑡𝑒𝑠𝑠𝑒 𝑑𝑒 𝑡𝑟𝑎𝑖𝑡𝑒𝑚𝑒𝑛𝑡 𝑑𝑒 𝑙𝑎 𝑚𝑎𝑐ℎ𝑖𝑛𝑒" est le même pour

Τ

Le rapport tous les travaux d’une même machine.

➢ Machines indépendantes 𝑅𝑚 : la vitesse d’exécution est différente pour chaque machine

et pour chaque travail.

𝛼|𝛽|𝛾

Problèmes d’ateliers « Flow Shop (𝜶 = 𝑭) »: C’est 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é d’un ensemble de tâches qui doivent s’exécuter sur les mêmes machines dans le même ordre et une seule fois.

𝛼|𝛽|𝛾

Problèmes d’ateliers « Flow Shop (𝜶 = 𝑭) »: C’est 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é d’un ensemble de tâches qui doivent s’exé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 à l’exception des versions avec deux machines et certains

cas particuliers avec trois machines.

• Une grande productivité mais une faible flexibilité.

𝛼|𝛽|𝛾

Problèmes d’ateliers « Job Shop (𝜶 = 𝑱) »: C’est 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 d’opérations n’est pas forcément le même pour tous les jobs. • Chaque job a son propre ordre de passage sur les machines.

Problèmes d’ateliers « Job Shop (𝜶 = 𝑱) »:

𝛼|𝛽|𝛾

Problèmes d’ateliers « Open Shop (𝜶 = 𝑶) »: C’est un atelier à cheminements libres où: • Le nombre d’opérations n’est pas forcément le même pour tous les jobs. • L’ordre de passage sur les machines est totalement libre.

Problèmes d’ateliers « Flow Shop Hybride »:

𝛼|𝛽|𝛾

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 d’ateliers « Flow Shop Hybride »:

𝛼|𝛽|𝛾

S t o c k s

𝛼|𝛽|𝛾

Traduit la relation (si elle existe) entre les différents tâches considérées. Parmi les relations les plus fréquentes on distingue: • La préemption des tâches: on interrompe l’exécution d’une tâche et on commence une autre tâche, quand on reprend la tâche interrompue, on termine l’exé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 d’opération à la salle de réveil sans attente.

𝛼|𝛽|𝛾

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,…

Exemples de critères liés au temps :

𝛼|𝛽|𝛾

• Temps de circulation (flowtime) : c’est le temps qu’une 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): c’est le temps nécessaire pour compléter l’ensemble de toutes

les n tâches.

• Retard algébrique (tardiness): Le retard d’une 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

• 𝑛 tâches, chaque tâche est indicées par 𝑖

• 𝑚 machines, chaque machine est indicées par 𝑗

• 𝑟𝑖 (release date) : une date de début au plus tôt

• 𝑝𝑖 : une durée de la tâche 𝑖

• 𝑝𝑖𝑗 (processing time): une durée de la tâche 𝑖 sur la machine 𝑗

• 𝑑𝑖 (due date) : une date de fin souhaitée ((au delà de cette date promise au client, on

encourt des pénalités – due date-).

• 𝑤𝑖 (weight) : un poids relatif (il peut traduire l’importance ou poids des clients).

Notations : objectifs et mesures de la performance

Les critères d’optimisation s’expriment en fonction des dates de fin des tâches (ou jobs):

•

•

𝑡𝑖: date de début de la tâche i

𝑡𝑖𝑗: date de début de la tâche i sur la machine j

• 𝐶𝑖 = 𝑡𝑖 + 𝑝𝑖: date de fin d’exécution de la tâche i (sur une seule machine)

• 𝐶𝑖𝑗 = 𝑡𝑖𝑗 + 𝑝𝑖𝑗: date de fin d’exécution de la tâche i sur la machine j et donc,

𝐶𝑖 = Max 𝑡𝑖𝑗 + 𝑝𝑖𝑗 : date de fin d’exécution de la tâche i sur les machines j (Completion time)

• 𝐶𝑚𝑎𝑥 = max (𝐶𝑖) : la durée totale de l’ordonnancement.

• 𝐹𝑖 = 𝐶𝑖 − 𝑟𝑖 (flow time) :la durée du séjour dans l’atelier (mesure les encours)

• 𝐿𝑖 = 𝐶𝑖 − 𝑑𝑖 (lateness) : le retard algébrique.

• 𝑇𝑖 = max (0, 𝐶𝑖 − 𝑑𝑖 ) (tardiness) : le retard absolu.

• La pénalité unitaire de retard 𝑈𝑖 = 0 si 𝐶𝑖 ≤ 𝑑𝑖 , 𝑈𝑖 = 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'œil :

• 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|𝑃𝑟𝑒𝑐|𝐶𝑚𝑎𝑥

Minimisation du makespan sur une seule machine avec des contraintes de précédence

1|𝑃𝑟𝑚𝑝|𝐶𝑚𝑎𝑥

Minimisation du makespan sur une seule machine avec des contraintes de préemption

𝑃𝑚 || ෍ 𝐶𝑖

𝑄𝑚 || ෍ 𝐶𝑖

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||𝐶𝑚𝑎𝑥

• Un problème à 1 seule machine • Objectif: minimiser le makespan 𝐶𝑚𝑎𝑥

𝑖 𝑝𝑖

1

3

2

4

3

7

M1

1

2

3

4

2

4

0 3 7 14 16

𝐶𝑚𝑎𝑥 = 16

1|𝑟𝑖|𝐶𝑚𝑎𝑥

• Un problème à 1 seule machine • Objectif: minimiser le makespan 𝐶𝑚𝑎𝑥 sous contrainte de disponibilité

𝐶𝑚𝑎𝑥 = 18

M1

1

2

𝑖 𝑝𝑖 𝑟𝑖

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

𝐶𝑚𝑎𝑥 = 16

𝑃2 |𝑟𝑖|𝐶𝑚𝑎𝑥

• Un problème à 2 machines parallèles. • Objectif: minimiser le makespan 𝐶𝑚𝑎𝑥 sous contrainte de disponibilité

𝑖 𝑝𝑖 𝑟𝑖

1

2

1

2

2

0

3

4

0

𝐶𝑚𝑎𝑥 = 5

M1

M2

3

0 4

1

2

0 1 3 5

Comment avoir l’ordonnancement 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 l’espace mémoire requis par

l’algorithme

𝐶𝑜𝑚𝑝𝑙𝑒𝑥𝑖𝑡é 𝑒𝑛 𝛼

𝐶𝑜𝑚𝑝𝑙𝑒𝑥𝑖𝑡é 𝑒𝑛 𝛾