基于随机搜索算法的薄膜分切管理系统

卢伟康，邹细勇，孟 灿，王国建，倪志祥

中国计量学院 光学与电子科技学院，杭州 310018

基于随机搜索算法的薄膜分切管理系统

卢伟康，邹细勇，孟 灿，王国建，倪志祥

中国计量学院 光学与电子科技学院，杭州 310018

1 引言

一维下料问题，是指原材料和所需材料维数都为一维时，在已知订单要求和原材料数据时如何进行优化切割下料，使得原材料尽量得到充分利用，成本尽量得到节约的线性规划问题[1-2]。国内外学者对一维下料问题的研究已经有一定的历史，诸如早期以Gilmore P C和Gomory R E为代表的线性规划方法（LP）[1-6]，以及之后百家争鸣的各种启发式智能算法[7-10]，都广泛地应用到解决一维下料问题中去，并取得了较大的成果。

实际生产中，诸如钢材、纸卷、管材、薄膜等原材料的排样切割都属于一维下料问题的范畴。随着工业化社会的发展，人们生产生活中对薄膜的需求量越来越大，薄膜生产行业已经进入了大规模生产营销的阶段。薄膜生产企业是典型的流程企业，具有订单数量多、产品交货期短等特点，生产过程常受到原料、设备和人力等因素的影响。不合理的薄膜下料与分切方法不仅会影响企业的生产效率，而且还会造成多项资源的浪费，增加企业的生产成本。为了降低成本，提高企业的下料生产效率，可以从以下两个方面着手：一方面是设计出合理的下料算法，减少分切余料的浪费；二是通过建立合理的产销存系统，优化排单的过程管理，缩短市场需求与生产规划之间的距离。

本文阐述了一种基于随机搜索方法的顺序启发式算法[11]，并在此算法基础上开发出了具有丰富功能的薄膜分切优化综合管理软件。

2 计算模型及算法实现

2.1 数学模型分析

一维下料是个NP问题[12]，即非确定多项式问题，其非确定性可由以下的数学模型看出。以原材料消耗总卷数最少的数学模型为例，在薄膜生产行业中，设大卷薄膜的宽度为L，一笔订单中共有m个规格的小卷薄膜，宽度分别为 l1、l2、…、lm，所对应的需求卷数分别为d1、d2、…、dm，设分切方案中共有 n种排样方式，每一种排样方式的重复使用次数分别为 x1，x2，…，xn，第i种排样方式中每个小卷薄膜使用的数量分别为ai1，ai2，…，aim，其中i表示第i种分切方案。设Z为使用的大卷数，以原材料消耗的总卷数最少为目标函数[13]，即Z尽量得小，则一维下料问题可描述为：

鉴于NP问题的复杂性及非确定性，至今无法确立一个能得到问题最优解析解的算法，因此已有的算法都旨在寻找能更接近最优解的分切算法。上述数学模型仅仅考虑了大卷薄膜消耗的总卷数尽量少的目标，而在实际的薄膜生产中，还需要考虑分切方案中排样方式更换导致的切割机器调整成本及分切剩余原料的库存积压问题。因此，实际生产中通常按优先级从高到低对以下三个目标进行生产排样的优化。首要目标是使原材料消耗最少，即薄膜原材料消耗的总卷数最少；其次，还要追求最终排样方式数少；最后，要求最后一种排样方式剩余的余料宽度较大，因为较长的余料可以回收并再次利用。基于顺序启发式算法思想，本系统通过以下几个策略来达到上述的目标。

（1）设立多个启发式规则。启发式算法往往通过设立一些参数和公式（启发式规则）作为判断条件来引导算法往设定的目标“前进”。通过启发式规则能使计算结果往想要的目标方向发展，但通常得到的是较优解。因此，本文设立了两类不同的启发式规则，一类是每生成一种排样方式时仅考虑该排样方式的最多可重复使用次数，另一类是每生成一种排样方式时同时考虑该排样方式的最多重复使用次数和该排样方式产生的余料宽度。以两类启发式规则引导算法多次重复执行，则可得到两组排样方案。再根据上述3个优化目标按优先级对其进行筛选。

（2）使用随机搜索算法获得排样方式。NP问题通常认为不可能在合理的时间范围内找到全局最优解。启发式算法适合用于来求解NP问题的原因在于其通过设立规则能快速有效地找到近似最优解。由于随机搜索算法在搜索小卷薄膜时具有随机性，使得启发式算法每执行完一次都能得到一种较优的排样方案，多次执行该算法就能得到多种不同的排样方案，再根据优化目标对其筛选，最终能获得其中最好的方案。

（3）优化伪随机性。随机运算中，在设置srand函数的种子时，如果采用默认设置好的种子，由于计算机随机运算是一种伪随机的方法，会导致每次分切排样的结果都相同，这相当于缩小了随机搜索算法的搜索空间。又由于薄膜分切的排样方案是通过重复搜索来不断优化的，而随机数发生器rand()产生的随机序列具有周期性，使算法反复迭代执行多次后无法搜寻到更优解。因此，本文在随机数运算中采用改变伪随机序列的策略，并以time变量作随机数种子，具体如下：算法每执行一定次数大循环后，重新设定时间种子为srand(time+rand())，即每执行一定次数大循环后重新更换伪随机序列，优化搜索的随机性。这种策略扩大了算法的搜索空间，有利于找到满意的排样方案。

