Calendrier : déterminer le prochain créneau horaire disponible

Version imprimable

30/08/2017, 14h35
nietsabes

Calendrier : déterminer le prochain créneau horaire disponible

Bonjour à tous,

je travaille sur un algorithme d'optimisation de production et je rencontre une difficulté pour déterminer la prochaine plage d'ouverture disponible dans un calendrier.

Pour faire simple mon algorithme détermine dans quel ordre lancer les différentes production de telle façon à ce que cela se fasse dans un minimum de temps (algorithme génétique).

La contrainte principale à optimiser dans mon cas est la disponibilité de "régleurs" qui permettent de passer d'une production à l'autre. Les machines sont automatiques et peuvent travailler la nuit et les weekend mais ont besoin de quelqu'un pour régler la machine et passer à la machine suivante.

Je cherche le meilleur moyen de gérer le planning de disponibilité des régleurs. J'ai d'une part une table avec toutes les dates ouvrées possibles pour chaque régleur. J'ai par ailleurs une seconde table qui indique les plages pendant lesquelles les régleurs sont déjà occupés (ce qui fait des plages d'exclusion).

Bref, je pense que c'est un problème de gestion de calendrier mais je dois dire que je désespère un peu pour trouver la bonne architecture de données pour le faire de façon efficiente.

Si je résume mon problème: je cherche une façon de gérer un agenda qui, lorsqu'on l'interroge sur une date, indique la prochaine plage horaire disponible.

Un grand merci,

Sébastien
30/08/2017, 18h15
Sve@r

Bonjour

Ton problème ressemble assez aux problèmes d'optimisation des graphes (voyageur de commerce, etc) et dépend donc plus de la théorie des graphes que d'un souci spécifique Python.

Par ailleurs il manque certains détails. Par exemple pour une production, utilises-tu qu'un seul régleur ou plusieurs ? Et si plusieurs, y a-t-il un ordre spécifique ou bien tu peux passer du régleur X au régleur Y sans que cela ne gêne ???

Question purement Python, moi j'utiliserais plutôt une classe "régleur" contenant ses dates ouvrées possibles et ses indisponibilités ; solution à mon sens plus parlante (ou plus évolutives) que gérer deux tables en parallèles...

Bonsoir Sve@r,

Citation:

Envoyé par Sve@r

Ton problème ressemble assez aux problèmes d'optimisation des graphes (voyageur de commerce, etc) et dépend donc plus de la théorie des graphes que d'un souci spécifique Python.

Tout à fait d'accord avec toi la solution que j'ai élaboré relève des problèmes du voyageur de commerce, dans sa variante avec plusieurs voyageurs mTSP

Citation:

Envoyé par Sve@r

Par ailleurs il manque certains détails. Par exemple pour une production, utilises-tu qu'un seul régleur ou plusieurs ? Et si plusieurs, y a-t-il un ordre spécifique ou bien tu peux passer du régleur X au régleur Y sans que cela ne gêne ???

J'ai effectivement plusieurs régleurs qui ont chacun une qualification spécifique pour chaque équipement. Par exemple avec 4 machines je peux avoir:

Albert : qualification machines 1, 2 et 3
Michel : qualification machines 2, 4

Donc je peux me retrouver avec des machines qui peuvent être réglées par plusieurs régleurs. Dans ce cas je prends le premier disponible (même si à l'avenir je peux chercher à équilibrer les réglages entre eux

Citation:

Envoyé par Sve@r

Question purement Python, moi j'utiliserais plutôt une classe "régleur" contenant ses dates ouvrées possibles et ses indisponibilités ; solution à mon sens plus parlante (ou plus évolutives) que gérer deux tables en parallèles...

Et bien là c'est précisément où je bloque. D'une part le principe de classe m'échappe (:calim2: shame on me mais je me suis mis à la programmation Python il y a 6 mois). D'autre part je cale sur la structuration à donner à mes infos pour que ce soit efficace.

Lorsque je calcule le temps de production d'une séquence de produits P1, P2, P3 (sur une unique machine pour faire simple) je dois à chaque fois déterminer si la début de production tombe bien sur un jour (et une heure) où l'opérateur est disponible. C'est sur cette fonction que mon algo coince le plus.
Soit une fonction "operateur_dispo":
Code:

1 2 operateur_dispo("2017/08/31 20:00") doit renvoyer --> "2017/09/01 07:00" (Albert travaille de 07:00 à 17:00) alors que operateur_dispo("2017/09/01 14:00") renvoie "2017/09/01 14:00" (Albert est immédiatement disponible)
Pour l'instant j'ai fait une vraie usine à gaz avec des tables (passées en numpy) pas très propres.

Sébastien

31/08/2017, 19h45
anapurna

salut

je comprend pas la difficulté

1°) tu récupère la liste des régleurs pouvant être la dans la plage horaire indiqué par la machine
dans le cas ou tu n'as rien c'est que ta machine ne s’arrête pas dans une bonne plage

