多品种分批量冲压车间的耦合选择NSGA−II调度优化

韩冰冰，王 双，葛 杨，王 颖

（1.许昌职业技术学院机电与汽车工程学院，河南许昌 461000；2.郑州大学机械学院，河南郑州 450001；3.贵州商学院，贵州贵阳 550014）

1 引言

随着客户对产品的个性化和多样化需求，产品种类日益增多，产品的生命周期日益减短。对于制造企业讲，生产模式由连续大规模生产转化为小批量、多种类生产。生产模式的转变使得生产调度与控制更加复杂，而优越的生产调度模式可以缩短生产周期、提高生产效率、降低生产成本[1]，因此研究冲压车间的生产调度问题具有重要意义。

冲压车间生产调度是指把车间有限的生产资源和运输资源在时间上分配给若干生产任务，在满足生产约束的前提下达到减少生产成本、缩短生产周期等目的[2]。根据优化目标的不同，可以将冲压车间调度优化问题划分为生产成本最优化、生产周期最优化、换模次数最优化、多目标优化等[3]。

从优化方法角度划分，冲压车间调度优化方法可以划分为最优化与启发式优化两大类。最优化方法包括枚举法、数学规划法[4]、拉氏松弛法[5]等，此类方法可以得到冲压车间的最优调度方案，但是只适用于小规模的调度优化问题，对于大规模调度问题其计算量过大以至于无法求解。启发式优化是指通过问题建模，将冲压车间调度问题转化为最优解搜索问题，常用的启发式优化算法包括粒子群算法、遗传算法等，此类方法优点是适用于大规模的车间调度优化问题，缺点是调度方案的优劣取决于启发式算法的搜索性能。文献[6]提出了改进帝国主义竞争算法，用于求解车间调度优化问题，实现了最大完工时间的最小化。文献[7]针对考虑序列依赖设置时间的冲压车间调度优化问题，将遗传算法与智能搜索算法相结合，给出了基于混合算法的优化求解方法。文献[8]结合冲压成产的能耗特性曲线，建立了完工时间最小、能耗最低的多目标模型，使用多层编码遗传算法对模型进行了求解，在减少完工时间的同时降低了生产能耗。文献[9]对于柔性作业车间调度问题，以机器总负荷、完工时间等为优化目标，将和声搜索算法引入到多目标遗传算法中并对优化模型求解，得到了有效、可行的调度方案。当前针对冲压调度优化的研究存在以下几个问题：（1）大多针对传统少品种大批量生产进行研究，不能满足当前多品种少批量的个性化产品生产需要；（2）计算车间成本没有考虑运输成本和换模成本等。

这里针对多品种分批生产的冲压车间调度问题，建立了冲压车间调度的优化目标模型和约束条件模型，在NSGA−II算法中引入了耦合选择策略，从而给出了耦合选择NSGA−II算法的优化方法，经过优化减少了冲压车间的完工时间、加工成本和换模次数。

2 冲压车间调度模型

2.1 问题描述

多种类分批量的离散型冲压车间车间调度示意，如图1所示。

图1 车间调度示意图Fig.1 Schematic Diagram of Workshop Scheduling

冲压车间中有N种分批量的待加工工件，记为J1，J2，…，JN。每个工件具有若干道加工工序，工件Ji的第k道工序记为Oik。对同一工件来说，其工序的加工顺序是预先确定的，且每道加工工序只有一套模具可用，这意味着不同批次的同一工件同一工序不能在时间上出现重叠。每套模具可以在不同冲压机上进行加工。接下来对冲压车间调度的已知条件、前提假设、优化目标进行明确。

已知条件：（1）工件类型、加工批量及数量；（2）每套模具可使用的机床集合；（3）每道工序在不同机床的加工时间、成本、换模时间等；（4）工件在机床间的运输成本。

前提假设：（1）工件使用等量分批原则；（2）同一工件的工序已预先确定，不同工件间无加工优先级；（3）同一批量的工件开始加工后不再间断。

优化目标：通过为每套模具分配机床，并确定各工件各批次的加工时序，实现所有工件的完工时间最短、换模次数最少、加工成本最少等目标。

2.2 问题建模

如前所述，这里以所有工件的最大完工时间最短、换模次数最少和车间能耗最低为优化目标。

（1）最大完工时间模型。最大完工时间是指在一个生产周期内，从第一个工件加工开始，到最后一个工件完工为止所消耗的时间。其数学描述为：

（2）换模次数模型。此处的换模次数是指一个生产周期内在所有机床上的换模次数总和，所有机床在0时刻的装模设置为一次换模，则换模次数计算方法为：

（3）加工成本模型。冲压车间的成本包括换模成本、冲压成本和运输成本，即：

根据生产实际，设置以下3个约束条件：

（1）同批次工件的同一工序只能在同一机床上加工，使用数学描述为：

（2）同一时刻某机床只能加工一道工序，即：

（3）任一批次工件的加工开始时间需大于上一批次工件的完工时间与换模时间之和，即：

综合以上建模过程，得到冲压车间调度模型为：

