質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.75%

  • アルゴリズム

    380questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

在庫計算の効率的なアルゴリズムについて

受付中

回答 2

投稿 編集

  • 評価
  • クリップ 8
  • VIEW 656

foxriver

score 4

現在在庫管理を行うシステムを作成しており、その際に在庫を効率的に使用するアルゴリズムを考えています。

ini_len = 50
stocks = [{"sid":1,"stock":25},
              {"sid":2,"stock":14},
              {"sid":3,"stock":5},
              {"sid":4,"stock":3}
              {"sid":5,"stock":9}
 ]
materials = [{"mid":1,"len":2,"count":19},
                  {"mid":2,"len":5,"count":9},
                  {"mid":3,"len":3,"count":15}
 ]


上記は規定値50(ini_len)の在庫が残り(stocks)25m,14m,5m,3m,9mあり
それらに対してmaterialsがそれぞれ一個あたりどのくらいの在庫を使用するか(len)、それが何個必要か(count)を表しています。
ここで全てのmaterialを処理するためにstocksからの効率的な消費を行い(sid4と5は3の倍数なのでmidからの消費を行なって完全になくすなど)、かつ不足していた場合は新たに在庫を追加(今回の場合ini_len=50のため、stocksに50が追加されるイメージ)するという処理を行いたいのですが、こうした在庫の消費と新規在庫の追加を実現するアルゴリズムがわからず悩んでいます。

目的としているアウトプットの形としては、上記の例だと
"""
sid1(stock=25)はmid2(len=5)から5個使う 完全に消費
sid2(stock=14)はmid1(len=2)から7個使う 完全に消費
sid3(stock=5)はmid2(len=5)から1個使う 完全に消費
sid4(stock=3)はmid3(len=3)から1個使う 完全に消費
sid5(stock=9)はmid3(len=3)から3個使う 完全に消費
"""
とした上で
残りのmaterial
mid1(len=2) 12個
mid2(len=5) 3個
mid3(len=3) 11個
について

新規作成の
"""
sid6(stock=50)はmid2(len=5)から3個、mid3(len=3)から11個、mid1(len=2)から1個使う
→完全に消費
sid7(stock=50)はmid1(len=2)から11個使う
→残り(50-22=28)
"""
というようにどこから何をどれくらい使うかということまで情報として持つことができればと思っています。

どなたか解決策を知っていましたらご教授いただければと思います。

========補足============
今回は在庫の残量が全て何らかのマテリアルで割り切れましたが、もし割り切れなくて消費しきれず、新規の在庫を追加することも問題はありません。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • jun68ykt

    2018/01/19 16:51

    与件を確認させてください。stocks のいずれかの要素の stock が 1 になった場合、その残りの 1 は、どのmaterialでも使えないので、破棄するしかなく、次の在庫追加時も、この 1 は無いものとして扱うということでよいですか?ちなみにstocks にある原材料は、何か、帯状のものをイメージしてます。

    キャンセル

  • foxriver

    2018/01/19 17:00 編集

    @jun68ykt はい、その解釈で問題ありません。厳密にいうとデータベースのデータからの削除は行いませんが、今回の計算に関してはどの条件でも利用は不可能なので、計算上は破棄で問題ありません。また原材料についてもそのイメージの通りです。今回は紙のロールです。

    キャンセル

回答 2

+7

直接の回答ではありませんが…

提示された問題はビンパッキング問題という最適化問題と同じだと考えられます。
これは、複数の大きさの異なる箱に複数の大きさの異なるモノを詰めるとき、必要な箱の個数を最小化する問題です。

今回の問題でいえば、箱=在庫(紙のロール)で、モノ=マテリアル(製品?) となります。
ただし在庫だけではモノが収まらない(足りない)場合は、新たに大きさ(長さ)50の箱(ロール)をいくつか購入する必要があり、その個数を最小化することになります。
また、箱の個数を最小化するのではなく、製造後の残り在庫の総長を最小化するほうが自然かもしれません。

このような最適化問題は、うまく定式化することで、既存のソルバーで解ける可能性があります。
ということで検索してみたところ、以下のページが参考になりそうです。
ビンパッキング問題の解き方

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

今回実現しようとしている仕組みは、在庫引当に関することだと理解しました。

業種・品種により引当のルールが異なると思いますが、
在庫管理といえば、
・余剰在庫は限りなく0にする。
・欠品(在庫不足)は起こさないようにする
の条件がつくことが多いと思います。

食品・医薬などでは、賞味期限・有効期限がありますし、アパレルでは、流行などもありますので、
古いものから先に引当(消費)する
という条件が優先されることが多いと思います。

今回の例では、

全てのmaterialを処理するためにstocksからの効率的な消費
かつ不足していた場合は新たに在庫を追加

とありますので、廃棄在庫(どこにも利用できない在庫)を最小にすることを考えて見ます。

  1. 情報の持ち方を整理します。
    stocksには割当済み在庫量(alloc_stock)をもたせます。
    materialsにも引当済み数量(alloc_count)をもたせます。
    割当情報として、stock_allocationを準備します。
    start

  2. 不足在庫の補充をします。
    stocksの総量 = 25+14+5+3+9 = 56
    materialsの総消費量 = 2*19 + 5*9 + 3*15 = 128
    不足量 = 128 - 56 = 72
    なので、在庫を2回分補充します(50×2)
    stock_start

  3. 引当は1つあたりの消費量の多い品目(mid2)から引当計算を行います。
    stocksの引当可能在庫(stock - alloc_stock)を1つあたりの消費量で割って、商と余りを求めます。
    引当は、下記の優先度で行います。
    ①余りが最小
    ②在庫量が最小
    ③midが最小
    引当結果は、stock_allocationに保持して、
    stocksのalloc_stock、materialsのalloc_countを更新します。
    mid1

  4. 次に1つあたりの消費量の多い品目(mid1)の引当計算を行います。
    2.と同様に、stocksの引当可能在庫(stock - alloc_stock)を1つあたりの消費量で割って、商と余りを求め、引当を行います。
    イメージ説明

以下、全ての品目に対して、同様に引当を行います。
全ての品目の引当が完了したら、stock_allocationには、
どの品目で、どの在庫をいくつ使用するか
の情報が保持されることになります。
イメージ説明

stocksにalloc_stockを持つことで、引当可能在庫の情報を管理できます。
在庫量は、実際に消費しないと減少しないと思いますので、
使う予定を管理しておく必要があると考えます。

以上、参考になればと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.75%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • アルゴリズム

    380questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。