2°) dans la liste des régleur obtenu tu supprime tout les régleur qui sont occupé à ce moment la
il te reste juste les régleur dispo
dans l'autre cas c'est que tu n'a aucun régleur dispo a ce moment la
31/08/2017, 21h07
valentin03

Machine et réglage

Il manque la durée maximale de fonctionnement machine entre deux réglages.
04/09/2017, 10h43
nietsabes
Citation:

Envoyé par anapurna

salut

je comprend pas la difficulté

1°) tu récupère la liste des régleurs pouvant être la dans la plage horaire indiqué par la machine
dans le cas ou tu n'as rien c'est que ta machine ne s’arrête pas dans une bonne plage

2°) dans la liste des régleur obtenu tu supprime tout les régleur qui sont occupé à ce moment la
il te reste juste les régleur dispo
dans l'autre cas c'est que tu n'a aucun régleur dispo a ce moment la

Bonjour,

en fait c'est le point 1 qui me pose des difficultés. Admettons qu'une machine s'arrête de fonctionner en plein weekend et que le prochain régleur dispo reprenne sont travail le lundi à 07:00 il faut que je puisse retrouver cette info.

Je vois plus ou moins comment le faire en SQL mais le problème étant que j'ai un nombre important de plages à calculer à chaque itération de mon algorithme, cela devient très vite très lent de faire des requêtes.

Admettons que je veuille comparer 100 scenarii entre eux (un scenario étant un ordre de production précis par exemple A B C vs B C A) :
- A chaque produit je vais chercher l'heure de dispo. Soit 20 x (pour 20 produits)
- multiplié par 100 scenarii j'ai donc 20 x 100 requêtes soit 2000
De plus je peux avoir des situations où j'identifie une plage de dispo à 16:00 un lundi par exemple. L'opérateur va commencer son travail mais va s'arrêter à 17:00 pour reprendre sa tâche à sa prochaine plage de dispo (le mardi à 07:00). Je dois donc refaire un calcul.

Ce qui constitue une difficulté significative c'est le volume des requêtes engendrées. Par construction mon algorithme d'optimisation effectue un nombre considérable d'itérations (exploration des solutions possibles) pour trouver (et construire) la meilleure solution possible et donc peut être pénalisé par des opérations à première vue élémentaires mais répétées un grand nombre de fois.

Enfin pour répondre à Valentin, la durée d'une production est variable par produit. Elle peut aller de 200 minutes à 20 000. La durée moyenne d'un réglage est de 240 minutes.

Merci !
04/09/2017, 11h14
tbc92
Citation:
Envoyé par nietsabes

Admettons que je veuille comparer 100 scenarii entre eux (un scenario étant un ordre de production précis par exemple A B C vs B C A) :

A chaque produit je vais chercher l'heure de dispo. Soit 20 x (pour 20 produits)
multiplié par 100 scenarii j'ai donc 20 x 100 requêtes soit 2000
Si tu utilises des requêtes, le maillon faible des requêtes, c'est effectivement quand tu lances énormément de requêtes.

Mais tu peux organiser tes données pour obtenir tes 2000 résultats via une seule requête ; une requête qui renvoie 2000 informations, c'est quasiment 2000 fois plus rapides que 2000 requêtes qui renvoient chacune une information.

Tu peux créer une table "Contenu_scénario" où tu aurais en gros les colonnes :
- Identifiant_Scenario
- Identifiant tâche ( A,B ou C dans ton exemple)
- Identifiant_ouvrier
- date/heure_debut
- date/heure_fin
04/09/2017, 12h15
nietsabes
Citation:

Envoyé par tbc92

Si tu utilises des requêtes, le maillon faible des requêtes, c'est effectivement quand tu lances énormément de requêtes.

Mais tu peux organiser tes données pour obtenir tes 2000 résultats via une seule requête ; une requête qui renvoie 2000 informations, c'est quasiment 2000 fois plus rapides que 2000 requêtes qui renvoient chacune une information.