3 基于耦合选择NSGA−II的调度优化

3.1 传统NSGA-II算法

NSGA−II算法是在遗传算法基础上加入非支配排序策略，使其适用于多目标优化问题[10]，其关键步骤包括染色体编码、遗传操作、解码等。

（1）染色体编码。染色体编码方式是实际问题与算法的结合点，每条染色体表示一个可行解。这里针对冲压车间调度问题，采用4基因链缠绕方式得到染色体，其中2基因链为自由变量，另外2基因链为非自由变量，不具备优化意义，其设置只是为了便于解码。以3个工件的4批次加工为例进行说明，加工任务，如表1所示。

表1 冲压加工任务Tab.1 Stamping Task

染色体长度与工序总数一致，对于图1中的加工任务，工件J1有2个加工批次，因此工序长度为6，工件J2、J3均有1个加工批次，工序长度分别为2、3，因此染色体长度为11。对于3工件4批次加工任务，染色体使用十进制编码，4基因链包括工序编码、机床编码、加工时间编码和加工成本编码，如图2所示。

图2 染色体编码方式Fig.2 Chromosome Coding Mode

图2中工序编码和机床编码为自由变量，可进行优化，加工时间、加工成本为非自由变量，根据工序和机床共同确定。工序编码解释为：编码1表示工件J1的第一批次，编码2表示工件J1的第二批次，编码3表示工件J2的加工批次，编码4表示工件J3的加工批次。

在工序编码中，1出现了3次，分别表示第一批次工件J1的工序O11、O12、O13，工序中其余编码与此含义一致。以第一基因位为例对4条基因链进行释义：工件2的第1工序在机床3上加工，加工时间为12s，加工成本为37元/h。

（2）染色体初始化。染色体以随机方式进行初始化，随机包括工序编码随机和机床编码随机。

实现方法为：首先生成一组可行的工序编码，随机生成对应的可用机床；将工序编码进行打乱并随机排序，而后随机生成对应的可用机床，重复以上过程，直至获得设定规模的染色体。

（3）染色体交叉。染色体交叉包括工序交叉和机床交叉2种方式，这里以随机方式选择一种交叉方式执行。工序交叉为将父代1和父代2的工序进行交叉，相应的机床保持不变，如图3所示。

图3中将编码2作为固定位，其余编码按照顺序依次交叉。由于染色体工序编码和机床编码位自由变量，因此只给出了工序编码和机床编码。

图3 工序交叉Fig.3 Procedure Crossover

机床交叉方法为：首先产生｛1，2，3，4｝的真子集，根据子集中的编码将相应的机床进行交叉。假如某次产生的子集为{4}，则机床交叉，如图4所示。

图4 机床交叉Fig.4 Machine Crossover

（4）染色体变异。以图2的编码为例对染色体变异方法进行介绍，从11 个基因位中产生两个随机数n1，n2∈[]1，11，且n1n2。将n1和n2对应的工序进行两点变异，得到中间子代。

为了防止出现非法解，需要检查中间子代的工序顺序，当交叉引起工序顺序变化时，将其机床按原编码顺序进行调整，从而得到合法的子代，以上过程，如图5所示。

图5 两点变异Fig.5 Two Points Mutation

在图5中将第4基因位和第8基因位的工序码交换，交换后发现编码“4”的工序顺序未变化，而编码“2”的工序顺序发生了变化。因此将父代中编码“2”对应的机床“3、1、4”依次填入到工序码“2”对应位置，得到子代。

（5）选择策略。传统NSGA−II 算法依据非支配排序和拥挤度进行选择，非支配排序方法和拥挤度计算方法可参考文献[11]，这里不再赘述。

传统NSGA−II 算法首先依据非支配层进行染色体筛选，而后依据拥挤度进行选择，使染色体规模保持恒定[12]。

（6）染色体解码。根据算法得到的优化解，对其解码得到冲压车间成产的甘特图，以图2所示的染色体编码为例，将换模时间全部设置为30min，其对应的机床甘特图，如图6所示。

图6 图1对应的甘特图Fig.6 Gantt Chart of Figure 1

（7）算法结束。当算法迭代次数达到最大次数时，算法结束，输出全局最优解。

3.2 耦合选择NSGA-II算法

分析传统NSGA−II 算法染色体选择方法可知，染色体选择首先依据非支配排序，而后依据拥挤度选择染色体，这种方法意味着拥挤度只能作用于最后一个非支配层，不利于染色体整体的多样性。

针对这一问题，这里提出了染色体的二元耦合选择方法，其核心思想为：根据非支配层排序，自适应确定每层需删除的染色体数量，而后根据拥挤度从每个支配层中删除拥挤度值小的染色体。

非支配层数量记为M，非支配层编号记为m，遗传操作后染色体超出设定规模的数量记为Qd，则支配层m需舍弃的染色体数量为：

分析式（8）可知，本节提出的耦合选择方法使拥挤度作用于每个非支配层，可以更有效提高染色体多样性和算法优化能力，以从2个支配层的20个染色体中选择14个为例，耦合选择策略与传统选择策略的对比效果，如图7所示。

