Problème de partitionnement industriel

Question

Nous parlons d'une usine de produits métalliques. Il existe une machine qui coupe de longues barres de fer en petites pièces qui sont ensuite utilisées pour créer divers produits.

Par exemple, j'ai l'obligation de produire des barres de longueur et de quantité suivantes: 2 morceaux de 248mm, 5 de 1150mm, 6 de 2843mm, 3 de 3621mm.

C'est la sortie du partitionnement.

J'ai côté entrée (encore une fois par exemple) 3 barres de 2500mm, 2 barres de 5000mm, 6 barres de 8000mm et 3 barres de 10000mm.

Je devrais trouver un moyen de couper les barres d’entrée de manière optimale - le reste (les parties trop petites pour être utilisées) après la coupe devrait être aussi petit que possible.

J'ai créé un algorithme qui crée simplement toutes les combinaisons possibles, puis choisit la meilleure parmi celles-ci. Le code fonctionne, mais dès que les entrées et les sorties sont un peu plus grosses, le calcul peut durer très longtemps. Je dois donc trouver une nouvelle approche du problème.

Avez-vous des indices?

Answer 1

Votre problème est assez courant dans la recherche opérationnelle. Regarder Problème de stock de taille réduite . Ce problème est essentiellement NP-difficile, comme vous l'avez compris vous-même. Cela ne va pas très bien.

Comment le résoudre? Une fois que vous êtes capable de comprendre le modèle, il serait préférable d'appeler un solveur de programmation mixte entier. J'ai déjà utilisé LPSolve 5.5

.

Il existe peut-être des algorithmes plus simples que vous pourriez coder pour traiter ce problème en particulier. Le problème de ces algorithmes se pose généralement lorsque vous devez ajouter des contraintes latérales auxquelles les auteurs n’ont pas pensé. Le solveur MIP est un outil beaucoup plus générique.

Answer 2

C’est ce que l’on appelle le problème d’emballage du bac de taille variable . C'est un processus difficile, ce qui signifie que votre solution échouera invariablement pour des entrées volumineuses. Cet article, ici , auquel malheureusement je n'ai pas accès, adresses ce problème et utilise l’industrie de la coupe du métal comme exemple.

Answer 3

La programmation linéaire est votre amie. Voir http://en.wikipedia.org/wiki/Linear_programming en général et en particulier , http://en.wikipedia.org/wiki/Linear_programming#Uses , < a href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel = "nofollow noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms .

Answer 4

On dirait que c'est similaire au problème de sac à dos (sachez que c'est vraiment méchant). J'ai trouvé ceci sur les DADS du NIST (référence pratique) plus facile à obtenir que l'ACM pour les non membres Emballage des bacs