question algo

[mon_yayou]

bonjour à tous,

je vous explique mon problème:
je voudrais creer un fichier permettant d'équilibrer des postes de travail avec différentes opérations.
par exemple: pour fabriquer un produit A il faut faire 10 opérations : OP1, OP2,...,OP10.
sachant que:
- chaque opération à un temps associé T1 pour OP1, T2 pour l'OP2,... T10 pour l'OP10.
- les opérations peuvent ne pas être faite dans l'ordre: OP1 puis OP2 etc...
mais qu'il y a tout de même des contraintes exemple pour réaliser OP10 il faut avoir réalisé OP4.

mon but est de regrouper ces opérations en X groupes (postes) (par exemple 4) de manière à ce que chaque groupe pèse le même poids en temps.

exemple:
poste 1 réalise: OP1,OP5,OP7
poste 2 réalise: OP4,OP2,OP3
poste 3 réalise: OP6,OP8,OP9
poste 4 réalise: OP10

donc ici on aurait: T1+T5+T7 environ = à T4+T2+T3 environ = à T6+T8+T9 environ = à T10

pourriez vous me renseigner sur les différents algorithmes qui permettent de réaliser ce type d'opération. Je voudrais des pistes pour commencer ma reflexion: comment faire pour mettre des priorités sur certaines OP mais ne pas bloquer le systéme?
comment classer?, comment regrouper? quels algorithmes serait utiles dans mon cas?
avez vous deja traité ce genre de pb?
par avance merci pour votre aide

 

[Robert]

Re : question algo

Bonjour mon_yayou, bonjour le forum,

Il y a bien longtemps j'avais créé pour une copine une application permettant de répartitir équitablement des valeurs : Lien supprimé. Je sais que le codes manquent de rigueur car j'avais moins de connaissance qu'aujourd'hui à l'époque mais peut-être elle te permettrait de gerer ton problème.
Cette appli devait gerer des chèques donc certaines parties n'auront pas d'intérêt dans ton cas...
Mais si tu veux l'utiliser :
Clique sur Données, Tape le mois et l'année (même si tu n'en as pas besoin) et valide. Ensuite rentre le nombre de participants (pour toi c'est le nombre de groupes). Une boîte de dialogue s'ouvre et tu inscris le nom de chaque groupe (oublie Accompte et Restant précédent) et tu valides.
Dans la boîte de dialogue suivante inscrit de temps dans le champ Valeur et le nom de l'opération dans le champ Nom, valide tes dix valeurs. Puis clique sur Terminer.
Un tableau récapitulatif te présente les données.
Clique sur le bouton Envoyer... Un deuxième onglet et préparé avec la répartition exacte des groupes.
Clique sur Calculer. La répartition se fait au plus près...
Tu peux ensuite avoir des tableaux séparés en cliquant sur Ranger...

 

[CBernardT]

Re : question algo

Bonjour mon yayou, Robert et le forum,

Projet intéressant que d'ordonnancer les opérations de production d'un produit P sur X postes de travail connaissant le nombre d'opérations et leur temps moyen de réalisation.

L’algorithme d’équilibrage des opérations à effectuer par les postes de travail pourrait avoir cette logique :

1- Calcul du temps total des opérations égal à la somme des temps de toutes les opérations à effectuer :

TpTotOps = T1 + T2 + T3……

2- Recherche du temps moyen par opération égal au temps total des opérations divisé par le nombre d’opérations :

TpMoyOp = TpTotOps / NbOps

3- Calcul du temps moyen par poste égal au temps total des opérations divisé par le nombre de postes affectés à la production du produit P :

TpMoyPoste = TpTotOps / NbPostes

4- Recherche du nombre moyen d’opération par postes égal au temps moyen des postes divisé par le temps moyen par opération :

NbMoyOpsPoste = TpMoyPoste / TpMoyOp

5- Recherche des solutions combinant un nombre d’opérations dont la somme des temps est égale ou plus ou moins égal au temps moyen par poste :

OpsPoste = [NbMoyOpsPoste(T1, T2, T3,…) = ~ TpMoyPoste]

Comme il n’est pas sûr d’avoir une somme de NbMoyOpsPoste temps d’opérations égale au temps moyen par poste, la recherche de la solution s’effectuera en utilisant un intervalle de recherche autour du Temps moyen par poste.
Un pourcentage T(m) croissant en boucle selon un taux fixé permet d’élargir progressivement l’intervalle de recherche jusqu’à obtention d’une solution. De même, le nombre d’opérations par poste est évolutif en fonction du nombre des opérations restante(s).

Intervalle = [TpMoyPoste*(1-T(m)), TpMoyPoste*(1+T(m))]

6- Une solution S(n) trouvée et sauvegardée, les opérations composant cette solution sont retirées de la liste des opérations. Si la liste restante n’est pas vide, reprise au point 5 afin de rechercher la solution S(n+1) avec la liste des opérations restantes.

Nota : le temps moyen d’une opération est à définir en nombres entiers ou décimaux. Exemple, un temps moyen d’opération de 4 minutes et 15 secondes sera validé soit par 255 (Secondes) soit 4,25 (Minutes).

Un essai d'application dans le fichier joint.

 

[mon_yayou]

Re : question algo

Bonjour à tous,

je suis en train d'étudier vos différentes réponse, mais je tiens avant tout à vous remercier pour la qualité de vos réponses. La logique ainsi que les ficiers que vous m'avez transmis sont autant de bases qui vont m'aider à avancer.

merci

 

[mon_yayou]

Re : question algo

merci pour vos exemples d'implementation
mais mon gros probleme vient surtout de l'introduction de la notion de precedence.
Je ne sais pas comment cela: comment parametrer cette notion, comment la gerrer,...
connaissez vous des outils type outils de recherche operationnel (pert, gantt, ... ) permettant de gerrer cette notion d'anteriorité?

et auriez vous une idee pour l'implementer?