1次元Bin Packingアルゴリズムを活用した作業配分最適化_3.実装(1)

3. Bin Packingアルゴリズムの実装

Itemのリストと制約を入力し、アルゴリズムを実装して結果を確認するには、開発環境が必要です。開発環境にはExcel VBA、Python、Rなど様々なものがある。このうち、Excel VBAは公開されているライブラリがなく、ソースコードをほとんどほとんど直接作成しなければならない。 PythonとRはBin Packingアルゴリズムを直接実装することも、すでに提供されているパッケージを使用することもできます。ここでは、Excel VBAで私が直接アルゴリズムを実装したツールとPythonで提供されるpackageを利用した活用方法を見ていきます。

3.1。 Excel VBAベースのツール

アルゴリズムを実装するツールや言語は通常、プログラムのソースコードからデータファイルを別々に入力として受け取ります。 Excel VBAは、プログラムのソースコードとデータを1つのファイルで管理することができ、分離して管理することもできる特性がある。ここでは、プログラムのソースコードとデータを1つのファイルで管理するように実装しました。

ItemのリストをExcel Sheetで入力して管理し、1次元Bin PackingアルゴリズムをVBAで実装したツールの構成とソースコードについて以下に簡単に紹介する。ソースコード全体は別添で提供し、 https://github.com/DAToolset/1D-bin-packing でも確認できる。

**注：この記事では、Excel VBAの概念や文法などについては扱わず、今後別の記事で詳細に作成する予定だ。

ツールの全体構成は次の図のようになります。 「Run」シートにデータを入力してオプションを設定し、「Run Bin Packing」ボタンをクリックして実行結果を確認します。

上図の4つの領域の詳細については、次の各目次で説明します。

3.1.1.入力データの構成

項目リストには、次の形式で名前とサイズを入力します。

ここで、Bin Item Nameは、Itemがどのオブジェクトであるかを識別するための名称で、Itemの種類に応じて適切に指定すればよい。たとえば、次のようになります。

• ItemがDatabase Tableの場合、対応するtable名
• アイテムがジョブの場合、対応するジョブ名
• その他、各Itemを識別するのに適した名称（順番なども可能）

注意するのは、Itemリストに名称重複があってはならないという点だ。 Sizeは同じでも異なった個体であることが分かってこそ、Binにどの個体を埋めるかを判断できるからだ。

Sizeには各Itemのサイズを入力します。 Sizeはtableの場合はrow数、byte数を使用でき、jobの場合は実行所要時間を分または秒単位で入力して使用することができる。所要時間はjobの実行記録で確認して記入するが、なるべく最近5回以上の所要時間のうち最大値と最小値を除いた平均値を計算して使用するのがよい。

さまざまな資料セットが必要な場合は、「Run」シートをコピーして入力してください。シートの名称はどんな名前でも構いませんが、の形で指定することが他のシートと区別できていい。たとえば、次の図のように「Run_Org」などで指定します。

複数のデータセットを作成して、各データセットシートに異なる材料または異なるオプションを設定してBin Packingを実行できます。実行結果が表示されるシートは、データセットごとに作成されず、固定的に使用される。各データセットで実行される結果をそれぞれ維持したい場合は、Excelファイルを別の名前で保存して別々のファイルとして生成する方法を使用すればよい。

3.1.2。オプション設定

制約条件であるBinの最大Sizeと基準列、降順ソートするかどうかは、次のように入力します。

Max Bin Sizeは、1つのBinに割り当てる最大サイズです。つまり、複数のItemを1つのBinに埋めるときのItem Sizeの合計に対する制約事項です。

Item Size 基準列は、1 つの Bin Item にさまざまな Size 値があるときにどの値を使用するかを指定する列です。たとえば、次のように単一のアイテムに複数のサイズを入力できるように設定する場合を考えてみましょう。

