Niveau algorithmique

capacités de production sur parc machine polyvalent

Posté par
yorozu 05-02-12 à 20:05

Bonjour,

Je me permets de vous soumettre un problème qui me rend ma vie professionnelle impossible au quotidien. J'ai le sentiment que seules les mathématiques peuvent en venir à bout, alors je lance ma bouteille à la mer...

Dans l'exemple, nous devons déterminer si les quantités demandées pour les trois références A, B et C peuvent être produites sur trois machines 1, 2 et 3 en l'espace de 24h.
Les capacités (temps de cycle par pièce) des machines sont les suivantes :

machine 1 :
temps de cycle référence A : 120 sec
temps de cycle référence B : 80 sec
temps de cycle référence C : (ne peut pas produire)

machine 2 :
temps de cycle référence A : (ne peut pas produire)
temps de cycle référence B : 110 sec
temps de cycle référence C : 70 sec

machine 3 :
temps de cycle référence A : 130 sec
temps de cycle référence B : (ne peut pas produire)
temps de cycle référence C : 100 sec

Il faut produire en 24h :
1200 pièces A
500 pièces B
800 pièces C

Comment déterminer si les quantités demandées pour chaque référence peuvent être produites ou non ?
Bien entendu, l'exemple est simple, et une répartition manuelle des quantités sur chaque machine par essais successifs peut nous permettre d'aboutir à une solution (si elle existe).
Mais comment procéder de manière "mathématique" ?

Et puis, comment s'en sortir lorsque vous vous trouvez face à un parc d'une douzaine de machines devant produire près d'une centaine de références, avec une polyvalence partielle sur chaque machine, celles-ci ne pouvant produire qu'une vingtaine de références différentes chacune ?

J'espère que ce problème suscitera un certain intérêt et que vous pourrez me donner les pistes d'une solution.
Quoi qu'il en soit, merci d'avoir au moins pris le temps de me lire.

Bonne soirée

Posté par re : capacités de production sur parc machine polyvalent 06-02-12 à 01:28

Bonjour

Machine 1 :

570 pièces A - 68400 s
224 pièces B - 17920 s

Machine 2 :

800 pièces C - 56000 s
276 pièces B - 30360 s

Machine 3 :

630 pièces A - 81900 s

Donc OK. Dans le cas général, ça m'étonnerait qu'il y ait un algorithme exact efficace, il y a trop de variables. Pour arriver à une solution approchée, je pense que le mieux est de commencer à "remplir" par la combinaison machine/pièce qui donne le plus d'économies de temps (ici, c'est la combinaison machine 2/pièce C, qui prend 30% de temps en moins par rapport à la machine 3).

Posté par re : capacités de production sur parc machine polyvalent 06-02-12 à 19:58

Bonjour,

Je suis totalement d'accord avec Bachstelze. Mais je trouve le problème fort intéressant, je risque de me pencher un peu dessus quand j'aurais du temps pour voir s'il y a pas un moyen de faire un petit programme qui trouve une solution en utilisant la force brute (genre listage de solutions avec un test basique à la fin). Ce, bien sure, dans le cas ou personne ne pourrait donner de solution suffisamment satisfaisante pour le cas général.

Posté par re : capacités de production sur parc machine polyvalent 07-02-12 à 12:01

Bonjour,

Merci de vos réponses.
Je travaille également sur la création d'un algorithme. Je pense avoir une idée.
Je le posterai quand il sera fini, pour peu que je trouve un moyen de joindre des fichiers. Ce sera du vba excel, car c'est le seul langage que je connaisse à peu près.
Mais je reste impatient de voir les idées que d'autres pourraient avoir...
Je vais partir sur un exemple avec 20 machines et 200 références à produire, avec une polyvalence complètement disparate sur les différentes machines, en espérant que l'algorithme ne prenne pas des heures pour en venir à bout.

A bientôt

Posté par re : capacités de production sur parc machine polyvalent 07-02-12 à 22:21

Bonsoir,

