Optimisation d'un enchainement de productions

[hbb]

Bonjour à tous,
Je reviens vers vous pour un petit coup de pouce sur la suite de mon projet.

Je recherche maintenant à optimiser des enchainements de productions en tenant compte des couts de changements
de ces production (cout d'un passage de la ref A vers la ref B par exemple)

Je ne sais pas si un ou plusieurs résultats peuvent être obtenus par formule.
J'ai indiqué un exemple de résultat qui pourrait être obtenu (à mon avis, c'est l'enchainement le moins couteux... si je ne me suis pas trompé....)

J'ai essayé de donner un peu plus de précisions dans le fichier directement.

merci encore pour votre aide !
bon app'
hbb

 

[ODVJ]

Re : Optimisation d'un enchainement de productions

Bonsoir,

a priori, tu as 3 solutions à 2 184 € :

• D-A-B-A-B-A-B-D-A-C
• D-A-B-A-B-D-A-B-A-C
• D-A-B-D-A-B-A-B-A-C

et 2 184 € est l'optimum.

je dis a priori car excel s'est planté plusieurs fois pour manque de ressource.

(par macro, ce serait beaucoup plus léger)

cordialement

 

[hbb]

Re : Optimisation d'un enchainement de productions

Bonjour ODVJ, le forum,
J'ai oublié de préciser que la 1ère ref à lancer en production doit être la A.
Je dois donc prendre en compte que la dernière ref programmée de la semaine enchaine ensuite sur la 1ère (A) le lundi suivant.

Je suis d'accord avec toi, une macro sera certainement plus adaptée.
Il existe sur le forum des exemples de calcul de "chemin le plus court" : Je pourrais les adapter à mon exemple.
Le problème vient du fait que je peux produire xfois la ref A, x fois la ref B etc... et là, ça ne fonctionne pas.

merci d'avance pour votre aide
Bon dimanche à tous !
hbb

 

[CPk]

Re : Optimisation d'un enchainement de productions

Bonjour...Juste histoire de mettre un caillou dans l'engrenage, les temps de changements ont été au péalable étudiés ou non ?

 

[hbb]

Re : Optimisation d'un enchainement de productions

Bonjour CPk,
Oui, les couts indiqués sont liés à des apports en matière : Ces valeurs sont réelles.
En réalité, les temps de changements de fab sont nuls et réalisés en temps masqués mais génèrent ces dépenses en matières.
a+

 

[ODVJ]

Re : Optimisation d'un enchainement de productions

Bonjour,

si tu dois commencer par la ref A chaque semaine, tu obtiendras les 3 ordonnancements optimaux :
A-B-A-B-D-A-B-D-A-C
A-B-D-A-B-A-B-D-A-C
A-B-D-A-B-D-A-B-A-C
auxquels il faut ajouter le retour au A pour la semaine suivante.
Cela fera un coût de 2837+737 = 3574€

Pour la modélisation de ton problème, vu le faible nombre de références, je te conseille de partir sur une représentation en base 4 des nombres de 0 à 4^9-1.
Remarque : base 4 parce qu'il y a 4 références, qui seront représentées par les chiffres 0 à 3. Puissance 9 parce que la somme des multiplicités vaut 10 et que le premier chiffre est forcé à 0 (Référence A de début de semaine).

Tu ne gardes que les nombres contenant 4 zéros, 3 uns, 1 deux et 2 trois. Il y en a 5040.
Tu élimines ensuite les solutions sans alternance. Il en reste 538 (edit : 316 si on considère qu'un chemin ne peut se terminer en A).
Tu prends la plus petite valeur en coût de ces 538 solutions.

Tout ça se fait sur une feuille de calcul de 262 144 lignes avec quelques filtres.

cordialement

 

[hbb]

Re : Optimisation d'un enchainement de productions

Bonjour ODVJ,
Merci pour ta réponse, j'avoue ne pas tout comprendre...
J'ai commencé à mettre en forme la suite de nombres comme tu l'as indiqué (pas encore finalisé, c'est long...)
Je ne peux pas insérer le fichier d'ailleurs, il fait déjà 13 Go .....
2 questions :
1- Est-ce que cette logique fonctionne quel que soit le nombre de fois que je dois produire les refs A, B, C et D dans la semaine?
2- Est-ce qu'il est possible de confier tout se raisonnement à une macro (plutôt que de devoir faire des tris à chaque ordonnancement ?

merci encore
Hbb

 

[ODVJ]

Re : Optimisation d'un enchainement de productions

Bonjour,

1) la logique restera la même mais sa mise en œuvre non, à cause de l'explosion combinatoire.
Sur des petites instances tu peux te permettre de tester toutes les solutions et ainsi être sûr d'obtenir la meilleure. Si tu augmentes le nombre de références et/ou la multiplicité, il faudra peut-être changer d'approche et d'algorithme et abandonner la certitude de l'optimum.
Jusqu'où envisages-tu de pousser la multiplicité de production des références ?

2) bien sûr, je pensais même que les poilus de la macro t'en auraient déjà fournie une.

Pour le modèle que je t'ai proposé, tu peux le voir comme le cheminement entre 4 villes A, B, C et D qu'il faut traverser respectivement 4, 3, 1 et 2 fois. (là, je ne compte pas le retour en A pour la semaine suivante)

La somme des multiplicités te donne la longueur du chemin (10 villes, 9 liaisons).

Comme le chemin doit commencer en A, tu peux retirer la ville de départ et limiter ta recherche exhaustive sur les chemins de longueur 9 (9 villes, 8 liaisons).

Il doit y avoir alternance de villes dans le chemin.
Les chemins (ceux réduits à 9 villes) ne peuvent donc commencer par A.

Maintenant, le passage en base 4 :
Tu as 4 villes. Tu peux les coder de 0 à 3.
Tu as 9 étapes dans un chemin réduit. Tu peux coder un chemin comme un nombre de 9 chiffres.
L'alternance interdit de commencer un chemin par 0.

Les chemins admissibles seront donc les nombres de 9 chiffres écrits en base 4, compris entre 101010101 et 323232323 (soit 69 905 à 244 667 en base 10) qui respecteront à la fois l'alternance et la multiplicité de présence des chiffres 0 à 3.

Tu vois ainsi qu'une macro qui bouclerait entre 69905 et 244667 passerait en revue tous les chemins.

Si tu passes d'une multiplicité 10 à une multiplicité 20, tu devras boucler de 73 milliards à 256 milliards...... là, même en élaguant à tour de bras, ça commence à sérieusement piquer les yeux.

cordialement

 

[hbb]

Re : Optimisation d'un enchainement de productions

Bonsoir ODVJ,
Je suis particulièrement impressionné par tes explications et par le temps que tu y as consacré !
Je ne veux surtout pas te décevoir mais j'ai peur que mon niveau en math ne me permette pas d'exploiter au quotidien ce type de raisonnement.
De plus, n'étant pas le seul à utiliser ce fichier, ça risque d'augmenter les complications...

Je souhaiterais que certains "poilus de la macro" m'aiguillent vers une programmation un peu plus simplifiée et surtout "automatique."
Malgré tout, je t'adresse un Grand merci pour tes explications, c'est toujours très enrichissant !

Bonne soirée
Hbb

 

[ODVJ]

Re : Optimisation d'un enchainement de productions

Bonsoir,

voilà une macro qui résout le problème en 1 seconde et des babioles.
je n'ai cependant pas cherché à faire quelque chose de paramétré selon ce qui peut varier chez toi.

donc, ça fonctionne sur le cas que tu as présenté mais uniquement sur ce cas.

à toi de dire ce que tu veux faire varier dans la vraie vie.

cordialement

 

[hbb]

Re : Optimisation d'un enchainement de productions

Merci ODVJ, je vais prendre le temps de regarder comment ça fonctionne.
Bonne soirée

 

[hbb]

Re : Optimisation d'un enchainement de productions

Bonsoir à tous,
Désolé d'insister, j'aime pas trop ça...

ODVJ a eu la sympathie de me proposer une solution : Malheureusement, les données d'entrée sont variables d'une semaine à l'autre (nombre de fois que chaque ref doit être produite)

Est-ce qu'une solution vous semble possible par macro ?
J'ai pas mal regardé sur le net (en l'occurrence l'algorythme de Dijkstra sur le principe du chemin le plus court qui pourrait être adapté) mais je m'y perds et dans toutes les macros présentées, il est question de passer une seule fois par chaque point.

Merci encore pour votre aide,
bonne soirée
Hbb

 

[ODVJ]

Re : Optimisation d'un enchainement de productions

Bonsoir à tous,

T'inquiète pas, tu as raison d'insister.

Moi aussi je vais insister une dernière fois car tu ne réponds pas à mes 2 questions :
1) sur l'amplitude des multiplicités de production des références? Leur somme peut monter jusqu'à combien?
2) le nombre de références est toujours de 4 ou il peut évoluer?

