王石

摘要

分析制造业排样问题可以分解为布局问题和组合优化二类问题，矩形布局问题通过“一刀切”剪切布局算法求解并实施自动化制造过程，组合优化问题通过极限算法和规划算法进行求解。介绍典型计算机辅助切割排样系统AutoCUT/AutoSAW在智能制造系统中的应用。

【关键词】排样 矩形布局 组合优化

1排样问题

排样问题也普遍被称为开料问题，也有的行业称之为“排版”、“下料”等，本文中出现的“开料”即与排样属于同一概念。广义的排样问题除了指工件在板料中的优化布局外，还应考虑各布局的下料数量，即各布局的组合优化，因此也称下料规划问题。由此，制造业中常见的矩形排样问题可以分为如图1所示的2个子问题：

（1）矩形布局问题。

（2）组合优化问题。

2矩形件排样优化

2.1矩形布局排样

切割布局问题也称为“Cutting问题”，是指在板料中优化布局不同尺寸切割零件。切割布局算法通常提取板材的特征和零件的特征，进行组合优化排布，从而产生若干零件组块集合，切割加工时先将整料切割成零件组块，然后再切割出零件。“一刀切”加工广泛适合于家具、建材、玻璃等行业，其工艺特点是每次切割都将材料一分为二，得到零件组块，对于不规则零件则再将组块进行冲压得到最终形状，如此直到所有零件切割完成。

剪切布局主要适用于锯切方式，常采用开料锯等设备。由于锯切一分为二的工艺特点，需要尽量采用平行走刀剪切方式，即每一步都尽可能的平行切割多次，有效减少切割方向转换。家具板材优先使用电子裁板锯，每次锯切都产生一个矩形工件，因此尽量采用平行线的切割工艺能够减少换板次数，从而降低加工时间和提高设备切割效率。图2解释了适用于锯切方式下的平行剪切方法，根据加工复杂度，可以设定不同搜索层次生成布局图形，一层剪切连续切割一组即可得到最终零件，二层剪切则在一组切割完成后，转换半成品方向，再进行一次切割，從而分两步切割出最终毛坯，而三层切割则可能部分零件需要进行三次转向才能切割完成，依次类推。

2.2排样布局的组合

实际生产中往往不止是一个切割布局图，而通常是一批订单需求分解得到的批量切割任务，因此需要考虑多个开料布局和需求数量的优化组合，使得组合后的排样图集合既能满足数量需求，同时有能达到较好的全局利用率，我们将此类问题归结为一个组合优化问题，组合优化的下层则是布局优化问题。组合算法可分为极限求解和规划求解两种方式，极限算法是基于通常的贪心策略，组合优化的效果一般，而规划算法则应用于大批量下料以及寻求最高全局利用率的场合，它通过数学方法计算最优解，其优化效果高于极限算法，但可能出现无解情况而导致计算失败。

目前研究的布局组合算法是一种基于线性整数规划方法的优化算法。其基本思想是先产生足够多的排样布局图数，然后列出多目标优化方程组，通过单纯形法等算法来选取最优排样布局的组合。本算法能够得出问题的全局最优解，即全局最优排样方案。

布局组合优化的模型如下：

Obj： min（clxl+c2x2+"'+cnxn）

St. ailxl+ai2x2+"'+ainxn≥di

xi>0 1=1，2，…，n整数

式中：n为切割方式;ci为第i=l，2，…，n的费用;Xi为第i=l，2，…，n;aij为第j种切割方式下第i种零件的数量，是整数。

该模型只适用于一维（线材）排样问题的求解，即时是一维排样问题，在零件数量（m）不是很大时，只要零件的长度相对与原料长度足够短，则模型需要处理数百万中切割方式。具体算法实现时可以采用一些简化搜索策略，减少计算量获得近优解。

3计算机辅助切割排样系统及其在智能制造中的应用

“AutoCUT开料专家”是专门针对工程下料排样而设计的排样优化系统，能够有效解决合理下料问题，高效完成零部件规划下料和优化排样布局，目前主要应用到定制家具、五金建材等行业，占有国内超过50%的市场份额。“AutoSAW智能锯”则在AutoCUT求解切割优化问题的基础上，主要针对电子开料锯进行嵌入式设计的设备智能化软件，它能够对基于PLC控制的电子开料锯进行智能化升级，将生成的优化排样方案直接控制电子锯，自动化完成优化和切割全过程，最大幅度的节约人工、加快生产周期、提高材料利用率，本软件目前装备了国内绝大部分电子锯设备，是当前主流的锯切装备智能优化软件。

AutoCUT/AutoSAW在工业智能制造中有着广泛的应用前景。在定制家具智能制造系统中，智能优化下料位于企业资源计划（ERP）、订单与设计系统（CAD）与设备制造系统（CAM）之间，与企业生产定制系统的数据管理（PDM）密切联系，同时是驱动企业后续生产过程的第一道自动化工序。AutoCUT向上承接ERP/CAD系统的产品数据，向下提供拆解优化后的切割方式输出，驱动自动化设备完成下料和切割毛坯，这为实施企业制造执行系统（MES）提供支撑。