Optimization of work distribution using one-dimensional bin packing algorithm_3.Implementation (1)

3. Bin Packing Algorithm Implementation

A development environment is required to input the list of items and constraints, implement the algorithm, and check the results. There are several development environments such as Excel VBA, Python, and R. Among them, Excel VBA does not have an open library, so you have to write most of the source code yourself. Python and R can implement the bin packing algorithm directly, or use an already provided package. Here, I will look at how to use the tool that implements the algorithm myself with Excel VBA and the package provided in Python.

3.1. Excel VBA based tool

A tool or language that implements an algorithm usually receives a data file as input separately from the program's source code. Excel VBA has the characteristic of being able to manage program source code and data in one file and manage them separately. Here, the program source code and data are managed in one file.

The configuration and source code of the tool that manages the list of items by inputting them into an Excel sheet and implements the one-dimensional bin packing algorithm with VBA will be briefly introduced below. The entire source code is provided as an appendix. https://github.com/DAToolset/1D-bin-packing can also be checked.

**Note: This article does not cover the concept or syntax of Excel VBA, but will be written in detail in a separate article in the future.

The overall configuration of the tool is shown in the figure below. Input data in “Run” sheet, set options, and click “Run Bin Packing” button to check the execution result.

Details of the four areas in the figure above are explained in the following table of contents.

3.1.1. Input material configuration

In the Item list, enter Name and Size in the following format.

Here, the Bin Item Name is a name for identifying the type of an Item, and it can be appropriately designated according to the Item type. For example:

• If the Item is a database table, the table name
• If the Item is a Job, the job name
• In addition, a name suitable for identifying each item (order number, etc. is also possible)

Note that there should be no duplicate names in the Item list. This is because even if the size is the same, it is necessary to know that they are different objects to determine which object to fill in the bin.

In Size, enter the size of each Item. For the size, the number of rows and bytes can be used in the case of a table, and in the case of a job, the execution time can be input in minutes or seconds. The required time should be checked in the job execution record, but it is recommended to calculate and use the average value excluding the maximum and minimum values among the last 5 or more times required.

If you need multiple data sets, you can copy and input the “Run” sheet. The name of the sheet can be any name, but It is good to specify in the form of to distinguish it from other sheets. For example, it is designated as “Run_Org” as shown in the figure below.

Bin Packing can be executed by creating multiple data sets and setting different data or different options in each data set sheet. The sheet on which the execution result is displayed is not created for each data set but is used permanently. If you want to keep the results of each data set, you can save the Excel file under a different name and create a separate file.

3.1.2. Option setting

The maximum size of the bin, which is a constraint, and whether to sort the reference column in descending order are entered in the following format.

Max Bin Size is the maximum size to be assigned to one bin. In other words, when filling multiple items into one bin, it is a constraint on the sum of Item Sizes.

Item Size standard column is a column that specifies which value to use when there are multiple size values in one bin item. For example, suppose that it is configured so that multiple sizes can be entered into one item as follows.

Columns that can be used as size values are C to I. Enter the column name to select which column to use as the size input value among them. To simulate by creating a random value in Size, copy the value generated by the formula in the J column (Rando Size), paste it as a value in the I column (Simulation), and then execute it by designating the reference column as I. . The reason why you should not specify the J column is because a formula is used in the J column and a new value is created every time it is calculated, so it is impossible to know which value was used as an input value.

If the item size descending sort option is selected (checked), first, the item size is sorted in descending order and Bin Packing algorithm is applied.

3.1.3. Run Bin Packing

When the input data configuration and option settings are completed, click the “Run BinPacking” button to execute.

If there is a duplicate in “Bin Item Name” when executing, an error may occur. Check and remove the duplicate and execute.

3.1.4. Check the execution result

The execution result consists of 5 sheets. The overall summary is checked in the Result summary sheet, which collects the execution results of each algorithm, and the detailed results of each algorithm are checked in each sheet.

• Result Summary: A sheet in which the results of executing each algorithm can be seen at a glance
• Next Fit: The result sheet of running the Next Fit algorithm
• First Fit: The result sheet of running the First Fit algorithm
• Worst Fit: The result sheet of running the Worst Fit algorithm
• Best Fit: The result sheet of running the Best Fit algorithm

The contents of the Result summary sheet are as follows.

Reference information for the Max Bin Size set in the options is displayed at the top, and a chart of the results of running each of the four algorithms is shown at the bottom.

The composition of the information displayed on the result sheet after executing each algorithm is as follows.