Size値で使用できる列はC～Iまでです。このうち、どの列をSize入力値として使用するかを選択するために列名を記入します。 Sizeに任意の値を生成して模擬実験するには、J列(Rando Size)で式で生成された値をコピーし、I列(Simulation)に値として貼り付けてから、基準列をIに指定して実行すればよい。 J列を指定しない理由は、J列に式が使用されて計算されるたびに新しい値が生成され、したがってどの値が入力値として使用されたかが不明になるためです。

Item Size降順ソートオプションを選択（チェック）すると、まずItemのSizeで降順ソートしてBin Packingアルゴリズムを適用する。

3.1.3。 Bin Packingの実行

入力データ構成とオプション設定まで完了したら、「Run BinPacking」ボタンをクリックして実行します。

実行時に「Bin Item Name」に重複があるとエラーが発生する可能性があります。

3.1.4。実行結果の確認

実行結果は5つのシートで構成されています。全体の要約は、各アルゴリズムの実行結果をまとめたResult summary sheetで確認し、各アルゴリズムの詳細結果は各sheetで確認する。

• Result Summary: それぞれのアルゴリズムを実行した結果を一目でわかるようにまとめたシート
• Next Fit：Next Fitアルゴリズムを実行した結果シート
• First Fit：First Fitアルゴリズムを実行した結果シート
• Worst Fit：Worst Fitアルゴリズムを実行した結果シート
• Best Fit：Best Fitアルゴリズムを実行した結果シート

Result summary sheetの内容は次のとおりです。

上段にはオプションで設定したMax Bin Sizeを参照情報が表示され、下段には4つの各アルゴリズムを実行した結果チャートが表示されます。

各アルゴリズムを実行した結果、シートに表示される情報の構成は次のとおりです。

アイテム	内容
①結果リスト	Bin Packingアルゴリズムを実行した結果、どのItemがどのBinに埋められているかを確認できます。ここで、Bin名称は、プログラム処理過程で“Bin_”+順番(5桁)の規則で生成する。
② Bin 合計	Bin単位でItem Sizeの合計を計算するためのピボットテーブルである。 <④Bin合計Chart>は、このピボットテーブルをデータソースとして作成されます。
③実行情報	アルゴリズムの処理にかかった所要時間、Bin 全残余空間の合計、全空間合計、空間非効率情報を表示する。空間非効率は、（ビン全体の残余空間合計）／（全空間合計）として計算される。
④ Bin 合計 Chart	<②Bin合計ピボットテーブル>を縦棒グラフで表現して視覚化した内容である。

▼ Next Fit 実行結果

▼ First Fit 実行結果

▼ワーストフィット実行結果

▼ベストフィット実行結果

3.1.5。 VBAコードの設定

Bin PackingをVBAで実装したソースコードについて簡単に説明します。 VBAプロジェクトの全体的な構成は次のとおりです。

• Sheet（Excel UI）は、入力データのリストを管理し、入力とアルゴリズム処理の結果の出力を表示します。
• モジュールは、全体の処理過程を処理し制御する役割とクラスのインスタンス生成、共通機能などを担当する。
• クラスは、入力データのメモリ積載とアルゴリズムの実装、結果データ出力などの機能を担う。

詳細項目の用途は次のとおりです。

• シート
  • 各シート：入力データ/オプション設定、実行結果出力
• モジュール
  • modControl: クラスをオブジェクト化し、入力資料の積み込み、Bin Packing角アルゴリズムの実装、結果出力などの全体処理管理
  • modFactory: クラスのオブジェクト化管理
    • VBAのクラスはコンストラクタの入力パラメータを指定できず、Factory Patternでオブジェクトを生成するように構成されています
  • modUtil: Logging、所要時間の文字列フォーマット設定などの機能管理
    • ここで Logging はファイルに残さず、Windows API 中 OutputDebugString で Debugger 上で log メッセージを確認できるように構成する。
    • DebuggerはDebugViewを使用することをお勧めします
