Mise en lots et ordonnancement
Cette démo porte sur un problème courant dans l'industrie. Il consiste à regrouper les ordres de fabrication (OF) d'une même famille de produits en batches de capacité fixe et d'une durée de 100 min (fournée, cuve), puis à les ordonnancer sur une ligne de production, famille par famille. Changer de famille demande un temps de réglage. Pour limiter les risques de rupture de stock, certains OF sont classés urgents, et tout batch qui en contient un est urgent et prioritaire. Trois objectifs sont minimisés par ordre de priorité : le nombre de batches urgents, le nombre total de batches, puis le temps de réglage total. Mon solveur, écrit en C++, calcule une solution optimale et la compare à une règle d'atelier classique.
- Solveur :
- méthodes exactes, branch and bound et programmation dynamique (Held-Karp).
- Règle d'atelier :
- heuristique gloutonne. Les OF sont affectés un à un, du plus long au plus court en commençant par les urgents, au batch de leur famille le plus rempli pouvant les contenir, sinon à un nouveau batch. Les familles sont séquencées par plus proche voisin selon le temps de réglage.
Le temps affiché correspond uniquement à la résolution par le solveur, effectuée sur un seul cœur d'un serveur virtuel partagé.
Résultat
- Batches urgents 3 comme la règle d'atelier Remplissage moyen : 92 % au lieu de 85 %
- Batches 5 −17 % au lieu de 6 Remplissage moyen : 77 % au lieu de 64 %
- Temps de réglage 110min −27 % au lieu de 150 min
Détail batch par batch
Solveur
| Famille | N° | OF | Remplissage |
|---|---|---|---|
| C | 1! |
| 80 % |
| Réglage C → B : 40 min | |||
| B | 2! |
| 100 % |
| Réglage B → A : 35 min | |||
| A | 3! |
| 95 % |
| Urgents terminés après 3 batches | |||
| A | 4 |
| 20 % |
| Réglage A → B : 35 min | |||
| B | 5 |
| 90 % |
Règle d'atelier
| Famille | N° | OF | Remplissage |
|---|---|---|---|
| A | 1! |
| 95 % |
| Réglage A → B : 35 min | |||
| B | 2! |
| 80 % |
| Réglage B → C : 40 min | |||
| C | 3! |
| 80 % |
| Urgents terminés après 3 batches | |||
| Réglage C → B : 40 min | |||
| B | 4 |
| 85 % |
| 5 |
| 25 % | |
| Réglage B → A : 35 min | |||
| A | 6 |
| 20 % |
- OF urgent
- OF non urgent qui complète un batch urgent
- remplissage du batch