基于改进遗传算法的辐照膜订单排产研究*

王嘉乐，郑飂默

(1.中国科学院大学，北京 100039；2.中国科学院沈阳计算技术研究所 高档数控国家工程研究中心， 沈阳 110168；3.沈阳高精数控技术有限公司，沈阳 110168)

0 引言

在全球能源转型的浪潮下，新能源作为油气燃料的替代品，它的发展一直是世界关注的焦点，各种新材料不断被提出。其中新能源汽车作为新能源应用的典型代表，产销规模急剧扩大，电池作为新能源汽车的核心部件，仅2018上半年，锂电池隔膜的总生产量就达到了7.6亿平方米[1-2]。巨大的市场需求使得电池隔膜的研究生产成为了国内外研究的热点。

目前，业界普遍使用智能优化算法来解决企业计划生产编制问题，这些算法在处理计划排产中出现的组合爆炸等问题都有着不俗的表现，常见的有遗传算法[3]，蚁群算法[4]，模拟退火算法[5]，粒子群算法[6]，禁忌搜索算法[7]等。其中遗传算法较其他算法编码解码方式多样，遗传操作简单，能够在全部解空间并行计算，对目标函数设置以及搜索解空间没有特定限制，算法适应面广的特点而有着更为广泛的使用。

辐照膜是一种新型微孔薄膜，辐照膜利用重离子加速器产生的离子束对薄膜进行辐照，当离子穿过薄膜后留下的轨迹自动就形成了微孔。在锂离子电池材料的结构中起到避免正负电极直接接触同时又导通离子的作用[8]。目前国际上按照隔膜微孔的成孔机理不同主要分为干法，湿法和辐照这三种方法。其中干法和湿法是两种工业上使用的成熟稳定的生产方法，辐照是一种新型的电池隔膜生产工艺[9]。

相较于干法和湿法利用物理外力对薄膜进行拉伸形成微孔，辐照微孔质量更佳。但是由于整个加速器系统构造复杂[10]，对现场温湿度要求苛刻，这就使得辐照生产不同型号的薄膜时不能仅仅通过修改拉伸力来实现生产型号的更改，操作难度高，并且频繁的切换型号不仅会造成生产时间的浪费也会严重影响重离子加速器的使用寿命[11]。相较传统薄膜生产过程，辐照膜更加注重薄膜的连续生产，相同型号的订单应尽量集中生产，原本适用于传统薄膜生产的交付日优先的排产方式[12]将导致频繁的设备切换，大量的参数重置会造成辐照膜生产时间的浪费，已经不能够满足辐照膜生产的要求。

因此为实现订单合理连续排产，解决由不连续生产而造成的辐照时间浪费问题，提高生产效率，避免订单延期，在解决传统计划调度问题的遗传算法基础上加入订单重组策略，提出新的排产算法用于解决辐照膜订单排产问题。

1 数学模型

1.1 问题描述

辐照膜的工业生产流程主要分为：薄膜放卷，重离子辐照，敏化，蚀刻，薄膜收卷5大部分。所生产的辐照膜因为薄膜的厚度，微孔的大小，开孔密度形状的不同又细分为不同的型号。每种型号在生产时都要预先设定好系统的工作参数，如重离子加速器的辐照角度，辐照强度，收放卷的传送速度等必要工艺参数。不同于传统的干法湿法的物理拉升成孔原理，仅通过修改对薄膜的张力大小不能生产出不同型号的辐照膜。因此每当生产不同型号的薄膜时，整条生产线都必须停机重新设定参数，当订单型号多样时频繁的切换生产型号不仅仅造成大量的时间浪费，同时也会严重的影响系统的使用寿命，致使生产效率不能有效的提高。因此对于辐照膜，为减少订单延误提高生产效率，关键是实现订单的连续化生产。

为了使订单型号相同的薄膜尽量集中生产，提出订单重组策略。即将相同型号的订单，在约束条件容许的情况下，通过对订单产量的合理调整实现相同型号订单的集中生产，如图1所示。

图1 订单重组原理