Maintenant, pour ton problème :
Tu ne cherches pas le plus court chemin mais plutôt le circuit hamiltonien le moins coûteux (problème du voyageur de commerce)
Même si ce problème a été très étudié, il devient vite retors avec des petites instances (quelques dizaines de références).

Le graphe dans lequel tu recherches ce circuit est issu du graphe complet de tes références (A, B, C et D) mais avec des répétitions de tes sommets à hauteur de la multiplicité de chaque référence.

Pour l'exemple que tu donnes avec 4*A, 3*B, 1*C et 2*D, ton graphe aura les sommets {A1, A2, A3, A4, B1, B2, B3, C, D1, D2}.
Ta matrice d'adjacence deviendra et tu pourras lui faire subir les macros que les contributeurs te proposeront.

Tu remarqueras que j'ai ajouté des valeurs énormes aux intersections des Ai, Bi, C et Di avec eux-mêmes pour garantir l'alternance de références.
Ce nouveau graphe est ainsi devenu complet (tout sommet est connecté avec tout autre sommet).

Dans les graphes complets orientés à n sommets, il y a (n-1)! chemins hamiltoniens. Tu imagines ce que ça donne à partir d'une quinzaine de sommets......
Les algo exhaustifs comme celui que je t'ai proposé ne tiennent plus la route (d'où mes questions sur les multiplicités dans la vraie vie).

