algorithm - 切り屑の少ないカッティングリストの算出

Question

私は、アルミ押出材の切断リストを作成するプロジェクトに取り組んでいます。

アルミ押し出し材の長さは 5m です。

5mの長さのアルミニウム押し出し材から切断する必要がある、より短い長さのリストがあります。

5mの長さのアルミニウム押し出し材から生じるオフカット廃棄物の量が最も少なくなるように、短い方の長さを切断する必要があります。

現在、私は通常、短い長さの最長のものを最初にカットし、短い長さの最短のものを最後にカットするように、カットリストを並べています。この規則の例外は、短い長さが 5m の長さのアルミニウム押し出し材の残りの長さに収まらない場合は常に、収まる最長の短い長さを使用することです。

これは、非常に効率的な (オフカットの無駄がほとんどない) カッティングリストを生成するように思われ、計算に時間がかかりません。ただし、カッティングリストは非常に効率的ですが、必ずしも最も効率的であるとは限りません。

妥当な時間で計算できる最も効率的なカッティングリストを計算する方法を知っている人はいますか?

EDIT：答えてくれてありがとう、私は「貪欲な」アプローチを使い続けます。なぜなら、それは非常に良い仕事をしているようで（効率的なカットリストを作成するための人間の試みを実行するよりも優れています）、非常に速いからです。

score 15 · Accepted Answer

これは、効率的に解決するのが難しい古典的な問題です。あなたが説明するアルゴリズムは欲張りアルゴリズムのように聞こえます。詳細については、このウィキペディアの記事をご覧ください。板取り問題

score 5 · Accepted Answer

この問題に関する具体的なアイデアはありません。恐れ入りますが、「遺伝的アルゴリズム」（これは次のようになります）を調べることができます...

カットする長さをランダムな順序で配置し、理想的なソリューションとの一致度に基づいてその順序にスコアを付けます（おそらく0％の無駄）。

次に、順序をランダムに変更し、スコアを付け直します。スコアが高い場合は、結果を捨てます。スコアが低い場合は、それを保持し、次の計算の基礎として使用します。スコアが許容範囲内になるまで続けます。

score 3 · Accepted Answer

あなたが説明したことは、ウィリーが述べたように、実際にカッティングストック問題として分類され、使用される押し出しの数ではなく無駄（残り物の合計）を最小限に抑えようとするため、ビンパッキング問題ではありません。

これらの問題は両方とも解決するのが非常に難しい場合がありますが、あなたが言及した「最適」アルゴリズム（現在の押し出しに適合する最長の「短い長さ」を使用）は、非常に低い複雑さで非常に良い答えを与える可能性があります。

score 2 · Accepted Answer

実は素材のサイズは決まっているのですが、リクエストが決まっていないのでビン詰めの問題です。

（私も仕事のために調べなければならないことがあるので、そうです！）

score 1 · Accepted Answer

私はここでもこの正確な（私の問題の長さは6 mです）問題に苦しんでいます。

私が取り組んでいる解決策は少し醜いですが、私はあなたの解決策に落ち着きません。説明させてください：

在庫サイズ5m

サイズをカットする必要があります（各1）：

**3,5

1

1,5 **

あなたの解決策：

3,5 | 0.5の無駄で1

1,5、残りは3,5

問題がわかりますか？

私が取り組んでいる解決策->ブルートフォース

1-考えられるすべてのソリューションをテストします

2-廃棄物でソリューションを注文する

3-最適なソリューションを選択してください

4-ソリューション内のアイテムを「ユニバース」から削除します

5-後藤1

私はそれが時間がかかることを知っています（しかし私は昼食に1時間30分かかります...だから... :)）

私は本当に最適な解決策が必要です（私はExcelで手作業（+-）でalmoust最適な解決策を実行します）、私が執着しているだけでなく、製品も安くはありません。

誰かが簡単でより良い解決策を持っているなら、私はそれが大好きです

score 1 · Accepted Answer

それはあなたが生産しているそれぞれの長さの量に依存すると思うので、それは興味深い問題です。それらがすべて同じ量であり、1つの5mの押し出しにそれぞれ異なる長さを得ることができる場合は、最適な解決策があります。

ただし、すべてが1つの押し出しに収まらない場合は、より大きな問題が発生します。各長さに対して同じ量のカットを維持するには、1つの押し出しに収まる長さの数（必ずしも順番ではない）を計算してから、各押し出しを順番に実行する必要があります。

7 に答える 7