图1中有A,B,C三种型号订单，按传统交付日排序会有4次型号切换。如果仅仅进行简单的订单合并会造成订单的延误，例如在1号之后插入5号会使2号延期。订单重组就是将5号的部分生产任务分别重组到1号和3号中，重组后型号切换将由4次降为3次。因为重组只是对订单的产量进行合理重分配，并没有因为重组造成订单数量的增加，不会造成订单求解空间的组合爆炸。同时又在不影响交付日的情况下尽最大努力实现订单的连续生产。

以已知的需求订单为研究对象，在订单最后交付日期，生产线最大产能等条件约束下，保持总产量不变以最大化连续订单生产为优化目标，结合辐照膜订单可重组的特点，建立辐照膜订单排产模型。

假设条件：①企业辐照膜产能固定，生产线的产能固定不变。②辐照膜订单能够提前完工，提前完工对辐照膜的生产没有影响。③订单排产针对生产线上订单。④辐照膜作为薄膜能够进行切分，订单的产量能够进行合理拆分重组。⑤拆分重组订单同原始订单只存在订购数量上的差别。

1.2 优化目标

保证生产总量不变的前提下，以最大化连续订单生产为优化目标见式(1)～式(3)，建立排产模型具体分析如下：

(1)延误日期率，在订单生产总量不变的前提下，订单的必要生产时间一定，订单的延误率越小表示订单排产的效果最好，企业获得的利润越高。其中：k表示特定排产序列，i和j表示订单，i,j∈ [1,2,…,n];aki表示订单i依排序后的生产顺序k，从排产日算起到生产完成为止所需时间;bi表示i订单从排产日算起到交付日为止的有效生产时间;di表示i订单延期(aki>bi)则为1，反之为0;si表示订单i的订购数量;c为常数，表示生产线的每日产能;式(1)LDi表示订单i的延误日期率；其中Di表示生产i订单的必要时间，LDk∈[0,1]。

(1)

(2)订单型号改变率(“互异”率)。定义“互异”特指排产序列中相邻两个订单型号不同的情况，k表示特定的排产序列，用Ek表示排产序列k中“互异”情况发生的总次数。G表示所有订单型号的总个数。式(2)STk表示k序列中的“互异”率，STk∈[0,1]。

(2)

(3)排产效率

将标准化后的延误日期率和“互异”率相加用来量化表征订单排产的效率SCk，SCk∈[0,2]。

SCk=LDk+STk

(3)

以SCk值得高低来代表辐照膜排产顺序的好坏，SCk值越低说明序列里订单延误和“互异”情况发生的次数越少，生产成本越低，效率越高。

1.3 约束条件

(1)生产线产能约束：式(4)表示全部订单量的总和小于等于年最大产能，c为常数表示日均产能。

(4)

(2)同型号合并生产约束：为了实现订单的重组，式(5)保证重组后订单的生产完成时间在交付日之前，式(6)保证下一订单的最迟交付日之间有余量。表示将j订单加入i订单中的生产量。其中D订单有富余的生产完成时间。

(5)

(6)

2 优化算法设计

遗传算法仿照自然种群优胜劣汰的机制，由染色体编码，交叉，变异，优势个体选择4个主要步骤组成，是一种智能优化算法。为了对上述目标模型进行优化计算，结合辐照膜生产的实际特点，在自适应遗传算法的基础之上引入订单重组机制，从而使得订单排产效果更好，同时加快了遗传算法的收敛速度。

2.1 染色体编码机制

改进后的自适应遗传算法，染色体以实数方式构成，染色体的排列顺序就代表了实际的排产顺序，同时为了适应订单重组机制，每次订单重组后形成一个新的订单群，每个遗传个体由两部分组成,分别为个体所属的订单群编号和个体染色体基因序列。

(0, [[R1], [R2], [R3], [R4], [R5], ……[Rn]])

(2, [[R1], [R2], [R3], [R4], [R5], ……[Rn]])

这里0,2就表示个体所属的订单群号，之后计算个体适应度值时就采用相应的订单群计算。[R1～Rn]即为个体染色体基因序列，代表了实际订单编号的排产顺序。

