一维仓装问题的一种新的基于图的算法

Debajit Sensarma^{* 1}，萨马森萨尔玛^{* 2}

加尔各答大学计算机科学与工程系，印度西孟加拉邦加尔各答
加尔各答大学计算机科学与工程系，印度西孟加拉邦加尔各答

摘要

装箱问题(BPP)是最著名的组合优化问题之一。该问题的主要目标是尽量减少使用的箱子数量，并在有限数量的箱子中有效地包装不同大小的物品。提出了一种求解一维仓装问题的新的基于图的算法。最后，用基准实例对该算法进行了实现和测试，并与现有的FFD算法在垃圾箱数量和垃圾空间方面进行了比较。在大多数情况下，新算法产生近似最优解，性能优于FFD。

关键字

图，箱子装箱问题，组合优化，启发式

介绍

在一维的装箱问题中，给出了一个物品序列L = (a1, a2，…，an)，每个物品的大小为S(ai)， i=1，..，n and the goal is to pack them into minimum number of bins with pre specified capacity C (i.e. partition them into a minimum number m of subsets B1, B2, …, Bm such that

从约束满足问题的角度来看，箱子装箱问题是在和约束下对集合L进行划分的问题，即将L划分为最小数量的块，称为箱子，使得每个箱子中物品的大小之和最多为给定容量C>0。装箱问题在现实世界中有各种各样的应用，如库存削减问题，电视节目编制问题，计算机存储分配问题，运输问题。在许多问题中，装箱问题被表现为主要的组合优化问题、次要问题或嵌入的特殊情况。例如，在集装箱装载问题中，装箱是嵌入的。

箱子包装可以用几种方式来定义。一种分类是基于它们的维度。有一维、二维、三维和多维的箱子包装。另一方面，问题有两种类型的包装，固定大小的仓包装问题和可变大小的仓包装问题。在固定大小的情况下，仓容量是固定的，不能有不同的容量。目标是:

i)尽量减少不超过其容量的箱子数量。

ii)尽量减少浪费空间。

iii)尽量缩短执行时间。

在可变大小的包装问题的情况下，箱子的容量变化。目标是在上述约束条件下打包物品，并将所选箱子的成本降至最低。

全文组织结构如下。第2节给出了问题的公式。第3节描述了现有的装箱问题算法。第四节介绍了所提出的算法。实验结果在第5节和第6节中给出。

2.问题公式化

给定“B”个容量为“C”的相同的箱子和一个包含n个大小为a1, a2，…的物品的列表，以及一个要打包的兼容图G (V, E)，其中V是物品大小的集合，E是边的集合，如果物品i和j兼容(即S (i) + S (j) V)，则(i, j) E。问题是将物品分配到箱子，使用最小数量的箱子，同时确保分配到一个bin的项目的总大小不超过bin容量C，并且两个兼容的项目分配到同一个bin。假设数字B足够大，以保证可行性;更准确地说，它是最优解中箱子数量的有效上限(注意B n)。该问题可能的整数规划公式为:

其中，如果使用bin k，则k y =1，否则为0;如果将i项放入bin k，则ik x =1，否则为0。

在约束条件(i)中，目标函数是使箱子总数最小化，并将所有容量相同的物品打包。约束(ii)保证填充在bin k中的项目(i a)的大小不超过bin容量。约束(iii)确保每个项目只放在一个bin中。约束(iv)制定相容性。

3.装箱算法

装箱是一个NP-Hard问题[1,2]。许多启发式和近似算法被提出来达到近似最优解。算法主要有在线和离线两种。

在线算法按照它们到达的顺序永久地将对象分配到一个箱子中。所有的在线启发式都有一个初始条件，即第一个对象已经被装箱。有各种在线算法。其中一些是:

A.下一次适合启发式。

在这个算法中，项目是按照它们到达的顺序排列的。任务是将下一项放置到当前bin中，如果它合适，则关闭该bin并启动一个新的bin。

B.第一适合启发式。

在这个算法中，项目是按照它们到达的顺序排列的。一旦物品到达，算法就会将物品放入编号最低的箱子中。如果项目不适合任何打开的bin，启动一个新的bin。

C.最佳拟合启发式。

该算法将项目按照它们到达的顺序排列。将下一件物品放入该箱子，以便在物品放入箱子后留下最小的剩余容量。如果项目不适合在任何bin，启动一个新的bin。

D.最差适合启发式。

该算法将项目按照它们到达的顺序放置，并将下一个项目放入该容器，该容器将在项目放入容器后留下最大的剩余容量。如果它不适合任何bin，启动一个新的bin。

离线算法在打包开始之前就拥有所有可用的对象。下面介绍两种著名的离线算法:

E.第一拟合递减启发式。

该算法首先对项目进行降序排序，然后将下一个项目放入它适合的最低编号的bin中。如果它不适合任何打开的bin，则启动一个新的bin。

F.最佳拟合递减启发式。

该算法首先对项目进行降序排序，并将下一个项目放入该容器，该容器将在项目放入容器后留下最小的剩余容量。如果它不适合任何bin，启动一个新的bin。

除了发展经典问题[4]的逼近算法外，该问题还存在一些变体。(a)物品数量最大化的箱子包装问题。[5] (b)箱子包装问题，每个箱子里可以装的物品数量是有限制的。[6] (c)类约束仓装箱问题。[8] (d)动态装箱问题。[7] (e)数据受限的Bin打包。[9,10] (f) Bin拉伸问题。[11]

4.算法

本文提出的算法是基于图[3]的。它是针对离线一维仓装问题而设计的。该算法是两个算法的集合。(a)算法B: Bin Counting和(B)算法C:构造兼容性图。算法C根据输入项的给定大小集创建兼容性图，算法B计算所需的箱子数量。每个仓的废物空间计算为仓的总容量与所选项目集的大小之和之差。该算法在合理的时间和空间内找到最小数量的箱子。下面描述了这两种算法。

5.实验结果

该程序是在英特尔®Atom™处理器，1.60 GHz, 1.0 GB DDR2 RAM和Borland c++ 5.5编译器上完成的。本节对FFD算法和本文算法的结果分别从i)箱数(Number of bins) ii)废物(Waste)两个方面进行评价

这里j y为bin j中物品的大小之和，C=每个bin的容量。测试实例取自or库[12]。基准数据集分为三类;简单类、中等类和硬类实例。表i包含简单实例的结果。在5个实例中，提出的算法对所有实例都产生了最优解，而FFD只对3个实例产生了最优解。表ii包含了中型类实例的结果。在5个实例中，提出的算法为4个实例生成最优解，为1个实例生成近最优解，而FFD仅为1个实例生成最优解。最后，Hard类实例的结果如表iii所示，所提出的算法在5个实例中对所有5个实例都产生了近似最优解，优于FFD。从以上三个表可以看出，本文算法的Waste Space(%)相对于FFD要小一些。 Here, N represents number of items, C represents bin capacity. We have chosen q= 2, 3, 4, 5.

6.结论

本文提出了一种求解一维装箱问题的启发式方法。该算法是一种基于图的离线算法。一个兼容性图是由一组项目大小构建的，其中项目大小作为图的节点，如果它们与容量约束兼容，则连接两个节点。在一些问题实例上的实验表明，该算法在垃圾箱数量和总浪费空间方面优于现有的离线FFD算法。

在未来，我们将在其他实例中试验所提出的算法，并将尝试将该算法应用于现实生活中的问题解决。

鸣谢

作者要感谢印度西孟加拉邦的加尔各答大学，新德里的科学与技术部(DST)的财政支持，以及审稿人的建设性和有益的意见，特别是没有计算机就不可能完成工作。

参考文献

加里，迈克尔·R·和大卫·s·约翰逊。“电脑和顽固性。”卷29。Wh freeman, 2002。
Basu, s.k . <算法的设计方法与分析>。PHI学习有限公司，2013。
托,Narsingh。图论在工程和计算机科学中的应用PHI学习有限公司，2004年。
Gonzalez, Teofilo F.编著，《近似算法和元启发式手册》。CRC出版社，2007年。
小科夫曼，爱德华。G.， JY-T。梁德伟和丁德伟。“箱子包装:使包装的件数最大化。”ActaInformatica 9.3(1978): 263-271。
克劳斯，K. L.， V. Y.沈，赫伯特D.施韦特曼。多程序设计计算机系统模型中几种任务调度算法的分析。ACM杂志(JACM) 22.4(1975): 522-550。
小Coffman, Edward G.， Michael R. Garey和David S. Johnson。“动态装箱。”SIAM计算杂志12.2(1983):227-258。
沙克奈，哈达斯和塔米·塔米尔。“在线类别限制包装的严格限制。”理论计算机科学321.1(2004):103-123。
刘伟平，杰弗里·b·西德尼。“用半序数数据进行装箱。”运筹学通讯19.3(1996):101-104。
曼达尔，C. A.， P. P.查克拉巴蒂，和S. Ghose。“易碎物品装箱的复杂性及其应用”计算机与数学及其应用35.11(1998):91-97。
阿扎尔，约西和奥德·雷格夫。“在线bin-stretching。”理论计算机科学268.1(2001):17-41。
http://www.wiwi.uni-jena.de/entscheidung/binpp/