使用一维装箱算法优化工作分配_3.实现（一）
三、装箱算法实现
需要开发环境来输入项目和约束列表，实现算法并检查结果。有多种开发环境，例如 Excel VBA、Python 和 R。其中，Excel VBA没有开放的库，所以大部分源代码都得自己写。 Python 和 R 可以直接实现 bin 打包算法，也可以使用已经提供的包。在这里，我将看看如何使用Excel VBA和Python中提供的包自己实现算法的工具。
3.1。基于 Excel VBA 的工具
实现算法的工具或语言通常接收数据文件作为与程序源代码分开的输入。 Excel VBA 的特点是可以将程序源代码和数据管理在一个文件中，并分别进行管理。这里，程序源代码和数据被管理在一个文件中。
下面将简要介绍通过将项目列表输入到Excel表格来管理项目列表并使用VBA实现一维装箱算法的工具的配置和源代码。整个源代码作为附录提供。 https://github.com/DAToolset/1D-bin-packing 也可以检查。
**注：本文不涉及Excel VBA的概念或语法，以后会在单独的文章中详细写。
该工具的整体配置如下图所示。在“运行”表中输入数据，设置选项，点击“运行Bin Packing”按钮查看执行结果。
上图中的四个区域的细节在下面的目录中进行了解释。
3.1.1。输入材料配置
在项目列表中，按以下格式输入名称和大小。
这里，Bin Item Name是用于识别Item的种类的名称，可以根据Item的种类适当地指定。例如：
- 如果 Item 是数据库表，则表名
- 如果项目是作业，则作业名称
- 此外，适合识别每个项目的名称（订单号等也是可能的）
请注意，项目列表中不应有重复的名称。这是因为即使大小相同，也需要知道它们是不同的对象才能确定将哪个对象填充到 bin 中。
在大小中，输入每个项目的大小。对于大小，表的情况下可以使用行数和字节数，作业的情况下可以输入分钟或秒的执行时间。所需时间应在作业执行记录中检查，但建议计算并使用最近 5 次或以上所需时间中的最大值和最小值除外的平均值。
如果您需要多个数据集，您可以复制并输入“运行”表。工作表的名称可以是任何名称，但最好以 的形式指定以将其与其他工作表区分开来。例如，它被指定为“Run_Org”，如下图所示。
Bin Packing 可以通过创建多个数据集并在每个数据集表中设置不同的数据或不同的选项来执行。显示执行结果的工作表不是为每个数据集创建的，而是永久使用的。如果要保留每个数据集的结果，可以用不同的名称保存 Excel 文件并创建单独的文件。
3.1.2。选项设置
bin 的最大大小，这是一个约束，以及是否按降序对引用列进行排序，按以下格式输入。
Max Bin Size 是分配给一个 bin 的最大尺寸。换句话说，当将多个项目填充到一个 bin 中时，它是对 Item Sizes 总和的约束。
Item Size 标准列是指定在一个 bin 项中有多个 size 值时使用哪个值的列。例如，假设它被配置为可以将多个尺寸输入到一个项目中，如下所示。
可以用作大小值的列是C到I。输入列名以选择其中的哪一列作为大小输入值。要通过在 Size 中创建随机值来进行模拟，请将公式生成的值复制到 J 列（Rando Size）中，将其粘贴为 I 列中的值（模拟），然后通过将参考列指定为 I 来执行它...不应该指定 J 列的原因是因为 J 列中使用了公式，并且每次计算时都会创建一个新值，因此无法知道哪个值用作输入值。
如果选择（选中）项目大小降序排序选项，首先，项目大小按降序排序并应用装箱算法。
3.1.3.运行箱包装
当输入数据配置和选项设置完成后，点击“Run BinPacking”按钮执行。
如果执行时“Bin Item Name”有重复，可能会出错，检查并删除重复执行。
3.1.4。检查执行结果
执行结果由 5 张纸组成。 Result summary sheet 中检查了整体摘要，该表收集了每个算法的执行结果，每个表中检查了每个算法的详细结果。
- Result Summary：一张表，其中执行每个算法的结果一目了然
- Next Fit：运行 Next Fit 算法的结果表
- First Fit：运行First Fit算法的结果表
- 最差拟合：运行最差拟合算法的结果表
- 最佳拟合：运行最佳拟合算法的结果表
结果汇总表的内容如下。
选项中设置的 Max Bin Size 的参考信息显示在顶部，运行四种算法中的每一种的结果图表显示在底部。
执行每个算法后，结果表上显示的信息组成如下。
| 物品 | 内容 |
|---|---|
| ① 结果列表 | 作为执行装箱算法的结果，您可以检查哪些物品装在哪些箱子中。这里的Bin名称是在程序处理过程中按照“Bin_”+序号（5位）的规则创建的。 |
| ② 斌总 | 这是一个数据透视表，用于以 bin 为单位计算项目大小的总和。 <④ Bin Total Chart> 是使用此数据透视表作为数据源创建的。 |
| ③ 执行信息 | 它显示处理算法所花费的时间、所有 bin 中剩余空间的总和、总空间以及空间效率低下的信息。空间低效率计算为 (Bin Total Residual Space Sum)/(Total Space Sum)。 |
| ④ 箱总图 | <② Bin 总数据透视表> 可视化为柱形图。 |
▼ Next Fit 执行结果
▼ 首次拟合运行结果
▼ 最差拟合执行结果
▼ 最佳拟合运行结果
3.1.5。 VBA代码配置
简要介绍了用VBA实现Bin Packing的源代码。 VBA项目的整体构成如下。
- Sheet（Excel UI）管理输入数据的列表，显示算法处理结果的输入输出。
- 一个模块负责处理和控制整个处理过程，创建类的实例和常用功能。
- 该类负责将输入数据加载到内存中，实现算法，输出结果数据等功能。
详细项目的目的如下。
- 床单
- 每张表：输入数据/选项设置，执行结果输出
- 模块
- modControl：管理对象化一个类，加载输入数据，实现每个装箱算法，输出结果的整个过程
- modFactory：管理类的实例化
- VBA类不能指定构造函数的输入参数，所以配置为使用工厂模式创建对象。
- modUtil：管理功能，例如记录和设置所需时间字符串的格式
- 在这里，Logging 不会留下文件，但它被配置为可以在 Windows API 中使用 OutputDebugString 在调试器上检查日志消息。
- 调试器建议使用 DebugView
- 班级
- CBin：1 类 Bin
- 主要方法：AddBinItem、IsAbleToAdd
- CBinItem: Class of 1 Item to be put in Bin
- 也就是对应于一行输入数据的一个类。
- 主要方法：CompareTo
- CBinItemCollection：管理多个 BinItem 列表的集合类。
- 主要方法：添加、排序、GetString
- CPacker：一个将 bin 列表作为 Collection 进行管理的类。
- 实现一种算法，将输入数据填充到现有 bin 列表中的适当位置或创建一个新 bin 来填充它
- 主要方法：DoPacking、Add、GetNewBin、GetBinNextFit、GetBinFirstBit、GetBinWorstFit、GetBinBestFit、PackToBin、DoOutput、GetRemainSizeSum
- CTimer：用于测量所用时间的类
- 使用 Windows API QueryPerformanceCounter、QueryPerformanceFrequency
- 主要方法：StartCounter、TimeElasped
- CBin：1 类 Bin
为了正确应用 OOP 概念，标准的做法是在类中公开由 Getter/Setter 组成的公共属性，而无需在类中公开成员变量。但是，在这个工具中，为了实现的方便，没有使用公共属性。但是，可以从外部访问的成员变量、函数和过程被声明为公共的，而要从外部访问的对象被声明为私有的。
VBA 源代码中定义的类之间的关系用 UML 类图简述如下。
上面类图中的类之间的关系是一种有关系。即在两个类之间定义的组合关系中，实心菱形（♦）是容器。
从右到左，可以看出下层与上层相连。一个输入数据由 CBinItem 类管理，而 CBinItemCollection 类将整个输入数据作为 CBinItem 的集合进行管理。 CBin 类管理各个 bin 对象，并将每个 bin 中填充的项目列表作为 CBinItemCollection 类的对象进行管理。 CPacker 类实现算法并将整个结果 Bin 对象作为 CBin 类的集合进行管理。每个类都有组合关系，所以当容器对象被移除时，所有的子对象都被移除。 CTimer 类在 CPacker 类中用于测量算法的执行时间。
在这里，CBinItemCollection 类用于管理整个输入数据，也用于管理每个 bin 中填充的项目列表。例如，假设 100 件物品装满了 10 个 bin 中的 10 件物品，则管理所有 100 件物品的对象也是 CBinItemCollection 类类型，管理每个 bin 中填充的 10 件物品的对象也是 CBinItemCollection 类类型。成为。
各个类的源码见附录，modControl这个模块控制着输入数据的加载、算法的执行、结果数据的输出全过程的伪代码如下。
Public Sub RunBinPacking()
입력자료를 읽어들여 CBinItemCollection type의 oInputItemCol 변수에 적재
입력자료의 정렬 실행을 선택했으면 oInputItemCol 내림차순 정렬
각 알고리즘의 실행결과를 담을 변수 선언
각 변수에 최대 Bin 크기와 PackingType을 설정하여 개체 생성
각 변수에 입력자료 채우기
결과출력
각 변수 메모리에서 삭제하여 정리
End Sub
在下一篇文章中，我们将查看使用 Python Bin Packing 包实现的源代码和执行结果。
<< 相关文章列表 >>
简体中文 
한국어 
English 
日本語 
Deutsch 
Español