Tu peux créer une table "Contenu_scénario" où tu aurais en gros les colonnes :
- Identifiant_Scenario
- Identifiant tâche ( A,B ou C dans ton exemple)
- Identifiant_ouvrier
- date/heure_debut
- date/heure_fin

Cela m'intéresse hautement mais est-ce possible de calculer un scenario d'un coup?

Sur la base d'un opérateur travaillant de 07:00 à 17:00 du lundi au vendredi inclus, admettons que j'ai les produits A B C D à produire :
- Produit A : tps de prod 2000 minutes, 240 minutes de tps de réglages
- Produit B : tps de prod 4000 minutes, 240 minutes de tps de réglages
- Produit C: tps de prod 6000 minutes, 240 minutes de tps de réglages
- Produit D: tps de prod 6000 minutes, 240 minutes de tps de réglages
Donc avec un début de prod général le 4 septembre à 12:00 je vais avoir :
1. Produit A : Dispo machine : 4/9/2017 à 12:00 - Début réglages A : 4/9/2017 à 12:00 - Début prod prod A : 4/9/2017 à 16:00 - Fin de prod A 5/9/2017 à 01:20
2. Produit B : Dispo machine : 5/9/2017 à 01:20 - Début réglages B : 5/9/2017 à 07:00 - Début prod prod B : 5/9/2017 à 11:00 - Fin de prod B 8/9/2017 à 05:40
3. Produit C : Dispo machine : 8/9/2017 à 05:40 - Début réglages C : 8/9/2017 à 07:00 - Début prod prod C : 8/9/2017 à 11:00 - Fin de prod C 12/9/2017 à 15:00
4. Produit D : Dispo machine : 12/9/2017 à 15:00 - Début réglages D : 12/9/2017 à 15:00 - Début prod prod C : ~~12/9/2017 à 19:00~~ 13/9/2017 à 10:00 (l'opérateur a du interrompre son réglage à 17:00 et les a repris le lendemain à 07:00) - Fin de prod C 17/9/2017 à 15:00
Je ne peux obtenir les dates de début de prod en une fois mais en cascade n'est-ce pas? D'où mes itérations très nombreuses pour calculer la performance d'un scenario.
04/09/2017, 14h56
anapurna

salut

tout cela deviens confus

Tout ceci me rappelle furieusement de l'optimisation de gestion de processus par la méthode Pert (Program Evaluation and Research Task)
pour ceci il faut connaitre les priorités des taches à effectuer pour pouvoir assigner un regleur par preference dans le cas ou deux machine doit etre regler en meme temps

si j'ai bien compris tu as des horaires "usine" qui ne varient jamais 07:00 à 17:00 du lundi au vendredi inclus
tu as pour chaque produit un temps de réglage est une durée optimal de fonctionnement
et tu as des régleur disponible uniquement dans la période horaire
il te manque l'occupation de Tes régleur à un moment T
a priori ton résultat est en minutes et pas en heures on sais que tu as 10 heures de boulots par jour soit 600 minutes
donc le calcul pour une journée est

Citation:

si HJourdebut+DelaisReg > HJourfin alors
ReportMinute = ((HDebutTask+DelaisReg)-HJourFin)
// ce qui signifie que le lendemain tu finis le réglage a HdebutJour+ReportMinute
// NewTask(Production)= JOURNPLUS1 + HdebutJour+ReportMinute
sinon
RestMinute = (HJourFin - (HDebutTask+DelaisReg))
// ce qui signifie que le jour même tu peut prévoir un réglage a HJourFin-RestMinute
// NewTask(Production)= JOURN + HJourFin-RestMinute

// HJourdebut = heure du début de journée soit 0 ou 7*60 ... tout dépend si tu veut faire un translation d’échelle ou pas
// DelaisReg = Délais de réglage machine en minutes
// HJourfin = Heure de fin de journée soit 600 ou 17*60 idem que HJourdebut
// HDebutTask = Heure du début de la tache x en minute depuis le début de la journée
// ReportMinute = nombre de minutes a reporter sur le jour d’après pour terminer le réglage
// RestMinute = nombre de minutes restant pour le prochain réglage
04/09/2017, 16h07
tbc92

Citation:

Envoyé par nietsabes

Cela m'intéresse hautement mais est-ce possible de calculer un scenario d'un coup?

A mon avis non, puisque dans un scénario, il va y avoir des temps morts (hormis bien sûr les heures non ouvrables.)
Mais si déjà tu peux traiter 100 scenarii en une passe, si chaque scenario contient 10 étapes, tu as 10 requêtes seulement à exécuter.
04/09/2017, 16h18
nietsabes

Mes excuses pour la confusion :?

J'ai deux types de ressources :
* des machines pouvant travailler 24/7.
* des régleurs présents du lundi au vendredi de 07:00 à 17:00

Une machine peut produire (et produit effectivement) 24h/24 et 7j/7 mais a besoin d'un régleur pour amorcer la production.

Mes charges :
J'ai une série de produits avec un temps de production requis (pas de notion durée optimale de fonctionnement) et un temps de réglage pour chacun d'eux. Par simplicité je n'ai pas introduit la notion de priorité pour chacun d'eux.

-------------

Ma première étape est d'évaluer pour chaque produit son heure de début de production et son heure de fin.

Dans mon exemple j'ai une machine et un régleur pour rester simple. Cela m'évite de devoir prendre en compte une table de dispo des régleurs dans un premier temps.

Le calcul de la performance d'un scenario est fait dans un second temps (temps employé, retard des commandes par rapport à la date demandée etc...)

Est-ce plus clair?

salut

il va donc falloir les dissocier en deux tache distinct la production et le reglage même si elle se suivent sans temps morts
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //////////////////////////////// TREGLAGE IDREGLAGE REGLEUR DTDEB DTFIN FIN //////////////////////////////// TPROD IDPROD DTDEB DTFIN FIN //////////////////////////////// TTOTALPROD IDPRODTOT IDMACHINE IDREGLAGE IDPROD FIN //Date Debut TREGLAGE.DTDEB //Date Fin TPROD.DTFIN
as tu vu les calcul que j'ai mentionné ?
Ceux-ci sont valable pour un régleur il te reste qu'a ajouter le temps de production et tu as la date de fin de production
en tenant compte des jour ouvrés bien évidement ce genre de calcul peut être effectué par le SGBD
ce sont des calculs simple

le plus dur étant de trouver le meilleur compromis possible

1°) Recherche des date de disponibilité des Machine

