结合批量问题的多目标矩形件优化排样

郑明月，刘林，2，阚方，方昶

1.合肥工业大学管理学院，合肥 230009

2.过程优化与智能决策教育部重点实验室，合肥 230009

结合批量问题的多目标矩形件优化排样

郑明月1，刘林1，2，阚方1，方昶1

1.合肥工业大学管理学院，合肥 230009

2.过程优化与智能决策教育部重点实验室，合肥 230009

1 引言

批量问题[1]（lot-sizing problem）就是解决在规定时间内每一个时期的生产数量问题，目标是最优化生产中的设置成本和库存成本。下料问题[2]（cutting-stock problem）主要分为一维下料与二维下料问题，本文所研究的是二维矩形件下料问题，主要目标一般为利用率最大化。由于批量问题对于生产中的损失成本无法优化，为了更好地解决生产中的最优化问题，将最小化损失成本考虑到原批量问题中去，形成了将下料与批量结合的新问题（下文简称为L-C问题）。L-C问题多出现在家具生产、玻璃加工、铝窗框加工、包装等工业中，很多学者在这类问题上都做了研究。Hendry[3]等人在1996年就提出了一种两阶段法来解决问题，他们在第一阶段找到最优下料方式，将其作为第二阶段的已知条件从而求解，然而这种两阶段求解方法通常只能对其中一个目标的优化较为明显，并不能得到全局的近似最优解；Nonas和Thorstenson[4]解决了包括生产准备成本和库存成本的基于批量问题的一维下料问题，但其方法只适用于一维下料问题，二维问题无法采用此方法；Gramani和Franca[5]提出了一种解决结合批量问题的二维下料问题模型，为后来的学者研究L-C问题提供了研究基础，但并未提出更为有效的求解算法；Nonas和Thorstenson[6]利用列生成法解决结合批量的下料问题，其方法只能解决小规模L-C问题，并且算法的运行效率不高；Poltroniere[7]等人利用启发式算法解决造纸业中的实际生产问题，通过实例可发现，该算法的利用率较低。在研究矩形件优化排样问题中，国内众多学者通过设计不同算法来求解。崔耀东提出了利用递归算法[8-10]和分支定界法[11]来获得有效解，但只适用于小规模二维下料问题，无法解决批量问题；杨玉丽[12]等人采用三块排样方式，基于背包问题和动态规划算法有效地解决了矩形件排样问题，该算法可以得到矩形件排样的近似最优解，但同样无法解决批量问题；许继影[13]提出了一种启发式递归与遗传算法相结合的混合启发式算法，虽然可以解决较大规模的矩形件排样问题，但无法适用于L-C问题。L-C问题是结合了下料及批量问题的新型复杂问题，国外学者的研究起步较早，但总体来说，对于中大规模问题，并不能在保证算法运行时间较短的情况下获得近似最优解，国内学者对L-C问题的研究则几乎没有。

由此可见，L-C问题无论是在国外还是在国内，其理论研究都较为缺乏，而在当今经济全球化，以及原材料稀缺的社会，L-C问题必将越来越普遍，无论是从理论研究出发还是从生产实际出发，提出一种较为有效的解决L-C问题的方法是是迫切需要的。近几十年来，进化算法的应用越来越广泛，多目标进化算法成为多目标优化领域的研究热点。Deb提出了非支配排序遗传算法NSGA（Non-dominated Sorting Genetic Algorithm）将非支配排序的概念引入到多目标优化领域，然而由于其计算复杂度较高，没有精英策略等缺点，继而又提出了NSGA-II[14]算法，其良好的分布性和较快的收敛速度受到了国内外学者的关注。为了充分解决L-C问题，本文建立起多目标排样优化模型，通过启发式规则产生初始种群，并以NSGA-II为基础设计了一种快速非支配排序算法对其进行求解，并取得了较好的结果。

2 问题描述及数学模型

某加工企业有一批长L宽W的矩形板材，需要加工成长li宽wi的小矩形零件M种，每种零件的需求数量为Di，i=1,2,…,M。每一时期需要生产每种零件数量多少取决于订货商对最终产品的需求数量。为了建立数学模型以解决在每一时期如何安排生产下料，现规定T为生产时期总数，M为零件类型总数，t=1,2,…,T，i=1,2,…,M。参数和变量定义如下：

