一种启发式算法和改进遗传混合算法在流水车间重调度中的应用

王 森, 熊福力,李 志

(西安建筑科技大学 信息与控制工程学院,西安 710055)

0 引言

流水车间重调度问题是以流水车间调度问题(flow shop scheduling problem,FSP)为基础模型的一种动态调度问题，多年来，研究者们大多关注以最大完工时间为优化目标，较少关注工件交货期对流水车间调度问题的影响。在考虑交货期时，一般认为交货期是一个固定的值，而不是一个模糊变量。遗传算法作为一种群体智能算法，具有全局搜索的特点，是求解流水车间调度问题常用的一种算法。然而，传统遗传算法存在收敛速度慢、稳定性差等缺点[1]。

在实际生产过程中，干扰事件的突然到来往往导致原调度不在可行，继而重新生成新调度方案，即为重调度。重调度即在尽量小损耗原调度性能水平的同时追求调度稳定性的优越， 如何既经济又髙效地实施干扰，重调度一直以来备受国内外调度学者与实践者的关注。常见的生产干扰事件有机器突然故障、一批新工件到达、工件返工、订单撤销、交货期提前、误操作等等[2]。

Chan和Hu[3]介绍了一种基于人工智能的制造业流水调度方法，并通过对预制生产特点的分析，建立了预制生产流水车间排序模型。Benjaoran[4]等人研究了模具数量对预制生产车间进度的影响，提出了定制预制生产车间进度模型。Ko和Wang[5]通过包括缓冲区大小的限制，即临时存储位置的大小，改进了人工智能调度的可行性，在机器之间，将待完工的部分完工预制件(以下简称在制品)存储到优化模型中，并开发出相应的调度系统。Yang[6]等人提出了多条预制生产线的流水车间调度模型，以促进多条预制生产线的优化调度。动态调度出现较早，Jackson对静态调度和动态调度做了区分。Yang[7]提出了流水车间预制生产多条生产线优化重调度模型。

本文针对传统遗传算法的不足之处对其作了相应的改进，在选择阶段引入了精英保留策略来确保算法的收敛性，在进行重调度时引入启发式算法；最后通过实验分析了该算法的优点，描述了流水车间重调度模型，并且通过实验分析了启发式算法和改进遗传混合算法求解流水车间重调度问题。

1 重调度的数学模型

FSP一般描述如下：有m台机器和n个作业；每个作业由m个操作组成，每个操作需要不同的机器。必须在所有机器上以相同的顺序处理n个作业[8]。其目的是找出作业顺序，使最大流动时间最小化，这在技术上被称为生产计划的最大完成时间。两个重要的约束为：① 一台机器上不能同时加工多个工件，且一个工件不能同时在多台机器上加工[9]；② 同一机器上工件的加工次序不限制，每个工件的加工路线亦无限制。预制构件都要经过6个生产步骤，即6道工序，它们分别为成型(M1)、放置钢筋和埋件(M2)、浇注(M3)、养护(M4)、脱模(M5)和精加工(M6)。其中，养护是一个并行过程，可以同时处理多个作业。除养护外，其余步骤是串行过程。浇筑，养护不可中断，其余步骤可中断；

1)优化目标

合同惩罚和存储成本是优化目标中，将随着工件数量线性增加。即优化目标表示为：

minfcs=αi*Max[0,duedate(i)-C(Ji,M6)]+

βi*Max[0,C(Ji,M6)-duedate(i)]

(1)

其中：fcs代表合同惩罚和存储成本；

Ji是按顺序i生产的工件号，Mk是处理第k步的机器的序号;

C(Ji,Mk)是预制件Ji在机器Mk上的离开时间;

αi,βk为早期惩罚与延期惩罚的惩罚系数;

duedate(i)是预制件Ji的交货期。

2)优化约束

(1)机器生产率约束

在调度过程中，不仅要考虑正常生产对机器生产率的约束，还要考虑生产紧急情况对机器生产率的制约。约束取决于生产条件变化的原因。式(2)和式(3)表示生产率的约束；

S(JiMk)≥

(2)

C(Ji,Mk)≥S(Ji,Mk)+Pi,k

(3)

其中：C(Ji,Mk),S(Ji,Mk),Pi,k是预制件Ji在机器Mk上的离开时间、进入时间、处理时间。