2.2 算法描述

步骤1设立样本参数Ns和评价公式选择参数method，令method=0。

步骤2用一种随机搜索算法获得Ns种排样方式。

步骤4对上述Ns个排样方式按评价公式V1= 10n-yt进行评价，选取其中V1值最大的排样方式并保留，被选定的个体为当前排样方式。

步骤5从还未排样的小卷薄膜集合中，扣除当前排样方式中已经使用的小卷薄膜。则待排样的小卷薄膜需求量更新为：dj=dj-n×atj，j=1，2，…，m，其中假设t为当前选中的排样方式。

步骤6迭代步骤2～6直到待分切的小卷薄膜集合为空，这样就生成了一种排样方案。

步骤7重复1 000次步骤2～6，期间每执行10次后重新设置随机数种子为time+rand()，从产生的1 000个排样方案里按三个优化目标的优先级顺序优选出最好的排样方案。

步骤8令method=1，步骤4中评价公式取V2=10n，重复步骤2～7的过程。

步骤9把两种评价公式下得到的各自最好的排样方案再次按三个优化目标的优先级选出其中最好的排样方案，作为最终排样方案。

3 薄膜分切管理优化系统概述

在下料算法的基础上开发了薄膜优化分切综合管理系统，其主要包括以下三个功能模块。

（1）订单数据的查询、导入和统计。连接存放订单信息的SQL数据库，实现了对数据库中订单信息的按订单号或日期进行实时查询。可以从一个或多个订单中选取相同物理属性（薄膜型号、厚度等）的薄膜订单进行组合并导入到分切界面，同时支持临时订单导入，可以从EXECL中导入规定格式的订单数据。对数据库中的订单进行统计，是根据设定的起始日期和结束日期计算并排列出期间订单中需求量最大的几种小卷的信息，生产分切薄膜时可以把最后一种排样方式的余料分切成畅销的几种小卷薄膜。

（2）分切计算：从数据库导入订单数据后，可以对当前的待排样数据进行添加、删除、修改操作，执行分切计算并经确认后更新数据库，把订单中已经确认过分切的小卷薄膜用“1”标记，表示已分切，默认标“0”，表示未分切。

（3）分切报表打印：分切完成后生产的排样方案除了在软件界面显示外，可以导出生成word报告并打印，报告中除包含了排样方案外还包括了当前订单的小卷薄膜的各物理属性及当前订单相关的各种信息，便于企业的全过程管理。生产车间根据批准的排样方案进行大卷薄膜的生产。

4 算例分析

通过大量的数据计算实验并同相关文献进行对比，本文所述的薄膜分切综合系统在计算结果及时间效率上都有一定的改进，下面以一些相关文献中的数据为例，对本文系统进行说明和分析（各膜卷宽度单位为mm）。

算例1以一BOPP薄膜企业的一个实际订单为例，原材料大卷薄膜宽度为8 280，8种小卷薄膜宽度分别为500、520、540、560、580、600、660和 720，需求量分别为144、144、144、144、144、99和99个，求下料方案。

文献[14]中的CAD系统已经跟国内外很多文献进行过算例对比，证实了该系统算法有效性，本文采用该文献提供的系统对上述案例进行分切计算，其排样方案如表1所示。

表1 算例1CAD系统排样方案

CAD系统给出的排样方案，包括5个排样方式，使用原材料74根，最后一个排样方式的余料为540，已经是一种较好的排样方案。

本文薄膜分切综合管理系统的排样方案计算结果如表2所示，从表中可以看出，本文系统包括4个排样方式，使用原材料74根，最后一个排样方式的余料为400。在使用原材料相同的情况下，减少排样方式数可以减少调整刀具的次数，节约人力物力，若考虑调整刀具所带来的成本大于生成多余余料成本差的情况，本文提供了一种更好的选择方案。此外在同一台计算机上，CAD系统处理上述案例用时在16 s左右，而本文系统不到1 s。

表2 本文系统算例1排样方案

算例2本算例来自文献[14]，假设原材料宽度为4 000，五种坯料宽度分别为463、405、324、256和182，需求量分别为100、200、200、200和200个，求下料方案。

文献[15]中采用一种顺序启发式算法求解，排样方案包括排样方式8个，使用原材料71根。文献[7]的CAD系统给出其中一种以排样方式少为目标的排样方案，如表3所示，包括排样方式3个，使用原材料71根，最后一个排样方式的余料为740。本文系统的给出表4所示排样方案，包括排样方式3个，使用原材料71根，最后一个排样方式的余料为2 180，超过文献[7]的该数值。最后一个排样方式余料越多，可以回收利用的价值越大。此外在同一台计算机上，CAD系统处理上述案例用时在5 s左右，而本文系统不到1 s。