在L-C问题中，目标分别最小化原料成本和零件库存成本。原料成本属于下料中的优化目标，零件库存成本则属于批量问题中的优化目标，若分开考虑得到原料成本最小的下料方案，则零件库存成本就可能相对偏高，若只是最优化零件库存成本则又可能导致下料过程中的原材料浪费较多，因此必须将两个问题同时考虑。现假设：

上述数学模型中，式（1）为最小化所用原料的总成本；式（2）表示零件库存成本最小化；约束条件（3）表示零件i的生产数量满足其总需求量；式（4）为库存平衡约束。

3 求解L-C问题的算法

L-C问题是两种问题的结合，单一问题的求解方法对于该问题的求解就存在了很多的局限性，传统的最低水平线法以及智能算法都不能单独有效解决L-C问题。因此，通过利用相关启发式规则优化产生该问题的初始种群，再利用能够有效解决多目标优化问题的改进快速非支配排序算法进行求解，可以同时解决下料问题与批量问题，大大提高了算法的有效性，具体算法流程如下：

步骤1初始化，随机启发生成种群规模为Npop的初始种群P0，计算个体的多目标适应值，对P0进行快速非支配排序，执行进化算子，产生规模为Npop的子代种群Qg（g为进化代数）。

步骤2合并父代种群Pg与子代种群Qg为Rg，计算Rg中个体的多目标适应值。

步骤3对Rg进行快速非支配排序，确定各层Pareto最优前沿面{F1,F2,…}。

步骤4计算个体拥挤度值，比较个体的优劣，产生规模为Npop的新父代种群Pg。

步骤5执行进化算子，产生规模为Npop的新子代种群Qg。

步骤6判断是否满足终止条件，若满足，输出Pareto最优解集，结束算法；否则，返回步骤2。

3.1 编码方法

用Pj=(a1j,a2j,…,aij,…,aMj)，i=1,2,…,M，来表示第j种下料方式，其中aij表示下料方式j中含零件i的个数（aij可重复出现，总数不超过需求量）。yjt表示在t时期内下料方式j的使用次数，则在t时期内的下料方案就可以表示为：3.2初始下料方式

3.2.1 相关规则

在对下料方式进行解码排样时，常见的算法有BL算法[15]、下台阶法[16]、最低水平线法[17]、剩余矩形算法[18]等。针对本文L-C问题的特殊性，在最低水平线算法的基础上进行了改进，制定了相关规则，使得排样结果更加合理。为了方便叙述，现定义以下两个概念：

定义1最低水平线宽度MinHW，是指距离板材底边最近的那条水平线段的宽度，如图1（a）所示。

定义2最低水平线高度MinHH，是指距离板材底边最近的那条水平线段与板材底边的高度，如图1（b）所示。

图1 最低水平线宽度及高度

（1）转向规则：取β为板材的小边，β=min(L,W)，比较d1=β-a×li，d2=β-b×wi，若d1＜d2，则li∥β，否则wi∥β。

（2）排放规则：

若MinHW大于所有未排零件尺寸，则继续排样；

若MinHW等于某一未排零件尺寸，则提前排入该零件，再继续排样；

若MinHW的大小介于未排零件尺寸之间，则搜索未排零件找到使得剩余宽度最小的零件排入，直至无法排入零件为止，再提升最低水平线高度MinHH，继续排样。

3.2.2 算法步骤

步骤1（初始化）原料剩余面积=原料初始面积，将待排零件放入集合π中。

步骤2随机从π中选择一种待排零件，在不超过原

步骤5判断是否满足所有零件需求，若满足，输出下料方式，结束算法。否则，更新零件的剩余需求量后返回步骤1。料剩余面积和该零件需求量的前提下，随机生成一个整数作为该零件的排样个数，根据规则排入到原料中。

步骤3更新原料剩余面积，将面积大于原料剩余面积的零件从π中删除。判断π是否为空，若为空，转下一步；若不为空，更新π中待排零件的剩余需求量，返回步骤2。

