7

こんにちは、このように運営されている製造会社で働いています

サプライヤーがロールあたり8000メートルと言う特定のサイズの材料のロールを入手します。次に、2000メートル、3000メートルなど、より小さなサイズのさまざまな顧客から注文を受けます。現在のロールサイズと現在のさまざまな注文を入力するだけのソフトウェアを作成するにはどうすればよいか考えていました。無駄を最小限に抑えるために、さまざまなロールをカットするための最良の方法を生成します。

たとえば、特定の時点で、次の注文がある場合があります。3000メートルの2個4000メートルの2個1500メートルの6個

次に、入力する必要があるのは、上記の注文と、サプライヤが提供するロールサイズだけです。この例では、8000メートルであると想定しています。

次に、ソフトウェアは次のような出力を生成する必要があります。ロール1-4000メートルの2つのロールウェイスト0ロール2-3000メートルの2つのピースと1500の1つのピース（ロールウェイスト500）ロール3-15000の5つのピース（ロールウェイスト500）

上記の例は非常に小さいため、スクリプトを最適化する必要があります。通常、一度に約200個の注文があります

私はこれをPHPとMYSQLで実行することを検討しているので、Webベースであり、会社の周りの人々がそれを利用できます。

それぞれの組み合わせをブルートフォースで試すことでこれを実現できることを私は知っています。しかし、この場合に役立つ他の並べ替えアルゴリズムと手法はありますか。

4

2 に答える 2

1

これは、すべての注文が履行された後に廃棄物を最小限に抑えたい、よく知られた在庫削減問題です。

ウィキペディアでは次のように説明されています。

切り株問題は最適化問題、より具体的には整数線形計画問題です。これは、業界の多くのアプリケーションから発生します。あなたが製紙工場で働いていて、裁断待ちの決まった幅の紙のロールがいくつかあると想像してください。無駄（残り物の量）を最小限に抑えるために、ロールをどのようにカットしますか?

一般的なケースは NP 困難です。これは、最適な結果を生成するための高速なアルゴリズムがないことを意味します。

ただし、計算が高速で「合理的に」適切な近似解を生成するアルゴリズムを作成することはできます。

編集（礼儀@David）：

メーカーから入手した元のロールが常に同じサイズ (この場合は 8,000 メートル) である場合、カッティング ストック問題は1D ビン パッキング問題に縮小されます。 .)

@David が削除された回答で提案した貪欲なソリューションは、おおよそのソリューションをすばやく安価に取得する方法です。

編集2：

少し言い間違えました。ビンパッキング問題の既知の多項式時間近似スキームはありません。ただし、貪欲なアルゴリズムは実際にはかなり問題ありません。

于 2012-04-28T19:08:55.167 に答える
0

あなたは1次元のビンパッキングアルゴリズムを探しています。First-Fit、Best-Fit、Random-Fitを解決するための多くの戦略があります。私はphpclasses.orgでphpソリューションを作成しました。私のプログラムは無料でダウンロードできます（ビンパッキング）。実際、私はその賞を受賞しました。問題がそれほど大きくない場合は、ブルートフォース方式を試してみます。

于 2012-04-28T19:06:55.213 に答える