(2)八小时工作制的约束

式(4)表示浇注工序每天八小时的工作；式(5)表示养护工序每天八小时的工作；式(6)表示其他工序每天八小时的工作。

C(Ji,M3)≥

(4)

C(Ji,M4)≥

(5)

C(Ji,Mk)≥

(6)

其中：HW，HN,HE是每天允许工作时间、非工作时间和加班时间。T是在不考虑8小时工作制的情况下计算C(Ji,Mk)得到的。D=(T/24)是从生产开始到C(Ji,Mk)的总天数，D取整。

当有紧急加工工件时，对其进行重调度处理，对紧急工件的处理方式本文的做法为：给予紧急加工工件更高的加工权重，使其先加工；在重调度过程中尽可能早地完工紧急加工工件；而对于重调度的开始时间的设置，假设原调度的开始时间从零开始，在急件到达时刻RT>0，而工件交付日期不变，故而重调度的开始时间Txtart即为RT时刻当前工件的6个工序的离开时间：

Txtart=C(JRT,Mk)

(7)

其中：JRT取整数；

重调度策略的步骤如下所示：

①在已排好的调度计划基础上，有紧急订单到来；

②假设有多个紧急订单，确定影响订单优先级的各个因素，将所有订单按优先级进行排序；

③根据紧急订单策略，将紧急订单依次插入到待加工工序，找到库存成本与延期交货的惩罚之和最小的位置；

④找到所有紧急订单的插单位置，得出最小惩罚，插单结束。

2 启发式算法和改进遗传混合算法

2.1 改进遗传算法

遗传算法是一种模拟达尔文生物进化论的模型，是通过模拟自然进化来寻找最优解的一种群体优化算法。改进遗传算法在传统遗传算法的基础上，加入精英保留策略以及动态变异率，最后经过调参，找出结果最优的遗传算法各个参数，从而使得改进遗传算法结果更优。

2.1.1 编码

本文采用工件号编码来表示个体(染色体)，一组编码代表一种加工方案，如对于6个工件中的工序 [4 1 3 2 6 5]，其中数字的顺序代表工件在各个机器上的顺序，数字代表着相应的工件号，如数字“4”表示在机器上第一个加工工件为工件4，数字“1”表示机器上第二个加工工件为工件1，以此类推，数字“5”表示在机器上第六个加工工件为工件5。所有工件在机器上的加工顺序相同，且每台机器在同一时刻只能加工一个工件。

2.1.2 初始种群的产生

在本文中，初始种群是随机产生的。使用MATLAB软件中的随机排序函数“randperm”对染色体进行随机编码，给定种群大小，通过多次调用该函数得到所需大小的初始种群。

2.1.3 计算个体适应度值

以目标函数的倒数作为个体的适应度值，并采用精英保留策略[10]使最优个体存活下来。

2.1.4 选择

本文采用合同惩罚和存储成本最小的指标来对调度个体的适应度值进行评价，即个体适应度值大的为优良个体。在计算完每个调度个体的适应度值后，采用精英保留策略进行个体选择。

2.1.5 交叉

本文采用部分映射交叉(Partial-Mapped Crossover，PMX)进行交叉，首先，随机选择一对染色体(父代)中多个基因的起始和终止位置(在同一位置选择两条染色体)；然后，交换两组基因的位置；最后，进行重复检测，并建立基于两组交换基因的映射关系，如图1所示，以1-6-3这一映射关系为例，可以看到第二步结果中Child1存在两个重复基因1，则将基因1先变为基因6，在变为基因3，Child2存在两个重复基因3，与Child1基因转变顺序相反，这时将其通过映射关系将Child1中的重复基因1转变为基因6，将Child2中的重复基因3转变成基因6，可以看到第三步Mid1存在两个重复基因6，Mid2也存在两个重复基因6，再通过映射关系将Mid1中的重复基因6转变为基因3，Mid2中的重复基因转变为基因1。以此类推至没有重复基因为止，即图2中第四步Final1和Final2所示。最后所有重复的基因都会经过映射转变为另一个基因，保证形成的新子代基因无重复基因。

2.1.6 变异

交叉操作后形成的新个体具有一定的基因突变概率。与选择操作一样，这种操作是基于概率的，这就变成了变异概率pm。一般来说，变异概率设置得很小，一般pm≤0.05。