Item	Contents
① Result list	As a result of executing the bin packing algorithm, you can check which items are filled in which bins. Here, the Bin name is created with the rule of “Bin_” + sequence number (5 digits) in the process of program processing.
② Bin total	This is a pivot table for calculating the sum of Item Sizes in units of bins. <④ Bin Total Chart> is created using this pivot table as a data source.
③ Execution information	It displays the time taken to process the algorithm, the total of the remaining space in all bins, the total space, and the space inefficiency information. The space inefficiency is calculated as (Bin Total Residual Space Sum)/(Total Space Sum).
④ Bin Total Chart	<② Bin total pivot table> is visualized as a column chart.

▼ Next Fit Execution Results

▼ First Fit Run Results

▼ Worst Fit Execution Results

▼ Best Fit Run Results

3.1.5. VBA code configuration

The source code that implements Bin Packing with VBA is briefly described. The overall composition of the VBA Project is as follows.

• Sheet (Excel UI) manages the list of input data and displays the input and output of the algorithm processing result.
• A module is responsible for handling and controlling the entire processing process, creating instances of classes, and common functions.
• The class is responsible for functions such as loading input data into memory, implementing algorithms, and outputting result data.

The purpose of the detailed items is as follows.

• Sheet
  • Each sheet: input data/option setting, execution result output
• module
  • modControl: Manages the entire process of objectifying a class, loading input data, implementing each bin packing algorithm, and outputting results
  • modFactory: Manage instantiation of classes
    • The VBA class cannot specify the input parameter of the constructor, so it is configured to create an object using the Factory Pattern.
  • modUtil: Manage functions such as logging and setting the format of the required time string
    • Here, Logging does not leave a file, but it is configured so that log messages can be checked on the Debugger with OutputDebugString among Windows APIs.
    • Debugger recommends using DebugView
• class
  • CBin: Class of 1 Bin
    • Main methods: AddBinItem, IsAbleToAdd
  • CBinItem: Class of 1 Item to be put in Bin
    • That is, a class corresponding to one line of input data.
    • Main method: CompareTo
  • CBinItemCollection: A collection class that manages a list of multiple BinItems.
    • Main methods: Add, Sort, GetString
  • CPacker: A class that manages a list of bins as a Collection.
    • Implement an algorithm that fills the input data to an appropriate place among the existing bin list or creates a new bin to fill it
    • Main methods: DoPacking, Add, GetNewBin, GetBinNextFit, GetBinFirstBit, GetBinWorstFit, GetBinBestFit, PackToBin, DoOutput, GetRemainSizeSum
  • CTimer: A class for measuring time spent
    • Using Windows API QueryPerformanceCounter, QueryPerformanceFrequency
    • Main methods: StartCounter, TimeElasped

In order to properly apply the OOP concept, it is standard to expose public properties composed of Getter/Setter without public member variables in the class. However, in this tool, public properties are not used for the convenience of implementation. However, member variables, functions, and procedures that can be accessed from outside are declared public, and objects to be accessed from outside are declared private.

The relationship between the classes defined in the VBA source code is briefly expressed as a UML Class Diagram as follows.

The relationship between classes in the class diagram above is a has a relationship. That is, in the composition relationship defined between the two classes, the filled diamond (♦) is the container.

 From the right to the left, it can be seen that the lower class is connected to the upper class. One input data is managed by the CBinItem class, and the CBinItemCollection class manages the entire input data as a collection of CBinItems. The CBin class manages individual bin objects and manages the list of items filled in each bin as an object of the CBinItemCollection class. The CPacker class implements the algorithm and manages the entire result Bin object as a collection of the CBin class. Each class has a composition relationship, so when the container object is removed, all sub-objects are removed. The CTimer class is used in the CPacker class to measure the execution time of the algorithm.

Here, the CBinItemCollection class is used to manage the entire input data and also to manage the list of items filled in each bin. For example, assuming that 100 items are filled with 10 items in 10 bins, the object that manages all 100 items is also of the CBinItemCollection class type, and the object that manages 10 items filled in each bin is also of the CBinItemCollection class type. to be.

Refer to the appendix for the source code of each class, and the pseudo code of modControl, a module that controls the entire process of loading input data, executing algorithm, and outputting result data, is as follows.

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

---

In the next article, we will look at the source code implemented using the Python Bin Packing package and the execution result.

---

<< List of related articles >>

• Optimization of work distribution using one-dimensional bin packing algorithm_1.Overview
• Optimization of work distribution using one-dimensional bin packing algorithm_2.Algorithm (1)
• Optimization of work distribution using one-dimensional bin packing algorithm_2.Algorithm(2)
• Optimization of work distribution using one-dimensional bin packing algorithm_3.Implementation (1)
• Optimization of work distribution using one-dimensional bin packing algorithm_3.Implementation (2)
• Optimization of work distribution using one-dimensional bin packing algorithm_4.Attachment
• One-dimensional Bin Packing Tool Recent Changes (as of March 21, 2021)
• Work distribution optimization tool using one-dimensional bin packing algorithm Full Contents, Download