步骤4按得到的下料方式Pj重复下料yjt次，直到该下料方式中的一个（或多个）零件满足需求，或某一零件的需求量小于其在该下料方式中的排样个数为止。

3.3 快速非支配排序算法

采用文献[12]中NSGA-II算法对种群进行排序并计算其个体拥挤度，每个个体i将得到非支配序ir和拥挤度id两个属性，采用偏序关系≺n来比较两个个体的优劣，只有当ir＜jr或者ir＝jr且id＞jd时，i≺nj，表示如果两个个体的非支配序不同，则序号低的个体（分级排序时先被分离出的个体）较优；如果两个个体的非支配序相同，则处于稀松区域的个体较优。

3.4 进化算子

为了保证种群个体的多样性，本文设计了一种进化方法，具体操作如下：

对于每一个个体随机进行位置变换操作或基因重新生成操作，由随机数0和1决定。位置变换操作就是随机选择个体中的两个基因位k1和k2(k1＜k2)，将k1前面的基因与k2后面的基因进行位置交换（包括k1,k2），得到新的个体，例如，个体P1=(a41,a81,a31,a11,a51,a21)，k1=2，k2=5，则新个体P′1=(a51,a21,a31,a11,a41,a81)。重新生成操作则是随机选择个体中的一个基因位k，并将该基因位后面的基因全部删除，还原成对应的待排零件数量，再利用上述生成算法重新生成后面的基因。

3.5 精英策略

对所有产生的子代种群，将其与父代种群合并，共同产生新一代种群，提高优化精度，以避免在进化过程中的优良个体丢失。

4 算例

为检验算法的有效性，现假设现有某加工企业需制定3周生产计划，生产的矩形件长度在100～800范围内，宽度在100～500范围内，总需求数量在100～700范围内，板材尺寸为4 100×1 500。用随机生成的方式产生矩形件的尺寸及需求数量，如表1所示。设零件平均库存成本hit=0.5，单位原料成本c=100，规定进化算法的初始种群规模Npop=2×106，进化代数为100，算法在英特尔奔腾2.4 GHz处理器上的运行时间为267 s，结果如表2和图2所示。

表1 待加工零件尺寸及数量

表2 运行结果

表3给出了本文算法与最短路径列生成算法（SCM）以及两阶段算法（LSP+CCSP）的比较结果，数据均为平均值。

表3 算法比较

实验结果表明，在中等规模矩形件排样问题中，本文算法能够在较快的时间内保证较高的利用率，同时降低总成本。

5 结束语

矩形件排样问题与批量问题相结合是实际生产中的常见问题，本文通过建立包含原材料成本和零件库存成本最小化两个目标的优化模型，设计了一种启发式进化算法来求解该NP-hard问题。该算法不仅解决了使用启发式算法利用率低的缺点，而且还能够在较短的时间内得到较优的下料方案，通过算例和其他算法的比较，证明了该算法的有效性。L-C问题在实际生产中远比本文研究的要复杂的多，实际生产中往往要考虑到加工设备的等待与维护，以及设备的加工能力和使用原料的种类，如何有效解决这类问题正是作者以后的研究方向。

图2 下料方案对应成本

[1]Lee A H I，Kang H Y，Lai C M.Solving lot-sizing problem with quantity discount and transportation cost[J].International Journal of Systems Science，2013，44（4）：760-774.

[2]Mobasher A，Ekici A.Solution approaches for the cutting stock problem with setup cost[J].Computers&Operation Research，2013，40（1）：225-235.

[3]Hendry L C，Fok K K，Shek K W.A cutting stock scheduling problem in the copper industry[J].Journal of the Operational Research，1996，47：38-47.

[4]Nonas S L，Thorstenson A.A combined cutting-stock and lot-sizingproblem[J].EuropeanJournalofOperational Research，2000，120（2）：327-342.

[5]Gramani M C N，Franca P M.The combined cutting stock and lot-sizing problem in industrial processes[J].European Journal of Operational Research，2006，174：509-521.

