Discussion :

[yoshï]

Bonjour,
Je souhaiterai soumettre vos méninges à un petit pb.

On a 20 files permettant de stocker des lots de marchandises. Toutes ces marchandises sont à destination d'un même lieu. Chaque file correspond à une livraison.
Toute les X minutes (X dépend du nombre de départ par heure) on a une file complète (15 lots) qui est envoyé sur une livraison. Il peut arriver qu'il y ait un problème avec le transporteur (ce qui va ralentir le nombre de départ par heure) et nous obliger à stocker simultanément davantage de livraison en attente.

En amont des files on a un trieur qui va envoyer le colis qui se présente sur le premier départ disponible. On a donc un stockage sur les livraisons selon les règles FIFO.

Dans le nouveau dispositif, nous voulons introduire la notion de colis prioritaires.

Nous savons en temps réel combien de colis prioritaires sont injectés dans le circuit (avant trieur) mais une fois dans le circuit nous procédons à des tests par échantillonage sur les colis (certains peuvent mettre du temps à arriver).
Il est donc impossible de savoir dans quel ordre les colis arrivent devant le trieur. Quand un colis prioritaire se présente il peut y avoir un certain nombre de ligne en attente déjà remplies.

Les objectifs que je me fixe sont:
-Quand un colis prioritaire se présente au niveau du trieur il doit être envoyé sur le prochain départ
-L'ordre FIFO des colis standard doit être conservé
-Essayer d'avoir toujours des départ de 15 lots (taux de chargement 100%)

J'ai écrit l'algorithme que voici:
Cet algorithme nécessite une ligne supplémentaire (dite "ligne d'optimisation")

- Durant la composition d'une livraison, on a un compteur qui indique le nombre de colis prioritaire dans le circuit (donc susceptible d'arriver)
- Pour chaque mission on créé un "airbag" qu'on va propager aux livraisons suivantes tant que les colis prioritaires ne sont pas arrivés:
Le calcul de la taille de l'airbag se fait comme suit : nbColis_Prio_Attendu + nbColis_optimisation - nbPLacesLibres (dans les airbags précédents).

- Si on arrive au nombre de lots max (15) - taille Airbag. On arrête d'envoyer des colis dans cette file.

- Quand un colis prioritaire se présente et qu'on est déjà en présence de ligne avec airbag on l'envoi sur la première place libre dans les airbags
(le compteur nbColis_Prio_Attendu est décrémenté). S'il n'y a pas d'airbag cela veut dire que la livraison courante est la prochaine à partir (il n'y a pas d'autres livraisons stockées dans les réservoirs) On décrémente le compteur nbColis_Prio_Attendu et on envoie le colis prio dans la ligne courante.