• クラス
  • CBin: Bin 1個単位のクラス
    • 主なメソッド：AddBinItem、IsAbleToAdd
  • CBinItem: Bin に入れる Item 1 個単位のクラス
    • つまり、入力データの1行に対応するクラス
    • 主なメソッド：CompareTo
  • CBinItemCollection: 複数の BinItem のリストを管理するコレクションクラス
    • 主なメソッド：Add、Sort、GetString
  • CPacker: Bin リストを Collection で管理するクラス
    • 入力データを既存のビンリストの適切な場所に埋めるか、新しいビンを作成して埋めるアルゴリズムの実装
    • 主なメソッド：DoPacking、Add、GetNewBin、GetBinNextFit、GetBinFirstBit、GetBinWorstFit、GetBinBestFit、PackToBin、DoOutput、GetRemainSizeSum
  • CTimer：所要時間を測定するためのクラス
    • Windows API QueryPerformanceCounter、QueryPerformanceFrequency の使用
    • 主なメソッド：StartCounter、TimeElasped

OOPの概念を適切に適用するには、クラスにはpublicメンバー変数なしでGetter / Setterで構成されたpublic Propertyを公開するのが定石です。しかし、このツールでは実装の便宜上、public Propertyを使用しなかった。ただし、外部からアクセス可能なメンバ変数と関数、プロシージャはpublicで宣言し、外部からのアクセスを制限する対象はprivateで宣言して区分した。

VBAソースコードで定義されたクラス間の関係をUML Class Diagramで簡単に表現すると、次のようになります。

上記のClass Diagramのクラス間の関係はhas a関係です。つまり、2 つのクラス間で定義された composition 関係で満たされた菱形（◆）の方が container です。

 右から左に行くほど、サブクラスから上位クラスにつながると見られる。入力データの1つはCBinItemクラスで管理し、CBinItemCollectionクラスは入力データ全体をCBinItemのコレクションとして管理します。 CBinクラスはBin個別オブジェクトを管理し、各Binに埋め込まれたItemのリストをCBinItemCollectionクラスのオブジェクトとして管理します。 CPackerクラスはアルゴリズムを実装し、結果のBinオブジェクト全体をCBinクラスのコレクションとして管理します。各クラスは、composition関係でcontainerオブジェクトが削除されると、すべての子オブジェクトが削除されます。 CTimerクラスは、アルゴリズムの実行時間を測定するためにCPackerクラスで使用されます。

ここで、CBinItemCollectionクラスは、入力資料全体を管理する目的にも使用し、各Binに埋め込まれたItemリストを管理する目的にも使用します。たとえば、100個のItemが10個のBinにそれぞれ10個ずつ埋められたとしたとき、全体100個のitemを管理するオブジェクトもCBinItemCollectionクラスtypeであり、各Binに埋め込まれた10個ずつのitemを管理するオブジェクトもCBinItemCollectionクラスtypeである。

各クラスのソースコードは別添を参考にし、入力データ積載からアルゴリズム実行、結果データ出力の全過程を制御するモジュールmodControlの擬似コードは次の通りである。

Public Sub RunBinPacking()
    입력자료를 읽어들여 CBinItemCollection type의 oInputItemCol 변수에 적재
    입력자료의 정렬 실행을 선택했으면 oInputItemCol 내림차순 정렬
    각 알고리즘의 실행결과를 담을 변수 선언
    각 변수에 최대 Bin 크기와 PackingType을 설정하여 개체 생성
    각 변수에 입력자료 채우기
    결과출력
    각 변수 메모리에서 삭제하여 정리
End Sub

---

次の記事では、Python Bin Packingパッケージを利用して実装したソースコードと実行結果について説明します。

---

<< 関連記事のリスト >>

• 1次元Bin Packingアルゴリズムを活用した作業配分の最適化_1.概要
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_2.アルゴリズム(1)
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_2.アルゴリズム(2)
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_3.実装(1)
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_3.実装(2)
• 1次元Bin Packingアルゴリズムを活用した作業配分の最適化_4。
• 1次元Bin Packingツール最近の変更（2021-03-21基準）
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化ツール