One-dimensional Bin Packing Tool Recent Changes (as of March 21, 2021)

1. Summary of Changes

The description of the 1D Bin Packing tool written on the blog is based on 2017-11-19.

Related articles: Optimization of task distribution using one-dimensional bin packing algorithm_1.Overview – Productivity Skills (prodskill.com)

As there are improvements while carrying out the K company project on March 21, 2021, it will be organized separately.

• Change Item Size from Integer (Long) to Real (Double) (Change variable name prefix)
• BinItem name case sensitive (Changed from Collection to Dictionary)
    – Change class name (CBinItemCollection -> CBinItemDic)
• Sort the distribution result by odd and even groups
• Improved BinItem loading code (Loop using offset -> get Variant array from range)
• If there are duplicates in the Bin Item Name, a duplicate list message box is displayed and the execution is aborted.

The changed version can be downloaded from the github repository below.

https://github.com/DAToolset/1D-bin-packing

2. Details of changes

2.1 Change Item Size from Integer (Long) to Real (Double) (Change variable name prefix)

In the previous version, if a real size value such as 0.1 or 21.8 was entered, it was converted to an integer type, and the values below the decimal point were truncated, and there was a problem in that it was not correctly distributed. This was mainly a problem when the Size value was used in KB, MB, GB, TB, etc. instead of the number of bytes.

The declaration of the “Public m_lSize As Long” member variable of the CBinItem class was changed to “Public m_dSize As Double”.

2.2 BinItem name case sensitive (Changed from Collection to Dictionary)

As a member variable of the existing CBinItemCollection Class, each item was stored in a Collection and managed. When searching for an item, an item instance was found using the item name as a key, but the item key of a collection has a characteristic that is not case-sensitive.

The table name and column name extracted from the case-sensitive database were duplicated as the item key of a case-insensitive collection, so it was changed.

In case-sensitive databases, table names “T1” and “t1” can be created and used, respectively. It is not recommended because it can cause confusion, but it needs to be improved because objects that have already been created need to be identified differently.

Class was rewritten using Dictionary so that the item key is case-sensitive, and the class name was changed from “CBinItemCollection” to “CBinItemDic”.

2.3 Order Sort by Odd and Even Groups of Distribution Results

In the BinPacking result, the item size of each bin is sorted as follows.

• When “Item Size descending order” option is selected: Sort in reverse order from the largest item to the smallest item
• If the “Item Size descending order” option is not selected: Input order

Assume that the result of executing bin packing is divided into 4 bins. If you copy the Bin Item list to create a work group and execute each work group, the following phenomenon may occur.

• Execution phenomenon when bin items are sorted in reverse order of size
  • Four concurrently executed task groups execute the largest task from the beginning.
  • If the server's resource (CPU, Memory, I/O) contention increases and resources are insufficient, some tasks will fail or the waiting time will be long.
  • The resource contention is gradually resolved as the execution of large-sized jobs is completed and gradually leads to smaller-sized jobs.
• When bin items are sorted in input order
  • Server resource contention intensifies and then resolves and repeats.

This phenomenon may create problems in which the server's load becomes severe or it is difficult to predict when the execution is completed due to the inability to utilize resources efficiently.

This problem may not occur if the sum of the sizes of the concurrently executed tasks is made nearly equal, but it is almost impossible to make the bin items close to equal size because the size of the bin items is not uniform.

In order to minimize this phenomenon, the items of each bin are sorted by size, but the option of reversing the even-numbered and odd-numbered sorting order in the bin order has been added.

When this option is applied, the distribution result is as follows:

Bin1: 2, 5, 3, 1
Bin2: 3, 6, 1, 2

It is changed as follows.

Bin1: 5, 3, 2, 1 # Decending order
Bin2: 1, 2, 3, 6 # Ascending order

2.4. BinItem loading code improvement

The code that reads the input bin item list on the “Run” sheet and loads it into memory was improved by using a Varaint array.

For how to use a variant array, refer to this article.

VBA Coding Pattern: Range Loop - Read

2.5. If there are duplicates in the Bin Item Name, a duplicate list message box is displayed and the execution is aborted.

In the previous version, if there was a duplicate Bin Item Name, it was ignored and proceeded. While changing to case-sensitive in this version, it was changed to check whether there are duplicates in the input data, notify the content, and then stop the execution. You just need to remove the duplicates or change them so that they are not duplicated and run it again.

---

The Bin Packing tool is not used often, but it seems to be used 4-5 times a year or more. Sometimes it's a big help for me. If you have any questions, please leave a comment.

---

<< 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