- A chaque fois qu'on constitue un airbag dans une file,on envoie les colis standard qui suivent en ligne d'optimisation (un colis standard en ligne d'optimisation pour un colis prioritaire attendu)
- Si arrivé à l'heure H pour un départ on est toujours en attente de colis prioritaire , on libère la file et on compléte le chargement avec des colis en voie d'optimisation (pour avoir un taux de chargement à 100%). En effet, une fois arrivé à l'heure H, la livraison doit partir avec ou sans les colis prioritaires. Il faut juste propager l'airbag pour se donner la capacité d'accueillir les colis prioritaires sur la mission suivante.

Quand il n'y a plus de colis prioritaire attendu on arrête d'envoyer des colis en voie d'optimisation. Ainsi on "tue" l'airbag et tout redevient normal.


Pour résumé avec cette méthode:
-les colis stockés en voie d'optimisation peuvent être décalé d'une mission maximum si des colis prio prennent leurs places
-Une fois devant le trieur, les colis prios prennent le prochain départ
-le taux de chargement est toujours de 100%

Mais le problème c'est qu'il me faut segmenter la ligne d'optimisation pour compléter les chargements. Or dans le système on ne peut pas couper une ligne.
A partir du moment où on ouvre une ligne on libère tous les colis présents.

Avez vous d'autres idées pour résoudre ce problème? on est libre d'imaginer d'autres formes pour les réservoirs
Je ne sais pas si je suis très clair dans mes explications. N'hésitez pas à poser des questions

[souviron34]

Bonjour,
Je souhaiterai soumettre vos méninges à un petit pb.
..
Avez vous d'autres idées pour résoudre ce problème? on est libre d'imaginer d'autres formes pour les réservoirs
Je ne sais pas si je suis très clair dans mes explications. N'hésitez pas à poser des questions

Et pourquoi ne pas faire avec les 20 files déjà présentes seulement ?

N colis prio dans le circuit = m files prio (m-1 pleines + 1 partiellement)

Nb files normales = 20 - m

m-1 files prio pleines

1 moitié-moitié sur laquelle on ajuste

?

[Franck Dernoncourt]

Et pourquoi ne pas faire avec les 20 filles déjà présentes seulement ?

En tombant par hasard sur cette phrase, souviron34 a failli me donner la motivation pour lire toute la conversation, mais j'ai rapidement dû me rendre à l'évidence qu'il ne s'agissait que d'une typo

[souviron34]

oopsss

[yoshï]

Et pourquoi ne pas faire avec les 20 files déjà présentes seulement ?

N colis prio dans le circuit = m files prio (m-1 pleines + 1 partiellement)

Nb files normales = 20 - m

m-1 files prio pleines

1 moitié-moitié sur laquelle on ajuste

?

Hello
Je pense que je me suis mal expliqué...
On ne peut pas changer la priorité des files. Les files partent dans l'ordre (File1 puis File2 puis File3.....) C'est pourquoi il faut propager un airbag qui va permettre au colis prio de s'insérer dans la prochaine livraison. Si on arrive à l'heure H (départ de la livraison) et qu'on a toujours pas les colis prio, on fait partir la mission qu'on complète avec le bon nombre de colis stockés en voie d'optimisation. L'airbag est propagé sur les missions jusqu'à ce que les colis prio arrivent.

Est ce que c'est un peu plus clair?

[souviron34]

On ne peut pas changer la priorité des files. Les files partent dans l'ordre (File1 puis File2 puis File3.....)

Ce n'est pas contradictoire avec ce que je disais...

Admettons que nb colis prio = 1.25 files

nb files total = 20

nb files normales pleines = 18 (File1 -> File18)

file 19 : 75% pleine normale + 25% airbag
file 20 : attente

au fur et à mesure que colis prio arrivent : file 19 se remplit. Si pleine, on rempli file20 jusqu'au délai.

Comme ça tu as toujours ton max de files normales pleines, et tous tes colis prios envoyés si ils arrivent tous à l'heure - avec le seul défaut étant d'avoir la dernière ligne prio éventuellement non remplie si certains n'arrivent pas à l'heure, et tu la complètes par les colis normaux en attente.

Et tu as toujours 20 files complètes.. et les colis prios arrivés à temps partis..

[yoshï]

ok je vais essayer de commencer le déroulement d'un scénario simple pour illustrer les méthodes car je n'arrive pas à comprendre ce que tu veux dire.

On commence toute les lignes sont vides. On imagine que la capacité d'une ligne est de 15 colis.

On sait que dans le circuit on est en attente de 3 colis prioritaires
1) Des colis standard (ST) arrivent les uns à la suite des autres, on les stocke sur la file mission 1.

2) On arrête de stocker dès qu'on a un nombre de colis = Capacité file - tailleAirbag.
Avec taille airbag qui est calculée comme suit:
nb de colis prio attendus + nb de colis en voie d'optimisation - nb des places dispo dans les airbags précédents
Donc dans notre cas on a une taille d'airbag = 3+0-0 = 3.
On arrête donc de remplir la mission 1 dès qu'on atteint 15 - 3 = 12 et on envoie en ligne d'optimisation un nombre X de colis ST (avec X = nb de colis prio attendu).

Au moment d'attaquer la mission 2 si aucun colis prio ne s'est présenté on a donc 12 colis ST en mission 1 et 3 colis ST en ligne d'optimisation (qui auraient du être affecté à la mission 1 mais qui ont permis de créer l'airbag).


3) On commence à compléter la mission 2
Tant qu' aucun colis prio ne se présente la taille de l'airbag en mission2 = 3 +3 - 3= 3.