2.2 适应度函数及选择机制

算法以式(7)为适应度函数，选择算子采用“轮盘赌”的方式。因为SCk表示排产效率，取值在[0,2]之间所以适应度函数可以表示为：

maxF=3-SCk

(7)

式(7)将目标函数求最小转化为适应度函数求最大，能够更好的适应轮盘赌选择机制。

2.3 遗传算子

(1)交叉算子

为使得算法能够尽可能的搜索到全部的解空间，交叉算子采用由顺序交叉方式[13]即随机选择亲代中的一段基因固定复制到子代中，将另一亲代中的固定基因之外的依次填充到子代基因的空位上，生成子代。

(8)

其中，fmax表示种群中最高适应度值，favg表示种群的平均适应度值，fkmax表示参与交叉的k1,k2中适应度的最高值。

(2)变异算子

采用SHIFT变异算子[15]，随机在染色体中选出一段基因，将之倒置之后重新放回到原选出位置，实现变异。在调度排产领域这种变异方式已被证实是最为有效的变异机制之一[16]。

同理变异概率Pb也采用自适应方式，计算公式如下：

(9)

2.4 订单重组策略

在传统遗传算法的基础上加入订单重组策略，将原始的订单群通过基于适应度值、延误率、“互异”率的重组选择策略后，重组形成新的订单群能够有效的提高算法的优化性能，具体重组策略如下。

(1)统计生产时间情况

在遗传算法的精英种群中找到多个优秀个体k，遍历这个k个体中的基因序列[[R1][R2]......[Rn]]，计算得到个体k的生产时间情况集A。

A={Jki|Jki=bi-aki,i∈[1..n]}

Jki=bi-aki

(10)

(11)

式(11)表示依据k个体的基因排序，从订单排产日算起到订单实际生产完成为止所需要的实际生产时间。其中si为订单i的订购数量，c为常数表示生产线的日产能。

式(10)表示依据k个体的基因排序，i订单的实际需要生产天数同合同容许的计划生产天数之差，Jki>0表示i订单能够顺利生产完成且富余Jki天，Jki<0表示i订单将延期完成且比计划交付日延后Jki天。式中的bi表示从排产日到订单交付日i订单的计划容许生产天数。

(2)选择重组订单

遍历生产时间情况集A，找出Jki值最小的订单i作为被拆订单，和Jki值最大的订单j，作为待插入订单。其中对于j订单需要保证Jk(i+1)的值大于零，即保证订单产量调整后不会对后续订单的生产有影响避免连锁反应，同时j订单的交付日期要早于被拆订单i，保证在交付日期之前完成额定产出。当j订单不满足条件时选择次大的订单作为待插入订单。如果没有满足上述条件的i,j则没有可重组订单。

(3)确定重组量

i表示订单重组中减少生产量的延期订单，j表示增加生产量的生产时间富余的订单，z表示增加(减少)的生产量值。

z=

(12)

式(12)表示当j为k个体基因序的最后一位时，因为j之后没有未完成订单，因此只要i订单的产量小于j可接纳量时就能够将i订单全部合并到j订单中去，否则调整量z为j所能接纳的最大量Jkj·c。

当j不是最尾订单，接纳量要同时小于j和j+1订单的容纳量，以保证订单重组之后对后续订单的生产没有影响，不会发生连锁反应。

最后i订单的生产量为si-z，j订单的生产量为sj+z，修改对应值后完成订单的重组，产生新的订单集合，依此生成新的子代加入到父代种群中。订单重组后计算个体的适应度值只需按照对应的订单集合计算，而不需要对个体基因长度进行改变，能够有效的减少遗传算法编码的复杂度同时优化排产效果。

2.5 算法流程

利用改进后的遗传算法优化辐照膜订单排产，首先随机生成初代种群W1，个体基因长度同订单总量相同，种群个体数为订单数的2倍。每经过11次遗传操作加入1次订单重组操作，选择前10个精英个体进行订单重组，对重组后的订单集随机生成新的种群加入到原种群中，继续进行遗传操作直到最大迭代次数或算法收敛，得到最终的排序结果。具体算法过程如图2所示。