donc a l'instant T on fait un requête qui nous permet de définir la date de fin de la production
j'imagine un truc comme cela ... ne connaissant pas la structure de tes table
Code:

1 2 3 4 Select IDPROD,TYPROD,ANNE(DTFIN),SEMAINE(DTFIN),JOURSEMAINE(DTFIN),HEURE(DTFIN) from EN_PRODUCTION where DTFIN > Getdate()
ce qui devrais donner un truc du genre
Code:

1 2 3 4 2|'B'|2017|36|MARDI|15H00 1|'A'|2017|36|MARDI|18H45 // CELLE CI DOIT ETRE TRANSFORME PAR MERCREDI 7 HEURE 3|'C'|2017|36|MERCREDI|12H00
....
nous avons vu que tu voulez changer de jour et d'horaire si tu dépasse l’horaire de journée (17 heure)
voila comment je vois la requête pour avoir les bonne infos sur l'heure Final
Code:

1 2 3 4 5 6 7 Select IDPROD,TYPROD,ANNEE(DTFIN) ,CASE DTFIN WHEN >@DTFINJOUR BEGIN HEURE(@DTDEBJOUR) ELSE HEURE(DTFIN) END as HDTFIN ,CASE DTFIN WHEN >@DTFINJOUR BEGIN case JOURN+1 WHEN > 5 BEGIN 0 ELSE JOURN+1 END ELSE JOURN+0 END as JOURSEMAINE ,CASE DTFIN WHEN >@DTFINJOUR BEGIN case JOURN+1 WHEN > 5 BEGIN SEM+1 ELSE SEM+0 END ELSE JOURN+0 END as SEMAINE from EN_PRODUCTION where DTFIN > Getdate()
2°) Récupérer toutes les productions a faire
Mettre la date de Fin de la Prodution en Cours pour chaque nouveau TREGLAGE de chaque nouvelle enregistrement TTOTALPROD pour chaque machine sur la date de DTDEB

3°) Verifier que les regleur soit disponible a la date de DTDEB

une fois les infos correct mis en place je pense que il n'y a plus trop de problème pour trouver les différent scénario
il faudra surement faire un Update d'un champs date reconstitué a partir de ANNEE,HDTFIN,JOURSEMAINE,SEMAINE
tout depend aussi de la puissance de ton SGBD

05/09/2017, 11h21
nietsabes

Vraiment un grand merci, je vais regarder ça et l'intégrer à mon algo existant.

:ave:
13/09/2017, 15h55
Nebulix

Il serait intéressant de savoir à peu près combien il y a de machines, de régleurs, quel est le délai possible de fabrication, quelle est la distribution des durées de fabrication.