-Si il y a libération de la mission 1 quand on est encore en train de remplir la mission 2 et qu'aucun colis prio ne s'est présenté, on libère la ligne mission 1 et on complète le chargement avec les 3 colis en ligne d'optimisation.
l'airbag en mission 2 est recalculée:
3+0-0 = 3

- Si la mission 1 n'est toujours pas libéré et qu'un colis prio se présente alors qu'on est en train de composer la mission2, le colis prio vient prendre une place de l'airbag en mission 1 et la taille de l'airbag en mission 2 est recalculée:
2+3-2 = 3
(quand on libère la mission 1 on complète avec seulement 2 colis de la ligne d'optimisation car il restait juste 2 places dans l'airbag)

Etc .....
On continue jusqu'à ce que le nb de colis prio attendu soit nul. Quand c'est la cas on arrête d'envoyer en ligne d'optimisation et on envoie directement sur la mission suivante (pour "tuer l'airbag").

Je vais en faire du pseudo code pour que ce soit plus simple à lire.
Concernant ta solution, j'ai un peu de mal à comprendre ce que tu proposes. Peux tu dérouler sur un exemple simple et court genre pour les 2 premières lignes?

En tout cas merci pour ton aide... Il faut en avoir du courage pour me lire

[souviron34]

ok je vais essayer de commencer le déroulement d'un scénario simple pour illustrer les méthodes car je n'arrive pas à comprendre ce que tu veux dire.

Je crois que c'est parce que tu es "coincé" dans ton mode de pensée sur les "airbags"..

On commence toute les lignes sont vides. On imagine que la capacité d'une ligne est de 15 colis.

On sait que dans le circuit on est en attente de 3 colis prioritaires
1) Des colis standard (ST) arrivent les uns à la suite des autres, on les stocke sur la file mission 1.

OK

2) On arrête de stocker dès qu'on a un nombre de colis = Capacité file - tailleAirbag.

Pas dans mon algo.. Dans mon algo "taille airbag" = 0, ou alors "taille airbag = nb colis prio" affecté à la fin (voir plus bas)

Simplement connaissant le nombre de colis prios dans le circuit (pas encore arrivés) Nprios, on sait que ça fait x lignes de 15 (x nombre réel)

On a donc une "marge" libre de files normales m = 20 - (int(x) + 1)

Tant qu'on n'a pas rempli ces m lignes de colis normaux, on est tranquille, on a forcément la place de stocker TOUS les colis prios.

Quand la m-ième ligne est remplie, on commence à remplir la m+1 avec les colis prios arrivés. Tant qu'il en arrive avant le délai, on complète, et on passe à la suivante. Quand on sait qu'il n'en arrivera plus on termine avec des colis normaux.

Là, j'ai exposé cette approche en mettant les x lignes désignées au bout (à la fin des 20).

En fait on peut le faire au fur et à mesure..