图2 改进后算法流程图

3 实例验证

应用上述改进算法对辐照膜排产问题进行求解。随机选取辐照膜生产企业的销售订单，数据包括辐照膜订单编号，薄膜定够量，薄膜型号，订单的交付日期等信息。对于其中的不同薄膜厚度，不同微孔形状的订单统一采用英文字母来区别订单的型号。实验中遗传算法的最大迭代次数为300次，基因编码长度同订单个数相同，交叉变异采用自适应概率式(8)、式(9)，以式(7)为适应度函数，式(3)为目标函数。

3.1 实验一

实验一，用下述三种方法对50个随机订单进行排产，试验结果如表1所示。

方法A：按照辐照膜订单中要求的订单结转交付日期顺序排产。

方法B：使用解决传统薄膜排产问题的遗传算法，不进行订单重组，进行辐照膜排产。

方法C：采用加入订单重组策略的新遗传算法进行辐照膜排产。

表1 三种方法对50个订单排产结果对比

实验表明改进后的遗传算法通过将订单进行重组，使得订单延误次数降为0次，同时较A,B两种排序方法，改进后的遗传算法使得因为生产型号互异而导致的停机次数分别减少了73%和57%，算法能够有效实现订单的连续排产，同时优化后的订单没有延误情况的发生，算法的正确性得到了验证。

3.2 实验二

实验二，以10个辐照膜订单为例对订单重组结果和改进前后的遗传算法的收敛性进行实验比较，实验结果图横轴为遗传代数，纵轴为染色体所代表的排产效率SCk，具体实验效果如图3、图4所示。

传统遗传算法：

图3 传统遗传算法结果图

图4 改进后的遗传算法结果图

排序结果：[5], [3], [1], [6], [4], [2], [8], [10], [7], [9]，“互异”次数：6次，总延误日期：130天，共有[1,2,7]这3个订单发生延误不能够按时完成。排产效率最小值为：1.2150847。原始订单集的详细信息见表2。

表2 原始辐照膜订单

改进后的遗传算法：

排序结果：[[1], [2], [4], [3], [8], [10], [5], [6], [7], [9]]，“互异”次数：5次，总延误日期：0天。排产效率最小值为：0.5。拆分后对应的订单集的详细信息见表3。

表3 辐照膜订单重组后的结果

表2、表3说明算法实现了对订单生产量的重分配，改进后的算法互异次数有效降低，延误率降为零。同时通过图3、图4比较发现加入订单重组的遗传算法和传统遗传算法都在迭代进行了100次后实现了算法的收敛，虽然订单拆分染色体算法较传统算法计算流程复杂但是重组并没有增加待排序订单的个数，算法仍具有良好的收敛性。

综合上述两个实验，订单重组遗传算法对于辐照膜能够合理的进行生产排序，由于算法实现了订单的合并使得停机次数降低了57%，节约了生产时间使得排序后订单的延期次数降为零，增大了企业利润。同时通过实验二的比较，从遗传迭代收敛图的比较上能够明显看到改进前后的算法都在100代时实现了收敛，算法步骤的增多没有影响算法的实质性能，仍然具有良好的收敛性。

4 结论

对于辐照膜订单排产的研究，结合辐照膜生产特性，将订单重组策略加入到传统遗传算法中，改进后的遗传算法能够更好的适应辐照膜订单排产的需要，突破了由于订单集固有缺陷对排产效率的桎梏，重组后的订单集排产更加合理，有效减少了订单延期和“互异”情况的发生。实验验证了所提模型和算法的正确性，最终得到了符合条件的排产序列。订单排产不能仅关注车间生产能力，对于订单本身的不合理也应作出修正，对于产品可拆分的订单在排产时都可以合理的进行订单数量的重分配，对于其他智能优化算法，如蚁群，粒子群等算法在进行可拆分订单的排产时都可以嵌入订单重组的机制，能够有效解决订单本身的不合理，从而得到更好的优化结果。融合多种机制求解可拆分订单排产算法是值得进一步研究探讨的问题。

DOI:10.1007/s40092-017-0205-y.