J'ai avancé sur le sujet.
J'ai trouvé un algorithme capable de distribuer la production de 200 références sur 20 machines différentes, chacune ne pouvant produire que certaines références avec (presque) à chaque fois des temps de cycle différents.
En vba, l'algorithme vient à bout du problème en 35 secondes.
Il parvient à organiser la production de manière à ce qu'elle se fasse avec un temps de marche cumulé des 20 machines de 460.55 heures. (j'ai encore quelques idées pour l'optimiser un peu (env. 5%), mais je me pencherai dessus plus tard)

Alors pour ceux d'entre-vous qui aiment les défis, je demande : QUI DIT MIEUX ?!

Le problème est simple :
- Organiser la production des 200 références sur les 20 machines
- Parvenir à tout produire en 24h maximum
- Obtenir un temps de marche cumulé de toutes les machines de moins de 460.55 heures

Vous trouverez au bout du lien suivant un fichier excel comprenant :
- les données d'entrée (détail des quantités à produire et détail des temps de cycle)
- la proposition de l'algorithme (résultat avec la distribution des pièces et résultat avec la charge en secondes)
... et bien entendu, ne comprenant pas l'algorithme, sinon ce ne serait pas amusant !
http://img74.xooimage.com/views/2/8/4/prod-distrib-315b0b1.xls
(Nota : Toutes les données d'entrée ont été créées de manière aléatoire, autour de la formule "alea()" de Excel)

Et histoire de vous titiller, sachez que je n'ai reçu aucune formation scientifique (si ce n'est les cours de maths du lycée dont je garde un souvenir très douloureux). Alors pour des as des maths comme vous, ça devrait être de la rigolade...!

Allez, bonne soirée...

PS : je sais qu'il y a un écart de 4 pièces sur 21,462... Je n'ai pas encore pris le temps de me pencher dessus...

Posté par re : capacités de production sur parc machine polyvalent 15-02-12 à 22:52

Bonjour,

Je me suis repenché sur ce problème cet après-midi et suis content de voir que vous avez pu trouver une solution.

Pour ma part, je vous propose une solution pour le cas général et qui normalement devrait fournir une solution qui n'est vraiment pas loin de la solution optimale (le but étant de minimiser le temps total de fonctionnement des machines).

Supposons donc que l'on ait $m$ machines et $n$ références en tout.

Notons maintenant $q_i$ la quantité à produire de la référence $i$ ( $1 \leq i \leq n$ ).
On pose aussi $M_{i,j}$ le temps en seconde que met la machine $i$ à produire la référence $j$ , si cette machine ne peut pas produire la référence en question on pose alors $M_{i,j}=86401$ .
On considère maintenant les variables $x_{i,j} \in \mathbb{R}$ qui représenteront le nombre de références $j$ produite par la machine $i$ , et on les mets toutes dans un vecteur de taille $mn$ selon l'ordre lexicographique.