对交叉后代集中每个后代的每一位，产生一个随机数rand∈[0,1]，若rang

改进遗传算法的流程图如图2所示。

2.2 启发式算法和改进遗传混合算法

对于启发式算法，本文选取NEH快速启发式算法，该算法为快速求解生产调度问题的算法。由于遗传算法具有可扩展性，容易与其他算法结合的优点。因此当干扰事件到来时，采用启发式算法与改进遗传混合算法，改进遗传算法得出的最优结果作为初始解传入快速启发式算法中，作为快速启发式算法的初始解，将紧急加工工件依次插入到每个位置上，得到不同位置的解，找出最小惩罚的调度工序的位置，可以快速解决干扰事件带来的影响，而且两种算法的优点都体现出来，不仅运行时间短，而且得到合适解与对应的调度工序。

2.3 启发式算法和改进遗传混合算法流程

1)利用MATLAB软件中的随机排序函数“randperm”产生染色体的初始种群，每个染色体代表一个生产安排；

2)生成与染色体相对应的条件最优调度；

3)基于优化目标对它们进行评估并确定是否终止；

4)如果要继续，则基于前一个染色体，通过变异和交叉并返回到第二个步骤来生成新的染色体群；否则，结束计算并输出由步骤3选择的最优调度。

当迭代次数达到调度器给定的极限时，优化终止，得到最合适的调度工序。

5)先提取出调度工序，在上述步骤完成后，当有紧急加工工件即在RT时刻有新工件到来，将RT时刻之后的未加工工件的工序提取；

6)保持原有调度工序，将紧急工件依次插入所有位置，每次找出最优解的位置，逐次进行到最后一个紧急加工工件，最终得出最优调度。

3 实验结果及分析

程序运行平台是Windows10操作系统中的MATLAB软件，经过调参可得各种参数如下：种群规模大小取为NIND=50,迭代次数取为MAXGEN=200,改进遗传算法采用部分映射交叉方法进行交叉操作，采用换位法进行变异操作，交叉率和变异率分别取作：Pc=0.85，Pm=0.02。以下面5种规模来验证改进遗传混合算法的性能。本仿真实验包含10*6、20*6、30*6、50*6、70*6五种问题规模，每个规模在相同条件下运行30次。通过模拟紧急加工工件干扰下的重调度情景，统计了合同违约金与仓储成本(Earliness/Tardiness，E/T)的实施方案，在相同运行时间下与不同运行时间下的不同方案，在不同大小规模下的方案。

表1为部分结果，由表1可得，10*6，20*6，30*6，50*6，70*6的最优解分别为1 263.9，2 024.8，1 909.5，9 369.1，22 462，紧急订单规模分别取4*6，10*6，14*6，20*6，30*6。结果分析为在小规模如10*6与20*6规模情况下，蚁群算法结果较好，在30*6，50*6，70*6的其他大规模情况下，改进遗传算法结果较好，但所需时间远远大于提出的改进遗传混合算法的时间，以70*6为例，蚁群算法与改进遗传算法单次运行耗时50 s左右，而启发式算法和改进遗传混合算法单次运行耗时15 s左右，时间差距比较大，因此，对3种算法在相同运行时间下进行比较。

表1 不同运行时间下合同违约金与仓储成本E/T的比较

运行结果如表2所示，10*6，20*6，30*6，50*6，70*6的最优解分别为1 363.9，4 155.6，3 875，17 122，28 644，结果分析为在相同运行时间下，在10*6与20*6规模情况下，蚁群算法结果较好，对于30*6，50*6，70*6等其余规模情况下，启发式算法和改进遗传混合算法结果最优。故而，在同运行时间下对于大规模情况来说，本文提出的启发式算法和改进遗传混合算法结果最优。

表2 同运行时间下合同违约金与仓储成本E/T的比较

4 结束语

本文以合同违约金与仓储成本最小化为优化目标的流水车间重调度问题。采用精英保留策略以及动态变异概率对遗传算法进行了相应的改进。使算法具有较强的寻优能力。同时，考虑到随着个体数目变大遗传算法运行时间过长的缺陷，以及遗传算法容易与其他算法结合的优点，提出了启发式算法与改进遗传算法的混合算法，算法包含了两种算法的优点，在前期具有较强的寻优能力，随着个体数目变大运行时间也不会变慢。