Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Regroupement de commandes en palettes complètes


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Regroupement de commandes en palettes complètes
    Bonjour,

    On doit préparer plusieurs commandes Cx de produits P avec des quantités différentes :
    - Commande C1 qté 2
    - Commande C2 qté 1
    - Commande C3 qté 3
    - Commande C4 qté 1
    - ...
    - etc pour plusieurs dizaines de commandes.

    Je dois regrouper ces commandes afin de déstocker, dans la mesure du possible, des palettes complètes de 50 produits (50 étant variable suivant le produit à traiter).
    Un regroupement ne doit pas dépasser 50 produits.
    Comment optimiser les regroupements de commandes afin d'avoir un maximum de palettes complètes de 50 produits ?
    Et non pas des palettes "presque complètes" de 49, 48, 47 produits.

    Je précise que je travaille actuellement en PL/SQL (Oracle) mais peu importe il s'agit d'algorithmique.

    Cordialement.

  2. #2
    Expert éminent sénior
    Bonjour

    C'est typiquement le "problème du sac-à-dos", pour lequel il n'existe aucune solution mathématiquement parfaite, actuellement. Tu vas être obligé de faire tous les cas possibles jusqu'à trouver une somme égale à 50. Une méthode d'exploration est de commencer par les grosses commandes.

    25-20-12-10-10-10, il faut trouver 20 + 10 + 10 + 10. Ce n'est pas la solution qui prend le plus gros.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Responsable Qt & Livres



    Citation Envoyé par Flodelarab Voir le message
    C'est typiquement le "problème du sac-à-dos", pour lequel il n'existe aucune solution mathématiquement parfaite, actuellement.
    Ce n'est pas vraiment un problème de sac à dos (pour lequel il existe un algorithme super efficace de programmation dynamique, bien que pas polynomial : https://fr.wikipedia.org/wiki/Probl%...tion_dynamique), puisqu'on n'y considère qu'un seul sac à dos. C'est plutôt du remplissage de conteneurs (bin packing), la version de base cherchant à minimiser le nombre de palettes à remplir (même si aucune n'est remplie à fond) : https://en.wikipedia.org/wiki/Packing_problems, https://en.wikipedia.org/wiki/Bin_packing_problem. Wikipedia propose une série d'algorithmes efficaces (mais pas polynomiaux).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Nouveau membre du Club
    Bonjour !

    Merci pour vos réponses, je vais explorer ces pistes

  5. #5
    Responsable Qt & Livres

    À mon avis, le plus simple serait de t'interfacer avec une solveur d'optimisation mathématique, ça serait tellement plus simple d'adapter une formulation de bin packing pour avoir un maximum de palettes de cinquante items. Maintenant, ça nécessite d'appeler des bibliothèques externes (à la CPLEX ou Cbc, que tu peux appeler en C).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !