A genetic algorithm for two-dimensional bin packing with due dates
A genetic algorithm for two-dimensional bin packing with due dates
复制标题
DOI：
10.1016/j.ijpe.2013.04.040
复制
发表时间：
2013-10
影响因子：
12
通讯作者：
J. Bennell;L. Lee;C. Potts
中科院分区：
文献类型：
--
作者：
J. Bennell;L. Lee;C. Potts
本文考虑了二维装箱问题的一种新形式，其中每个矩形都有一个交货期，每个箱子都有固定的加工时间。因此，目标不仅是最小化箱子的数量，而且要最小化矩形的最大延迟。这个问题的起因是削减库存，以及通过混合订单利用更大的需求件池可能会提高效率，同时也旨在确保一定水平的客户服务。提出了一种搜索解空间的遗传算法，该算法使用一种新的布局启发式算法来解码基因，该算法是基于为排样问题设计的最佳匹配启发式算法。遗传算法采用了一种创新的交叉算子，它考虑了每对父母中的几个不同的孩子。此外，在主目标周期性地在最大延迟和箱数之间交替的情况下，对双重目标进行分层优化。因此，该方法产生了几个具有不同权衡的非支配解决方案。还实施了两种进一步的方法。一种是基于以前的统一禁忌搜索，针对这个修订后的问题进行了适当的修改。另一种是随机下降，作为比较结果的基准。综合计算结果表明，统一禁忌搜索算法在最小化仓位方面仍有较好的效果，但遗传算法的性能略好一些。当也考虑最大延迟时，遗传算法要好得多。
This paper considers a new variant of the two-dimensional bin packing problem where each rectangle is assigned a due date and each bin has a fixed processing time. Hence the objective is not only to minimize the number of bins, but also to minimize the maximum lateness of the rectangles. This problem is motivated by the cutting of stock sheets and the potential increased efficiency that might be gained by drawing on a larger pool of demand pieces by mixing orders, while also aiming to ensure a certain level of customer service. We propose a genetic algorithm for searching the solution space, which uses a new placement heuristic for decoding the gene based on the best fit heuristic designed for the strip packing problems. The genetic algorithm employs an innovative crossover operator that considers several different children from each pair of parents. Further, the dual objective is optimized hierarchically with the primary objective periodically alternating between maximum lateness and number of bins. As a result, the approach produces several non-dominated solutions with different trade-offs. Two further approaches are implemented. One is based on a previous Unified Tabu Search, suitably modified to tackle this revised problem. The other is randomized descent and serves as a benchmark for comparing the results. Comprehensive computational results are presented, which show that the Unified Tabu Search still works well in minimizing the bins, but the genetic algorithm performs slightly better. When also considering maximum lateness, the genetic algorithm is considerably better.