-
05-07-2019 - |
質問
金属製品工場の話です。長い鉄の棒を細かく切断してさまざまな製品を作る機械があります。
たとえば、次の長さと数量のバーを作成する必要があるとします。248mmの2枚、1150mmの5つ、2843mmの6つ、3621mmの3つ。
それがパーティショニング出力です。
入力側には、(たとえば)2500mmの3バー、5000mmの2 bar、8000mmの6バー、10000mmの3 barがあります。
入力バーを最適にカットする方法を見つける必要があります。カット後の残り(小さすぎて使用できない残りの部分)はできるだけ小さくする必要があります。
私は、考えられるすべての組み合わせを単純に作成し、その中から最適なものを選択するアルゴリズムを作成しました。コードは機能しますが、入力と出力が少し大きくなると、計算が非常に長く続く可能性があるため、問題に対する新しいアプローチを見つける必要があります。
何かヒントはありますか?
他のヒント
これは、可変サイズのビンのパッキング問題と呼ばれます。これはNPハードです。つまり、入力が大きい場合、ソリューションは必ず失敗します。この記事、こちらは、残念ながら私もアクセスできません。アドレスこの問題は、例として金属切削産業を使用しています。
線形プログラミングはあなたの友人です。一般的に、特に、 http://en.wikipedia.org/wiki/Linear_programming を参照してください。 、 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 。
>ナップザック問題(本当に厄介なことを知っている)に似ているようです.nist.gov / div897 / sqg / dads / HTML / binpacking.html "rel =" nofollow noreferrer ">ビン詰め