Problèmes d’ordonnancement des ateliers de type 1|𝛽|𝛾

Problèmes d’ordonnancement de type 1

Les problèmes d’ordonnancement de type 1 concernent la gestion d'une seule ressource, comme une machine, avec pour objectif d'optimiser un critère spécifique tout en respectant certaines contraintes. Ce document aborde les différentes méthodes de résolution, des exemples pratiques, ainsi que les objectifs à atteindre dans le cadre de ces problèmes d’ordonnancement.

Introduction et problématique générale

Les problèmes d’ordonnancement de type 1|𝛽|𝛾 se concentrent sur l'optimisation d'un critère 𝛾 choisi, tout en respectant les contraintes 𝛽 imposées. La résolution de ces problèmes peut s'appuyer sur des méthodes utilisées pour les problèmes d’ordonnancement à une seule machine. Un aspect intéressant de ces problèmes est la gestion des goulets d’étranglement.

Les objectifs principaux à résoudre incluent :

• Minimisation de la durée totale 𝐶𝑚𝑎𝑥.
• Minimisation des encours σ 𝐹𝑖 ou σ 𝑤𝑖𝐹𝑖.
• Minimisation des retards et des pénalités dues aux retards σ 𝑇𝑖 , σ 𝑈𝑖, 𝐿𝑚𝑎𝑥, 𝑇𝑚𝑎𝑥.

Modélisation mathématique des problèmes d’ordonnancement

Problèmes à étudier

Les problèmes d’ordonnancement à étudier incluent :

• 1|𝑟𝑖|𝑇𝑚𝑎𝑥
• 1 || σ 𝑇𝑖
• 1 || σ 𝑈𝑖
• 1||𝐶𝑚𝑎𝑥
• 1|𝑃𝑟𝑒𝑐|𝐶𝑚𝑎𝑥
• 1|𝑟𝑖|𝐶𝑚𝑎𝑥
• 1 || σ 𝐶𝑖
• 1 || σ 𝐹𝑖
• 1 || σ 𝑤𝑖𝐶𝑖
• 1|𝑟𝑖| σ 𝐶𝑖
• 1|𝑟𝑖, 𝑝𝑟𝑚𝑝| σ 𝐶𝑖
• 1||𝐿𝑚𝑎𝑥

Problème 1||𝐶𝑚𝑎𝑥

Pour le problème 1||𝐶𝑚𝑎𝑥, il existe 𝑛! ordonnancements possibles ayant la même durée, qui est égale à la somme de 𝑝𝑖 σ 𝑝𝑖, ce qui signifie que toutes les solutions sont optimales. L'objectif est de minimiser le makespan 𝐶𝑚𝑎𝑥.

Exemple :

𝐶𝑚𝑎𝑥 = 16
𝑖    𝑝𝑖
1    3
2    4
3    7
4    2

Ordonnancement :

M1
1    2    3    4
0    3    7   14   16

Problème 1|𝑃𝑟𝑒𝑐|𝐶𝑚𝑎𝑥

Pour le problème 1|𝑝𝑟𝑒𝑐|𝐶𝑚𝑎𝑥, il n’existe pas 𝑛! ordonnancements possibles. L'objectif est de minimiser le makespan 𝐶𝑚𝑎𝑥 tout en respectant la précédence des tâches. Supposons que l'on dispose de 6 tâches pour la fabrication d’un produit donné :

• La tâche 3 précède les tâches 2, 4, 5.
• La tâche 3 doit être exécutée après la tâche 1.
• La tâche 5 ne peut être exécutée qu’après les tâches 4 et 6.

Exemple :

𝑖    𝑝𝑖
1    3
2    4
3    7
4    2
5    2
6    8

Ordonnancement :

M1
1    1    1    1
3    3    3    3
𝐶𝑚𝑎𝑥 = 26

Problème 1|𝑟𝑖|𝐶𝑚𝑎𝑥

Pour le problème 1|𝑟𝑖|𝐶𝑚𝑎𝑥, l'objectif est de minimiser le makespan sous contrainte de disponibilité. Un ordonnancement est optimal si les tâches sont rangées dans l’ordre croissant de 𝑟𝑖 (FIFO).

Exemple :

𝑖    𝑝𝑖    𝑟𝑖
1    3    0
2    4    5
3    7    3
4    2    9

Ordonnancement :

M1
1    0    3    5    9    16
𝐶𝑚𝑎𝑥 = 18

Key Takeaways

• Les problèmes d’ordonnancement de type 1 se concentrent sur une seule ressource.
• Les objectifs incluent la minimisation de la durée totale et des retards.
• Différents types de problèmes d’ordonnancement nécessitent des approches spécifiques.

Glossaire

• 𝐶𝑚𝑎𝑥 : Durée totale d'achèvement des tâches.
• σ 𝐹𝑖 : Somme des encours.
• 𝑟𝑖 : Temps de disponibilité des tâches.
• 𝑝𝑖 : Temps de traitement des tâches.
• 𝑈𝑖 : Indicateur de retard.

Questions fréquentes

Qu'est-ce que l'ordonnancement de type 1 ?

L'ordonnancement de type 1 concerne la gestion d'une seule ressource pour optimiser un critère spécifique tout en respectant des contraintes. Il s'applique souvent dans des contextes industriels.

Quels sont les objectifs principaux des problèmes d'ordonnancement ?

Les objectifs principaux incluent la minimisation de la durée totale d'achèvement, des encours, et des retards ou pénalités associés.

Comment résoudre un problème d'ordonnancement avec précédence ?

Pour résoudre un problème d'ordonnancement avec précédence, il est essentiel de respecter l'ordre d'exécution des tâches imposé par les contraintes de précédence tout en minimisant le makespan.

Quelle est la différence entre ordonnancement avec et sans précédence ?

Dans un ordonnancement sans précédence, les tâches peuvent être exécutées dans n'importe quel ordre, tandis que dans un ordonnancement avec précédence, certaines tâches doivent être terminées avant d'en commencer d'autres.

Y a-t-il des exercices corrigés disponibles sur l'ordonnancement ?

Oui, des exercices corrigés peuvent être trouvés dans des ressources académiques et des manuels spécialisés sur l'ordonnancement.