基于可行域的矩形智能排样系统设计

张鹏程,孙亚红,郑荣杰

(1.河北工程技术高等专科学校,河北 沧州 061001;2.献县电力局,河北 沧州 062250)

在冲压生产中,材料费用是主要的生产成本,一般能够占到总成本的 60%～80%,提高材料利用率是降低冲裁件成本的重要途径,而材料利用率的高低取决于冲裁件的排样方案。计算机优化排样[1](CAN)是计算机辅助设计与制造(CAD/CAM)技术的重要分支之一,它应用范围非常广泛。在工程应用领域中,冲裁件排样、玻璃切割、报刊排版、家具下料、服装裁剪、皮革裁剪、大规模集成电路设计中都存在大量的下料排样问题[2]。排样问题是将一系列形状各异的零件在板材中按最优方式进行排布,要求零件排放在板材内,各个零件互不重叠,并满足一定的工艺要求。

1 矩形自动排样系统的开发

1.1 功能需求

矩形排样系统的处理对象主要为待排入的矩形及变化的排样空间,其功能必须具备采集矩形相关数据及排样参数,自动完成排样操作,排样完成后能够输出最优排样方案及排样结果并能动态模拟排样过程。另外,如果用于指导工程实践,系统还应具有友好的操作界面,灵活的数据采集方式,方便进行排样流程控制;同时对于不同的排样问题,应具有很好的适应性,能够快速给出优良的排样方案。

1.2 可行域法的设计思想

在排样求解过程中,一个最基本的要求就是放入的每一个矩形不能和已经放入的矩形发生干涉,同时,也不能和排样空间发生干涉,否则排样无效。判断一个矩形放入排样空间中是否发生干涉是非常繁琐且计算量大的过程,而且随排放矩形的增多,其复杂程度会不断增加。为了避开此类复杂计算,本设计引入了矩形可行域的概念:首先确定排样空间,根据矩形排样问题的特点它可以被抽象成一个直角多边形;当排样空间确定之后,计算待排矩形在当前排样空间中的可行域,即矩形能够放入排样空间中所有有效位置的集合(也是一个直角多边形区域);最后利用定位策略选择可行域内矩形的最佳放置位置,将矩形排入并修改排样空间。重复此过程,直至再无矩形可以被放入排样空间,排样完成。

1.3 算法流程

在求解矩形排样问题时,采用可行域确定排样策略,则可避免一些启发式算法对于不同排样问题适应性及求解效率较差的缺点,使排样问题的求解变得灵活而快速。利用可行域法求解矩形排样问题可以充分利用矩形可行域所包含的有效信息,将其做为矩形在排样过程中定序和定位的基础,最终获得良好的排样方案。本系统求解矩形排样问题的算法流程如图 1所示[3]。

2 矩形排样系统的实现

2.1 系统总体结构

矩形智能排样系统的总体结构如图2所示。

2.2 系统设计

1)排样空间的描述

排样空间可以抽象为一个动态直角多边形,它随着排样过程的进行不断发生变化。本系统利用MFC中的CArray类定义数组并按顺时针方向记录排样空间的顶点序列。对于排样空间的处理主要涉及原始排样空间的描述、排样过程中排样空间的更新以及排样后期排样空间的分割、提取、调整等一系列的内容[4-5],这些功能分别由不同的函数实现。

2)可行域的计算

矩形可行域的计算[6-7]采用偏移多边形法,由函数GetFeasibleRegion()来实现。首先将排样空间多边形按矩形的宽和高的 1/2向内偏移,获得其偏移多边形;为了去掉偏移多边形的自交部分(如排样空间的某些区域矩形不能放入,偏移后必会发生自交),搜索偏移多边形的边界顶点,获得边界多边形;最后对边界多边形的顶点进行处理,即可确定矩形的可行域,具体算法及详细论述见文献[7]。

图1 可行域法求解矩形排样问题的算法流程图

3)排样策略的确定

矩形排样问题属于NP完全问题,其求解一般依赖于启发式算法。在设计时将矩形的排样过程分解为两个步骤,即定序和定位。对于定序操作,借鉴人们对排样问题传统直观的认知经验,采用按待排矩形的面积降序排列,先将面积最大的矩形放入,然后依次在剩余矩形中选择面积最大的重复上述操作,即先放大的,再放小的。对于定位操作,采用文献[8]中提出的定位函数法,根据不同的定位点对应的不同的定位函数值,结合评价函数从可行域中选择最佳的放置位置。

4)排样过程的实现

排样过程的流程如图1所示。该过程由函数Layout()实现,首先读入排样矩形数据,并按矩形的面积做降序排列,计算当前矩形在排样空间中的可行域,然后将可行域多边形的顶点带入定位函数f(x,y)计算,根据评价函数minf(xi,yi),选定矩形的合理放置位置(xi,yi)。重复上述过程,直到矩形数为0或再无矩形可以放入剩余排样空间中,排样完成。

图2 二维矩形自动排样系统总体结构图

3 排样系统的测试及应用

运行矩形智能排样系统 MyLayout Sys,打开所示参数设置对话框,以文本文件方式输入排样数据,并根据需要设定定位函数的参数。如图3所示。

以用开放的矩形排样数据集 http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/strip3.xls中的矩形数据对该系统进行测试。以T7和N7中两组矩形数据为例,矩形数量分别为197个和199个,排样空间为200×200。测试计算机配置为Intel PentiumD 925,1G内存,矩形按面积降序排入,排样子空间选取按可行域面积优先。定位函数参数采用图 3中数据,吸引子的位置选在排样空

间的四个角上。排样系统输出排样结果如图4、图 5所示。

图3 定位函数参数设计输入对话框

4 结论

以基于可行域的矩形排样问题的求解理论为依据,结合各类相关算法,利用VC++6.0作为编程工具,完成了矩形智能排样系统的设计与开发。在开发过程中,综合考虑了不同形式、不同规模的矩形排样问题的特点,以及工程实践中对于排样问题的具体要求,从而使得该系统具有简捷的实用性,广泛的适应性和较高的稳定性。对于算法及程序本身的优化,在一定程度上提高了该问题的求解效率,缩短了获得优异排样方案的运算时间。实例证明采用可行域方法求解矩形排样问题是一个非常好的思路,它使得整个求解过程变得简洁、高效且富于弹性。

[1]崔耀东.计算机排样技术及应用 [M].北京:机械工业出版社,2004.

[2]贾志欣.排样问题的研究现状及趋势 [J].计算机辅助设计与图形学学报,2004,16(7):890-897.

[3]Zhang Pengcheng,WangJinmin,Zhu Yanhua.Rectangle Packing Problems Solved by Using Feasible Region Method[C].ICADAM 2008,2008:591-600.

[4]张鹏程,郗艳梅,李国顺,等.利用可行域的矩形布局求解方法[J].现代制造工程,2010,354(3):90-93.

[5]Pengcheng Zhang,Hongxia Ren,Yanmei Xi,ect.Calculation and Optimization of Packing Space in Rectangle’s Packing Design[C].ICMS2010,2010:71-74.

[6]张鹏程,王金敏,朱艳华.凹点法求解矩形可行域研究 [J].天津工程师范学院学报,2007,(4):40-44.

[7]王金敏,张鹏程,朱艳华.矩形布局可行域的确定 [J].计算机辅助设计与图形学学报,2008,20(2):246-252.

[8]王金敏,杨维嘉.动态吸引子在布局求解中的应用[J].计算机辅助设计与图形学学报,2005,17(8):1725-1730.