Calcul de la longueur de stock optimale

Question

Ceci est similaire à cutting stock problem, mais avec une légère différence. Je veux savoir quelle est la longueur optimale du stock en fonction de la taille des coupes.

complications possibles:

1. L'article de Wikipedia sur le problème des stocks de coupe est bien au-dessus de ma tête. Je soupçonne que la compréhension de la façon de résoudre ce problème pourrait être critique pour résoudre mon propre problème.

2. Certaines longueurs de coupe sont plus courantes que d'autres. Tout ce qui est inférieur à 2 pieds est considéré comme de la ferraille, alors nous préférons ne pas faire une coupe qui laisse un gros morceau de ferraille. D'un autre côté, nous ne voulons pas conserver de nombreux stocks partiels dans l'espoir que nous en aurons besoin un jour.

Answer 1

Ai-je bien compris. Vous avez différentes longueurs coupées (3,6, 10,2, 8,3, 7.3, ...) et vous voulez savoir quel stock est le meilleur pour vous donner le moins de déchets de coupure? Voulez-vous trouver une seule valeur de stock, ou plusieurs? Y a-t-il une longueur maximale, une longueur minimale? Si vous n'avez pas une longueur maximale, le meilleur choix est d'utiliser un stock très long où toutes les longueurs de coupe correspondent exactement, mais je ne pense pas que ce soit ce que vous voulez ..

MISE À JOUR J'ai travaillé sur ce problème pendant un certain temps dans le cadre de mon travail, nous avons un produit qui le fait (et plus). Pour une solution simple, vous pouvez implémenter une heuristique First Fit Decreasing qui fonctionne avec une longueur de stock donnée. Puis utilisez au hasard plusieurs longueurs de stock et utilisez chaque fois l'heuristique pour les remplir. Rappelez-vous la longueur de stock avec le gaspillage minimum.

Si vous voulez un algorithme plus avancé, je vous conseille d'acheter notre logiciel :-)

Answer 2

Le problème dépend également du nombre de stocks S que vous souhaitez utiliser.

Si S = 1, la longueur du stock doit être la somme des tailles de toutes les coupes. Si S> 1, vous voulez diviser la taille des coupes en groupes S et minimiser la différence entre les sommations de tailles des coupes dans chaque groupe. Ceci est très proche du partition problem, qui est NP-difficile.

Answer 3

Il semble que vous ayez la version "en ligne" de ce problème d'optimisation ou similaire. en ligne signifie que vous ne connaissez pas toutes les informations à l'avance, -à-dire que vous devez prendre des décisions que les ordres viennent dans