On considère maintenant les blocs matriciels suivants:
- La concaténation des $m$ lignes de la forme
$(\underbrace{0,...,0}_{n(k-1) \text{zeros}},M_{k,1},M_{k,2},...,M_{k,n}, \underbrace{0,...,0}_{n(m-k) \text{zeros}})$
pour $k=1,2,...,m.$
C'est-à-dire un bloc de la forme:
$B_1=\left[\begin{array}{c c c c c c c c c c c} \\ M_{1,1} & \ldots & M_{1,n} & 0& \ldots & \ldots & \ldots &\ldots & \ldots & \ldots & 0 \\ \\ 0& \ldots & 0& M_{2,1} & \ldots & M_{2,n} & 0&\ldots & \ldots & \ldots & 0 \\ \\ &&&&&\vdots & & & & &\\ & & & & &\vdots & & & & &\\ \\ 0&\ldots &\ldots & \ldots & \ldots & \ldots & \ldots & 0 & M_{m,1} & \ldots & M_{m,n} \\ \end{array}\right] \in \mathbb{R}^{m \times mn}$
- La concaténation des lignes qui sont obtenues grâce aux combinaisons linéaires suivantes:
$\sum_{l=1}^m e_{k+m(l-1)}, k = 1,2,...,n,$ où $e_1,e_2,\ldots,e_{mn}$ est la base canonique.
Ainsi ce bloc est de la forme:
$B_2 =\left[\begin{array}{c c c c c c c c c c c c c c} \\ 1& 0 & \dots &\dots & 0 & 1 & 0 & \dots& 0 & 1 & 0 &\dots & \dots& 0 \\ \\ 0 & 1 & 0 & \dots &\dots&0 & 1 & 0 & \dots & 0 & 1 & 0 & \dots & 0\\ \\ \vdots & \ddots & \ddots & \ddots & && \ddots & \ddots & \ddots && \ddots & \ddots & \ddots &\vdots\\ \\ \vdots & & \ddots & \ddots & \ddots && & \ddots & \ddots & \ddots && \ddots & \ddots &0\\ \\ 0& \dots &\dots& 0 & 1 & 0 &\dots&\dots & 0 & 1 & 0 & \dots & 0 & 1 \\ \end{array}\right] \in \mathbb{R}^{n \times mn}$
avec n-1 zéros entre chaque 1.
Avec ces blocs on construit la matrice $A$ donnée par:
$A = \left[\begin{array}{c} -I_{mn} \\ B_1 \\ B_2 \\ -B_2 \end{array} \right]\in \mathbb{R}^{(mn+m+2n)\times mn}$
Maintenant on construit le vecteur b comme la transposée du vecteur:
$(\underbrace{0,\dots,0}_{mn fois},\underbrace{86400, \ldots, 86400}_{m fois},q_1,\ldots,q_n,q_1,\dlots,q_n)\in \mathbb{R}^{mn+m+2n}$

On peut finalement (après tout ces effort de constructions) considéré le programme linéaire suivant en posant $x = (x_{1,1},x_{1,2}, \ldots, x_{m,n})\in \mathbb{R}^{mn}$ :
$\\ min\left\{\sum_{1 \leq i \leq m,1 \leq j \leq n} M_{i,j}x_{i,j} :x\in\mathbb{R}^{mn} \text{ et } Ax \leq b \right\}$
(ou l'inégalité entre deux vecteurs est définie comme la vérification de cette inégalité sur chaque composante)
Notons que l'on peut (même si ce n'est pas réellement nécessaire) montrer que les colonnes de la matrice A sont toutes linéairement indépendantes.
Ainsi on peut sans autre appliquer la méthode Simplex pour trouver une solution minimale de ce problème (il est clair que le problème n'est pas dégénéré vu la nature du problème).

Le seul problème c'est que c'est solution, que je noterai $s$ , est dans $\mathbb{R}^{mn}$ or on veut une solution dans $\mathbb{Z}_+^{mn}$ .

C'est là que l'on perd un peu de l'optimalité de l'algorithme. C'est pourquoi je propose la suivante pour gérer ce petit problème final.
On pose
$t_i = \sum_{1 \leq k \leq m} s_{k,i}-[s_{k,i}], 1 \leq i \leq n$
Ici $[a]$ dénote la partie entière de $a$ , notons aussi que $t_i \in \mathbb{N}$ .
En suite on classe $t_1,\ldots,t_n$ par ordre décroissant. Histoire de simplifier la rédaction de la fin de la réponse je supposerai, sans pertes de généralités, que c'est déjà le cas.
Ensuite on procède comme suit avec k partant de 1:
i) On prend la machine qui nécessite le moins de temps pour produire la référence k ET qui ne travaille pas déjà 86400 s et on lui demande de produire $t_k$ références k.
ii) On a alors deux cas:
- la machine a le temps de tout produire avant d'avoir effectué 86400s de production alors c'est tout bon et on pose $k = k+1$ et on repart de i).
- la machine n'a pas le temps de tout produire. Alors on lui demande de produire le maximum que possible, mettons t références et on repart au point i) en posant $t_k=t_k-t$ .

J'espère que l'un des maître en mathématiques qui arpentent ce forum aura le courage de me lire et de vérifier mes dires. Et je peux concevoir que ne soit pas forcément facile de compréhension pour quelqu'un qui s'est arrêté aux maths du lycée. Néanmoins si vous avez vraiment envie d'implémenter cet algorithme, je dirai qu'une fois la méthode Simplex comprise le reste ne devrait poser aucun problème.