图7 两点变异Fig.7 Two Points Mutation

在图7中，按照传统选择策略在第2非支配层中删除6个染色体。

按照耦合选择策略，依据式（8）在第1非支配层删除2个染色体，第2非支配层中删除4个染色体。从结果可直观看出，耦合选择方法的染色体分布均匀性（也即多样性）更好。

3.3 基于耦合选择NSGA-II算法的求解流程

根据以上对耦合NSGA−II 算法的描述，制定基于耦合选择NSGA−II算法的冲压车间优化流程，如图8所示。

图8 优化流程Fig.8 Flow of Optimization

4 实验验证及分析

4.1 实验设置

以某汽车生产的冲压车间调度优化为例进行验证，在某一生产周期内该车间需生产4种工件，每种工件均生产2批，可用的机床为6台，各工件的工序、可用机床、生产时间、生产时间及相应的模具，如表2所示。另外，将换模时间统一设置为30min，换模一次的成本为20元。

表2 冲压任务及条件Tab.2 Stamping Task and its Condition

表中：“—”表示此机床无法加工此工序；“8/46”—机床M1加工工序O11的单件时间为8s，单价加工成本为46元/h，其余数据与此数据含义一致。

各机床之间的运输成本，如表3所示。

表3 机床间的运输成本（元）Tab.3 Transportation Cost Among Machines（yuan）

4.2 耦合选择NSGA-II与传统NSGA-II对比分析

耦合选择NSGA−II算法的参数设置为：染色体规模为200，迭代次数为100，交叉概率为0.45，变异概率为0.05。使用耦合选择NSGA−II算法得到的Pareto解集，如图9所示。

图9 Pareto解集Fig.9 Pareto Solutions

按照相同的参数设置，使用传统NSGA−II 算法同样可以获得一组Pareto解集，将耦合选择NSGA−II算法与传统NSGA−II算法得到的Pareto解集分别统计，结果，如表4所示。

表4 两种NSGA-II算法的搜索结果Tab.4 Searching Result of Two NSGA-II Algorithms

由表4 中的统计数据可以看出，耦合选择NSGA−II 算法的Pareto解集中解的质量高于传统NSGA−II算法，耦合选择NSGA−II算法得到的3个目标参数最大值、最小值和均值全部小于传统NSGA−II算法，这是因为传统NSGA−II算法的选择机制没有考虑到染色体多样性问题，而耦合选择NSGA−II算法的选择机制交替使用支配层和拥挤度作为参考，兼顾了染色体多样性和优劣性，因此耦合选择NSGA−II 算法Pareto 解集质量高于传统NSGA−II算法。

4.3 耦合选择NSGA-II优化方案与当前方案对比

使用线性加权法从耦合选择NSGA−II算法优化的Pareto解集中选择一个最优解，分为3 步实现，分别为消除量纲、确定权重、计算综合评价。

（1）消除量纲

各目标参数的量纲不同，难以进行有效的比较，因此首先需要消除量纲。对于M个目标参数，每个目标有N个解，则参数序列{dmn}采用极差法消除参数量纲，为：

式中：emn—目标参数m的第n个解消除量纲后的值；dmn—目标参数m的第n个解消除量纲前的值；dmmax—目标参数m的最大值；dmmin—目标参数m的最小值。

（2）确定权重

这里将3 个目标参数设置为相同权重，即w1=0.33、w2=0.33、w3=0.34。

（3）计算综合评价

根据各参数权重和去量纲后的参数值，计算第n个解的综合评价为：

式中：Sn—第n个解的综合评价值。根据这里的优化目标，Sn取得最小值对应的解即为最优解。

按照以上步骤，从Pareto解集中获得最优解，染色体解码后得到机床甘特图，如图10所示。

图10 优化后的机床甘特图Fig.10 Machine Gant Chart After Optimization

冲压车间当前的冲压方案根据批次顺序确定的，即按照工件顺序加工完一批后再加工第二批，机床甘特图，如图11所示。

图11 优化前的机床甘特图Fig.11 Machine Gant Chart Before Optimization

统计优化前后冲压车间的换模次数、加工成本和最大完工时间，对比结果，如图12所示。优化前换模次数为23次，加工成本为2050元，最大完工时间为15.86h。优化后换模次数为11次，加工成本为1672元，最大完工时间为9.52h，比优化前分别减少了52.2%、18.4%、40.0%。以上结果说明耦合选择NSGA−II算法可以对冲压车间调度进行有效优化，减少了加工时间、加工成本和换模次数。

图12 优化结果对比Fig.12 Comparison of Optimization Result

5 结论

这里研究了多品种分批生产的冲压车间调度优化问题，建立了冲压调度优化模型，提出了耦合选择NSGA−II 算法的优化方法，经验证得出以下结论：（1）与传统NSGA−II算法比，耦合选择NSGA−II 算法的选择策略能够兼顾染色体的多样性和优越性，其Pareto解集质量高于传统NSGA−II算法；（2）与当前冲压方案比，优化后的冲压调度方案有效减少了完工时间、加工成本和换模次数。