论文部分内容阅读
二维矩形件排样问题和直线块排样问题广泛应用于机械加工、印刷排版、布匹裁剪、VLSI设计等领域。由于排样问题的复杂性为NP完全，以及工业生产中即使很小的材料利用率的提高也能带来显著的经济效益，因此这类问题的近似求解方案非常重要。
目前针对矩形件排样问题提出的一些有效的启发式算法，如Best-fit(BF)算法、Fastlayer-based(FH)算法，都是在布局图上的最低水平线上选取合适的矩形进行排放。为了充分利用一些较好的填充策略，本文设计的多水平线(Multi-layerHorizon，MLH)算法不仅在最低水平空间中进行矩形排放，还将其左右相邻的合适位置作为排放区域;另外，在最佳高度线下方的左右两个位置处也进行矩形填充，以增大获取到最优解的可能。同等测试条件下的实验结果表明，对于21组Hopper&Turton问题，MLH算法获得的解的质量略差于BF算法;而13组Burke问题，MLH算法却明显好于BF算法。
在研究直线块排样问题时，本文选取最基本的L/T形块作为研究对象，提出了对零件直接排放的顶点最少(VerticesLeast，VL)算法。VL算法将所有待排零件在最低水平空间上尝试排放后，选取与当前布局图重合点最多的那个零件正式排放。如果最低水平空间上不能容纳的下任何零件，则提升其高度至左右相邻空间高度的较小值。由于VL算法同样适用于矩形件排样问题，将其与BF算法以及MLH算法进行了对比。对于Hopper&Turton问题的测试结果表明，VL算法的平均排样高度略好于MLH算法，差于BF算法;而对于Burke问题，VL算法的结果比BF和MLH算法都差。另外，对于3组L/T形块排样问题，VL算法的求解结果差于结合了模拟退火算法的B*-trees算法，而与应用了回溯技术的Corner-occupyingaction(COA)算法的结果相同。
由于启发式算法在求解排样问题时的解并不理想，为了提高算法的求解精度，本文引入粒子群算法来优化求解空间，设计出了混合算法MLH+PSO和VL+PSO，并讨论了学习因子和最大速度对混合算法收敛的影响。分析得到，随着学习因子的增大和最大速度的减小，算法的收敛速度呈现先增快后减慢的趋势。在对Hoppezr&Turton和Burke问题进行实验测试后，MLH+PSO和VL+PSO算法无论是获取到最优解的实例数目还是平均排样高度，都明显好于目前比较著名的BF+SA、BF+SW和LH算法;而对于26组不可旋转的non-zero-waste问题，MLH+PSO算法的解也明显好于Leastwastedfirst(LWF)算法和ExactApproach(EA)算法。此外，对于直线块排样问题，VL+PSO算法的排样结果明显优于B*-trees算法和COA算法。通过大量实例测试和算法对比，表明了经过PSO算法优化后的MLH和VL算法都相当有效。
最后，在以上算法的研究基础上，采用VisualC++开发出了一套用于处理矩形件和L/T形块排样问题的简单系统。