变尺寸装箱问题的迭代/贪婪动态规划算法

姚汝林，尹石军，郭蕴华

(1.上海交通大学 船舶海洋与建筑工程学院，上海 200240; 2.招商局重工(江苏)有限公司，江苏 海门 226116；3.武汉理工大学 能源与动力工程学院，湖北 武汉 430063)

0 引言

管材切割是船舶建造过程中的一个重要的生产步骤，新近研究将船厂管材切割问题描述为一维下料问题(One-dimensional cutting stock problem，1D-CSP)[1]。但是，由于船舶建造的复杂性，某些场合零件管和原料管都具有随机长度。在此情况下，应将船舶建造的管材切割问题描述为变尺寸装箱问题(Variable-sized bin packing problem，VSBPP)，而非1D-CSP[2]。对于VSBPP问题，研究人员先后提出了近似算法[3]、分支定界算法[4]、分组遗传算法(Grouped genetic algorithm, GGA)[5]、迭代递减首次适合算法(Iterative first-fit decreasing, IFFD)[6]、迭代MBS启发式算法(Iterative minimal bin slack, IMBS)[7]、可变邻域搜索(Variable neighborhood search,VNS)方法[8]和基于动态规划的启发式方法[9]进行求解。

上述方法在优化计算花费和剩余长度等方面都取得了一些进展。但是，船舶建造的管材切割化问题是VSBPP的特殊变体，其VSBPP问题(VSBPP of pipe-cutting in ship-building，VSBPP_PS)与经典VSBPP有所不同。第一，上述大多数算法都假定箱子的长度类型是有限的，而每种类型的供应都是无限的。这些假设与船舶建造中的一些管材切割实例恰好相反。在船舶建造的实际生产情况中，经常遇到的情形是箱子(原料管)和物品(零件管)的长度是随机的。第二，很多文献都涉及基于动态规划来解决背包问题的方法。动态规划的时间复杂度为O(l·n)[10]，其中：l为箱子的长度，n为物品数。然而造船厂的切割精度为“mm”，即使对于6 m的原料管，l也等于6 000 mm。对于动态规划而言，船厂的大多数原料管都是“超长”的。更为不利的是每根原料管的长度都不同，需要对所有原料管执行动态规划进行试算。……