algorithm - 産業分割問題

Question

金属製品工場の話です。長い鉄の棒を細かく切断してさまざまな製品に加工する機械があります。

たとえば、次の長さと数量のバーを製造する必要があります: 248mm を 2 本、1150mm を 5 本、2843mm を 6 本、3621mm を 3 本。

それがパーティショニング出力です。

入力側には、(例として) 2500mm のバーが 3 本、5000mm のバーが 2 本、8000mm のバーが 6 本、10000mm のバーが 3 本あります。

入力バーを最適にカットする方法を見つける必要があります。カット後の残りの部分 (小さすぎて使用できない残りの部分) は、できるだけ小さくする必要があります。

考えられるすべての組み合わせを単純に作成し、それらの中から最適なものを選択するアルゴリズムを作成しました。コードは機能しますが、入力と出力が少し大きくなるとすぐに、計算が非常に長く続く可能性があるため、問題への新しいアプローチを見つけなければなりません。

ヒントはありますか？

score 5 · Accepted Answer

あなたの問題は、オペレーションズリサーチではよくある問題です。カッティングストックの問題を見てください。この問題は、自分で考え出したように、本質的に NP 困難です。あまりうまくスケーリングしません。

それを解決する方法? モデルを理解できたら、混合整数計画法ソルバーを呼び出すのが最善です。以前にLPSolve 5.5を使用したことがあります

特にこの問題に対処するためにコーディングできる、より単純なアルゴリズムがあるかもしれません。これらのアルゴリズムの問題は通常、作成者が考えていなかった副次的な制約を追加する必要がある場合に発生します。MIP ソルバーは、より一般的なツールです。

score 4 · Accepted Answer

これは、可変サイズのビンパッキング問題と呼ばれます。これは NP 困難です。つまり、ソリューションは大規模な入力に対して常に失敗します。こちらの記事 (残念ながら私もアクセスできません) では、この問題に対処し、例として金属切削業界を使用しています。

score 1 · Accepted Answer

score 1 · Accepted Answer

ナップザックの問題に似ているように見えます (本当に厄介なことを知っています) NIST DADS (便利なリファレンス) でこれを見つけました非メンバーの場合、ACM よりも簡単にアクセスできますビンパッキング

4 に答える 4