On rempli ligne1. On sait qu'il y a X colis prios. On commence à remplir ligne2. 3 colis prios arrivent. On les met dans ligne2. On continue normalement avec ligne 2. Reste X-3 colis prios. etc... Par contre, dès qu'on arrive à 20-(X-déjà arrivés), on attend (peut-être en estimant le nombre censés arriver avant le délai) sans remplir (ou alors en remplissant sur la base de l'estimation) de colis normaux.

On peut alors, si on dispose d'une estimation du nombre censé arriver dans un certain délai (admettons 10 minutes avant le départ de la livraison), remplir de colis normaux jusqu'à ce nombre .. Sinon on prévoit plus large, et on prend en compte tous les colis prios pas encore arrivés.

Mais de toutes façons de cette manière on limite la casse : tous les camions partent pleins, sauf à partir du numéro y, où les suivants sont vides mais le y est partiellement vide. Comme je disais, si on dispose d'une limite de temps, on rempli de colis normaux à partir de ce temps jusqu'au dernier, en lui laissant une marge "expérimentale" ..

De toutes façons tu auras à prendre en compte au dernier moment / dans un certain délai la différence entre le nombre prévu et le nombre réellement arrivé pour optimiser le remplissage. Autant que ça soit réparti sur uniquement le plus petit nombre de camions concernés : plutôt que d'avoir à compléter 20 camions, ce serait peut-être 2, quitte à ce que le dernier soit à remplir quasi-entièrement.

A mon avis (mais je ne suis pas dans ta boîte) il est plus rentable de faire partir n (n < 20) camions pleins que 20 camions pas pleins..


Ton problème est une variante du problème de "remplissage successif de bac de sable", et il y a eu un post sur ce sujet l'an dernier, je crois..

[yoshï]

Je crois que c'est parce que tu es "coincé" dans ton mode de pensée sur les "airbags"..

Je pense surtout que le pb vient du fait que je n'ai pas exprimer correctement les hypothèses de départ....

15 colis par camions est une limite, on ne peut donc pas réduire ta variable "n". Un camion peut partir avec moins de 15 colis mais pas avec plus (nos colis sont un peu spéciaux ). Ceci implique qu'il va falloir 1 départ camion par ligne de colis. A l'origine une ligne représentait un chargement camion mais avec mon système il faut compléter avec la ligne d'optimisation (du moins quand on attend des colis prioritaires, le reste du temps on fonctionne normalement)

Le nombre de colis prioritaires ne représente que 3% du nombre de colis total. Il va donc être compliqué et surtout très long de faire des lignes complètes de colis prioritaires (imagine si il y a plus d'une heure entre 2 colis prioritaires). Je pense donc que la solution optimale consiste à compléter des lignes de colis standard avec les prioritaires dès qu'ils arrivent.

Je rappelle également les objectifs de départ:
- Quand un colis prioritaire arrive il doit prendre le prochain camion qui part (c'est pourquoi je lui réservais une place avec les airbags )
-le taux de remplissage des camions doit être maximum (15 colis par camion)
-Il faut préserver autant que possible le FIFO des produits standards (si un colis prio a pris sa place le colis standard partira avec la prochaine mission).
C'est pourquoi je tiens compte dans mon calcul de l'airbag des colis en voie d'optimisation.

[souviron34]

Je pense surtout que le pb vient du fait que je n'ai pas exprimer correctement les hypothèses de départ....

15 colis par camions est une limite, on ne peut donc pas réduire ta variable "n". Un camion peut partir avec moins de 15 colis mais pas avec plus (nos colis sont un peu spéciaux ). Ceci implique qu'il va falloir 1 départ camion par ligne de colis.

C'est bien ce que j'avais compris.

Le nombre de colis prioritaires ne représente que 3% du nombre de colis total. Il va donc être compliqué et surtout très long de faire des lignes complètes de colis prioritaires (imagine si il y a plus d'une heure entre 2 colis prioritaires).

Tu ne m'a pas compris : je comptais en "nombre de ligne", mais je ne pensais pas à faire des lignes complètes de colis prio, simplement à compter combien ça bouffe sur les 20 lignes dispos.

Ma limite était pour tenir compte de ta remarque du premier post :

mais une fois dans le circuit nous procédons à des tests par échantillonage sur les colis (certains peuvent mettre du temps à arriver).
Il est donc impossible de savoir dans quel ordre les colis arrivent devant le trieur. Quand un colis prioritaire se présente il peut y avoir un certain nombre de ligne en attente déjà remplies.

Le nombre max peut être représenté en nombre de files, c'est tout.

Je pense donc que la solution optimale consiste à compléter des lignes de colis standard avec les prioritaires dès qu'ils arrivent.

Nous sommes bien d'accord, mais je ne vois pas ton concept d'airbag.. Tant que tu n'as pas ateint la m-ième file..

Si un colis prio arrive, on le met dans le premier camion qui va partir, et c'est une ligne LIFO pour les colis normaux si on est à 15 colis.

Puis ça se propage..

Je ne vois pas pourquoi fair intervenir un "airbag" systématiquement : chaque fois que X colis prio arrivent dans un camion presque plein, on enlève les X' derniers colis normaux (tant qu'il y en a) et on les bascule dans le camion suivant.

L'airbag pour moi n'intervient qu'en sécurité si on arrive à un petit nombre de camions restants (20-m), et que le nombre de colis potentiellement arrivant comence à être majoritaire.

Je rappelle également les objectifs de départ:
- Quand un colis prioritaire arrive il doit prendre le prochain camion qui part (c'est pourquoi je lui réservais une place avec les airbags )
-le taux de remplissage des camions doit être maximum (15 colis par camion)
-Il faut préserver autant que possible le FIFO des produits standards (si un colis prio a pris sa place le colis standard partira avec la prochaine mission).

Mion approche en tient compte, et soit je ne comprend pas ta notion de "voie d'optimisation", soit il y a quelque chose que je ne comprend pas..

Prenons un petit graphique :

Cas 1 :

Camion en train de se remplir : N

Normal : xxxxxxxxxxxxx 13 colis

1 colis prio arrive : xxxxxxxxxxX 14 colis dont 1 prio

1 colis normal arrive : xxxxxxxxxxxxxXx 15 colis dont 1 prio -> Camion part


Cas 2 :

1 prio arrive : X 1 colis prio dans le camion N+1

12 colis normaux arrivent : Xxxxxxxxxxxxx : 13 colis dont 1 prio

3 colis prios arrivent : il y a (théoriquement) de la place pour 2. Mais si on pousse le dernier colis normal dans le camion suivant, on rentre :

XxxxxxxxxxxxXXX et le camion N+1 part

le camion N+2 ayant 1 colis x


Il faut donc simplement garder les "segments" de colis normaux (nb et indice de fin de chaque bloc) pour faire une LIFO correcte. Par défaut on doit pouvoir faire un camion entier de prios si il en arrive 15 avant le délai.


Si je reprend mon dernier exemple, en ajoutant un trou :

soit un camion de 13 colis, tel que : xxxXXxxxxxXxx

On a 3 sectons de colis normaux : 1-3 6-10 12-13

il reste 2 places. Si 5 colis prio arrivent, on bascule 12-13 dans le camion +1, et on bascule aussi 10. On a libéré 3 places.

Il suffit de maintenir une structure (place min - place max) pour décrire les sections.


Si on ne veut pas gérer des sections, il suffit de pousser le(s) colis prio arrivant en file FILO jusqu'à ce qu'ils soient en butée soit sur la posiition 1 soit sur le dernier prio si il y en a déjà.

[souviron34]

Tiens..

Opportunément le posteur ayant démarré le thread dont je parlais plus haut a posté ce matin et m'a ré-actualisé ce fil, je l'ai donc retrouvé

Création d'un programme en C

(avec un titre pareil !!!!)

Et tu as une référence en 2D (qui te pointeras sans doute vers des références 1D) dans le post #7

Mais normalement le pseudo-algo que j'ai décrit plus haut devrait marcher..

PS: le terme donc à rechercher serait "avalanche" (ou peut-être "cascade")

[pseudocode]

3 colis prios arrivent : il y a (théoriquement) de la place pour 2. Mais si on pousse le dernier colis normal dans le camion suivant, on rentre :

XxxxxxxxxxxxXXX et le camion N+1 part

le camion N+2 ayant 1 colis x

Je pense qu'il ne peut pas changer un colis de ligne. Sinon le problème serait assez trivial.


Si j'ai bien compris le problème:

                      +-> Ligne 3 : _______________  -+
                      |                               |
d,X,c,b,a ->[trieur] -+-> Ligne 2 : _______________   +--> Camion
                      |                               |
 (colis)              +-> Ligne 1 : __xxxXXxxxxxXxx  -+

- Comment faire pour au final avoir "X, a" dans la ligne 1, et "b, c, d" dans la ligne 2, alors que le trieur ne connait pas à l'avance l'ordre/nombre les colis qui vont arriver. Tout ce qu'il sait c'est qu'au total il y a N colis prioritaires (notés "X").

[yoshï]

Désolé pour le retard et merci de vos réponses.

@Souviron, je réalise enfin d'où vient la confusion. Je n'avais peut être pas suffisamment inssisté sur le fait que je suis contraint par les installations physiques dans les entrepôts. Ainsi les lignes de stockage ne permettent pas de faire du LIFO. il est donc pour l'instant impossible de réaliser l'opération suivante:

3 colis prios arrivent : il y a (théoriquement) de la place pour 2. Mais si on pousse le dernier colis normal dans le camion suivant, on rentre :

Si j'ai bien compris le problème:
- Comment faire pour au final avoir "X, a" dans la ligne 1, et "b, c, d" dans la ligne 2, alors que le trieur ne connait pas à l'avance l'ordre/nombre les colis qui vont arriver. Tout ce qu'il sait c'est qu'au total il y a N colis prioritaires (notés "X").

@Pseucode, C'est exactement le pb.

Dans ma solution on stockera "a" sur la mission 1 puis "b" dans une ligne temporaire (dite d'optimisation). ON a donc créé un airbag pour "X".
Après il y a 2 solutions

-----------------------------------------------
-->Soit "X" arrive avant le départ de la mission 1

Mission1
on libere ligne mission 1 XaxxxXXxxxxxXxx (15 colis)

Mission2
on libere optimisation : b (1 colis)
& on libere ligne mission2 : ????????????dc (14colis)

-->Soit la mission 1 part avant l'arrivée de X

Mission1

on libere optimisation : b (1 colis)
& on libere ligne mission1 axxxXXxxxxxXxx (14 colis)

et si X n'est toujours pas arrivé quand on atteint l'avant dernière place de la mission 2, on recréé un airbag en envoyant un colis en ligne d'optimisation, etc....
-----------------------------------------------


Aujourd'hui les lignes ne comptent pas le nombre de colis libérés => Quand une ligne s'ouvre tous les colis stockés sont libérés.
Mon algo implique qu'on puisse segmenter la ligne d'optimisation pour venir compléter les missions quand besoin est avec le bon nombre de colis standard.
Il va donc falloir installer des détecteurs (boucle de comptage) sur la ligne d'optimisation pour pouvoir gérer des libérations partielles.

Le LIFO serait par contre beaucoup plus compliqué à gérer physiquement sur nos lignes.
Si vous avez des suggestions ou des idées d'amélioration je serai content d'en discuter.

Merci encore

[pseudocode]

Je ne vois pas de solution qui puisse à la fois gérer toutes les contraintes:
- taux de remplissage 100%
- ordre FIFO sur les colis non urgent
- pas de connaissance a priori de l'ordre des colis
- files temporaires insécables
- ...

Ta solution actuelle est sans doute la meilleure si on souhaite garantir totalement les 3 premières contraintes.

Pour ma part, quitte à mettre des détecteurs, je les mettrais avant la trieuse afin de savoir si un colis urgent va être traité. C'est a mon sens la contrainte la plus forte que tu as, et ca serait bien de pouvoir s'en libérer.

[yoshï]

Pour ma part, quitte à mettre des détecteurs, je les mettrais avant la trieuse afin de savoir si un colis urgent va être traité. C'est a mon sens la contrainte la plus forte que tu as, et ca serait bien de pouvoir s'en libérer.

Tout à fait d'accord avec ça, je réfléchis également à des solutions, certes plus onéreuses, mais qui permettraient d'avoir un suivi plus précis des colis avant trieuse.
Le problème c'est que sur tout la parcours, y compris juste avant la trieuse, on a des machines qui effectuent des contrôles par échantillonage de manière aléatoire en sortant des colis de la ligne principale (Il est donc impossible de connaître l'ordre exacte d'arrivée). Les colis une fois controlés (certains contrôles peuvent prendre plusieurs dizaines minutes) sont remis sur la ligne principale.

[pseudocode]

Tout à fait d'accord avec ça, je réfléchis également à des solutions, certes plus onéreuses, mais qui permettraient d'avoir un suivi plus précis des colis avant trieuse.
Le problème c'est que sur tout la parcours, y compris juste avant la trieuse, on a des machines qui effectuent des contrôles par échantillonage de manière aléatoire en sortant des colis de la ligne principale (Il est donc impossible de connaître l'ordre exacte d'arrivée). Les colis une fois controlés (certains contrôles peuvent prendre plusieurs dizaines minutes) sont remis sur la ligne principale.

Dans ce cas, on ne peut pas trop travailler en amont de la trieuse, sauf a perdre la notion de FIFO ou accepter des ratés dans la détection des colis urgents.

Ta solution reste sans doute la meilleure avec toutes les contraintes que tu as. Si on peut relacher d'autres contraintes, on peut en simplifier le fonctionnement. Mais sinon, je ne pense pas qu'on puisse avoir mieux.