表3 CAD系统算例2排样方案

表4 本文系统算例2排样方案

5 结束语

本文把一维下料问题同实际生产需求相结合，提出了一维下料问题的三个分等级优化目标，即首先考虑原材料的利用率，其次考虑排样方案中排样方式数，最后考虑最后一种排样方式中余料宽度。采用了一种基于随机搜索的多启发式规则算法，通过设立多个启发式规则和优化伪随机性来增大可行解的搜索空间，最终找到当前启发式规则下的最优排样方案。

通过与其他研究文献的算例对比，验证了本文算法在计算结果及时间效率上的改进。此外，通过对比研究发现，大部分的一维下料算法在随着坯料种数的增多，即m变大时，其算法的计算时间呈几何上升，由于本文算法的随机搜索次数不会随着m的变大呈几何上升，即使处理十余种种规格的坯料，仍然能在1 s内完成计算，大大减少了计算时间。本文的分切算法同生产管理相结合，除算法分切外还有很多管理、统计功能，使企业生产、管理相结合，具有较大的应用价值。

[1]Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem[J].Operations Research，1961，9：849-859.

[2]Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem-part2[J].Operations Research，1963，1：863-888.

[3]Vnaee P H，Barnhat C，Johnson E L.Sovling binary cutting stock problems by column generation and branchand-bound[J].Comput ational Optimization and Applications，1994，3（2）：111-130.

[4]Chauny F，Loulou R，Sadones S，et al.A two-phase heuristic for the two-dimensional cutting-stock problem[J]. Journal of the Operational Research Society，1991，42（1）：264-271.

[5]Zak E J.Row and column generation technique for a multistage cutting stock pro blem[J].Computers&Operations Reasearch，2002，29（9）：1143-1156.

[6]Francois V.Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem[J]. Operations Research，2000，48（6）：915-926.

[7]Cui Yaodong，Yang Yuli.A heuristic for the one-dimensional cutting stock problem with usable leftover[J].European Journal of Operational Research，2010，204：245-250.

[8]Haessler R W.A heuristic solution to a non linear cutting stock problem[J].ManagementScience，1971，17：8793-8803. [9]Beasley J E.An exact two-dimensional non-guillotine cutting tree search procedure[J].Operations Research，1985，33（l）：49-64.

[10]Vharenkamp R.Random search in the one-dimensional cutting stock problem[J].European JournalofOperation Research，1996，95：191-200.

[11]Haessler R W.Controlling cutting pattern changes in one-dimensional trim problems[J].Operations Research，1975，23（3）：483-493.

[12]Cui Y，Zhao X，Yang Y，et al.A heuristic for the onedimensional cutting stock problem with pattern reduction[J].Proceedings of the Institution of Mechanical Engineers，Part B，Journal of Engineering Manufacture，2008，222（6）：677-685.

[13]刘睿，严玄，许道云，等.一种有效的求解一维下料问题的启发式算法[J].计算机应用，2009，29（4）：1180-1182.

[14]刘睿，严玄，陈菲，等.考虑多目标优化的一维排样系统[J].计算机应用与软件，2010，27（1）：23-25.

[15]王小东，李刚，欧宗瑛.一维下料优化的一种新算法[J].大连理工大学学报，2004，44（3）：407-411.

LU Weikang,ZOU Xiyong,MENG Can,WANG Guojian,NI Zhixiang

College of Optical and Electronic Technology,China Jiliang University,Hangzhou 310018,China

A mathematical model of the one-dimensional cutting stock problem is established for film manufacturing,and a heuristic algorithm based on the random search algorithm is put forward to cut the raw film stock.The implementation steps of the cutting algorithm are given,which has been integrated with the functions of database query,data screening, data import and report generation into a management system.The contrast experiments with the same type systems show that the computation time is shorter and layout scheme has less model number,which demonstrates that the system is effective and efficient.

random search;one-dimensional cutting;heuristic algorithm

建立了薄膜分切的一维下料数学模型，提出采用一种基于随机搜索的启发式算法进行大卷薄膜的分切。给出了分切算法的实现步骤，将其与薄膜数据库查询、筛选、导入和报表等功能集成，形成了一体化的分切综合管理系统。与其他多种一维下料系统进行算例对比，排样方案及计算时间证实了该系统的有效性。

随机搜索；一维下料；启发式算法

A

TP391.7

10.3778/j.issn.1002-8331.1301-0042

LU Weikang,ZOU Xiyong,MENG Can,et al.Film cutting management system based on random search algorithm.Computer Engineering and Applications,2014,50（23）：267-270.

国家自然科学基金（No.50905170，No.61007012）；浙江省重点科技创新团队项目（No.2010R50020）。

卢伟康（1988—），男，硕士研究生，研究领域：软件开发；邹细勇（1979—），男，副教授，研究领域：机器人导航、计算机控制、智能照明系统。E-mail：dean-1140@163.com

2013-01-07

2013-03-29

1002-8331（2014）23-0267-04

CNKI网络优先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.016.html