Il faut passer soit par des heuristiques, soit par un solveur.
Le solveur d'excel est limité à 200 variables et 100 contraintes. Donc tu peux l'oublier.

Je viens de tester avec le solveur GLPK et le résultat pour 10 références est obtenu en moins de 2 secondes.
Avec 16 références, il a fallu attendre 13 secondes.
Il y a donc de l'espoir si tes multiplicités restent raisonnables.

Je te laisse ingurgiter tout ça, mais sache qu'il est possible de piloter GLPK via VBA de façon à masquer toute la cuisine technique.

cordialement

 

[hbb]

Re : Optimisation d'un enchainement de productions

Bonsoir ODVJ,
Excuse-moi de ne pas avoir répondu à ces 2 questions.
- Le nombre de refs peut varier de 2 à 6 d'une semaine à l'autre (ok, avec 2 refs, le calcul de tête ne sera pas très compliqué !)
- Pour ce qui est de la multiplicité, c'est difficile à dire, chaque ref peut être renouvelée en production de 1 à 30 fois...
En règle générale, on se situe plus à environ 6-10 fois mais je dois m'assurer que l'outil ne plantera pas à la moindre évolution des besoins de fab....

Visiblement, le sujet n'est pas aussi évident que je l'imaginais au départ.
Moi qui pensais que quelques lignes de Vba auraient été suffisantes !!!
merci,
bonne soirée
hbb

 

[ODVJ]

Re : Optimisation d'un enchainement de productions

Bonsoir,

Je viens de tester avec une instance 4 Références et multiplicité 12, 3, 9, 15.
5,324 secondes pour le résultat.
ça semble tenir la route.....

Il faudrait que tu fournisses les matrices de coût pour 6 références ainsi qu'une vingtaine d'exemples de multiplicité (réels ou exagérés) pour chaque situation de références hebdo : 3, 4, 5 et 6.

Je suppose que les références d'une semaine à 3 références sont incluses dans les références d'une semaine à 6 références. Sinon, il faudra fournir autant de matrices des coûts que nécessaire.

Pour ce qui est d'une macro qui résoudrait ton problème, il faut peut-être attendre un peu que les autres membres du forum se manifestent.

Sinon, le principe de résolution pourrait être le suivant :
1) selon les multiplicités et les références d'une semaine, créer la matrice des coûts de dimension "somme des multiplicités"
2) générer le fichier data pour glpk
3) lancer par un shell.execute un fichier .bat qui lui même lance glpk avec les fichiers modèle et data, avec redirection de la sortie dans un fichier texte
4) traiter le fichier résultat pour le rendre présentable sous excel.

cordialement