質問
私はアルミニウム押出材の切断リストを作成するプロジェクトに取り組んでいます。
アルミフレームの長さは5mです。
5 メートルの長さのアルミニウム押出材から切断する必要がある短い長さのリストがあります。
5m の長さのアルミニウム押出材から、端材の発生量が最も少ない順に、短い長さのものを切断する必要があります。
現在、私は通常、短い長さの中で最も長いものが最初にカットされ、より短い長さの中で最も短いものが最後にカットされるような方法でカットリストを注文しています。このルールの例外は、5 メートルの長さのアルミニウム押出材の残りに短い長さが収まらない場合は、収まる最も長い短い長さを使用することです。
これにより、非常に効率的な (オフカットの無駄がほとんどない) カッティング リストが生成されるようで、計算にそれほど時間はかかりません。しかし、たとえカットリストが とても 効率的であるとは限りませんが、 ほとんど 効率的。
合理的な時間で計算できる最も効率的な切断リストを計算する方法を知っている人はいますか?
編集:回答ありがとうございます。「貪欲な」アプローチは非常に良い仕事をしているようで(効率的なカットリストを作成する人間の試みを上回り)、非常に高速であるため、「貪欲な」アプローチを使い続けます。
他のヒント
申し訳ありませんが、この問題に関する具体的なアイデアはありません。しかし、「」を検討してみてはいかがでしょうか。遺伝的アルゴリズム' (これは行きます 何か このような)...
切断する長さをランダムな順序で配置し、その順序が理想的なソリューションとの適合度 (おそらく無駄が 0%) に基づいてスコアを与えます。
次に、順序をランダムに変更し、スコアを再設定することを繰り返します。スコアの方が高い場合は、結果を無視します。スコアが低い場合は、それを保持し、次の計算の基礎として使用します。スコアが許容範囲内になるまで続けてください。
実際には、マテリアルのサイズは決まっていますが、リクエストは決まっていないため、ビン詰めの問題になります。
また、 ウィキペディアが役に立ちます!
(仕事上も調べないといけないことがあるかもしれないので、イェーイ!)
これは興味深い問題です。なぜなら、それは生産する各長さの量に依存すると思うからです。それらがすべて同じ量で、それぞれ異なる長さを 1 つの 5 メートルの押し出し材に入れることができる場合、最適な解決策が得られます。
ただし、すべてが 1 つの押し出しに適合しない場合は、さらに大きな問題が発生します。各長さで同じ量のカットを維持するには、1 つの押し出しに適合できる長さ (順序どおりである必要はありません) を計算し、各押し出しを順番に実行する必要があります。
ここでも、まさにこの問題(私の問題の長さは6メートル)に苦労しています。
私が取り組んでいる解決策は少し醜いですが、私はあなたの解決策に満足しません。説明しましょう:
在庫サイズ 5メートル
サイズにカットする必要があります (各 1 つ):
**3,5
1
1,5**
あなたの解決策:
3,5 | 1 0,5の無駄で
1,5 3.5が残った状態で
問題がわかりましたか?
私が取り組んでいる解決策 -> ブルートフォース
1 - 考えられるすべての解決策をテストする
2 - 廃棄物に応じてソリューションを注文する
3 - 最適なソリューションを選択する
4 - ソリューション内のアイテムを「ユニバース」から削除します。
5 - 後藤 1
時間がかかるのはわかっています(でも、昼食までに 1 時間 30 分かかります...それで...:))
私が本当に最適解を必要としているのは、私がこだわりがあるだけでなく、製品が安くないからです (私は Excel でほぼ最適解を手動で (+-) 実行しています)。
誰かが簡単でより良い解決策を持っているなら、私はそれが大好きです