[6]Nonas S L，Thorstenson A.Solving a combined cutting-stock and lot-sizing problem with a column generating procedure[J]. Computers&Operations Research，2008，35：3371-3392.

[7]Poltroniere S C，Poldi K C，Toledo F M B，et al.A coupling cutting stock-lot sizing problem in the paper industry[J]. Annals of Operations Research，2008，157（1）：91-104.

[8]崔耀东，黄健民，张显全.矩形毛料无约束二维剪切排样的递归算法[J].计算机辅助设计与图形学学报，2006，18（7）：948-951.

[9]崔耀东.生成矩形毛坯最优T形排样方式的递归算法[J].计算机辅助设计与图形学学报，2006，18（1）：125-127.

[10]崔耀东，季君，曾窕俊.生成矩形毛坯最优两段排样方式的递归算法[J].南京航空航天大学学报，2006，38（1）：111-114.

[11]崔耀东，张春玲，赵谊.同尺寸矩形毛坯排样的连分数分支定界算法[J].计算机辅助设计与图形学学报，2004，16（2）：252-256.

[12]杨玉丽，崔耀东，景运革，等.生成矩形毛坯最优三块排样方式的精确算法[J].机械设计与制造，2008（9）：11-13.

[13]许继影.矩形件优化排样的混合启发式方法[J].计算机工程与应用，2012，48（13）：234-239.

[14]Deb K，Pratap A，Agrawal S，et al.A fast and elitist multi objective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[15]Edmund B，Robert H，Graham K，et al.A new bottom-left fill Heuristic algorithm for the two dimensional irregular packing problem[J].Operations Research，2006，54（3）：587-601.

[16]刘德全，滕弘飞.矩形件排样问题的遗传算法求解[J].小型微型计算机系统，1998，19（12）：20-25.

[17]贾志欣，殷国富，罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报，2002，14（5）：467-470.

[18]李满江，孟祥旭，王志强.矩形件和任意多边形排样问题的算法及应用[J].贵州工业大学学报：自然科学版，2002，31（4）：126-131.

ZHENG Mingyue1,LIU Lin1，2,KAN Fang1,FANG Chang1

1.School of Management,Hefei University of Technology,Hefei 230009,China
2.Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,Hefei 230009,China

This paper studies the multi-objective rectangle packing problem combined with lot-sizing problem by multi-objective heuristic evolutionary algorithm.Establish a multi-objective optimization model containing the raw materials cost minimization and parts inventory cost minimization.Initialize the patterns by heuristic algorithm and then use improved fast non-dominated sorting algorithm getting the cutting program.Through the results and comparison with other algorithms, this algorithm can solve small rectangle packing problem with high utilization and low total cost in a fast time.

rectangle packing;lot-sizing;multi-objective optimization;heuristic;evolutionary algorithm

设计多目标启发式进化算法，研究了一种考虑批量问题的二维矩形件排样问题，建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。先用启发式算法初始化下料方式，再用改进的快速非支配排序算法进行优化求解，确定下料方案。通过实验结果以及与其他算法的对比表明，在中等规模的矩形件排样问题中，该算法能够在较快的时间内既保证较高的原料利用率，又能降低该问题的总成本，证明了该算法的有效性。

矩形件排样；批量问题；多目标优化；启发式；进化算法

A

TP391

10.3778/j.issn.1002-8331.1212-0338

ZHENG Mingyue,LIU Lin,KAN Fang,et al.Multi-objective rectangle packing problem combined with lot-sizing problem.Computer Engineering and Applications,2014,50（22）：260-264.

国家自然科学基金重点基金（No.71231004）；国家自然科学基金（No.71171071）；安徽省高校省级自然科学研究项目（重点）（No.KJ2011A215）。

郑明月（1988—），女，硕士生，研究领域为多目标优化下料问题；刘林（1964—），男，博士，副教授，研究方向为生产运作管理、优化与决策、管理信息系统；阚方（1989—），女，硕士生，研究方向多目标优化下料、决策科学与技术；方昶（1986—），男，博士生，研究方向为优化调度、多目标优化下料。E-mail：mingyue1020@126.com

2012-12-28

2013-04-17

1002-8331（2014）22-0260-05

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