柔性作业车间调度问题(flexible job-shop sche- duling problem, FJSP)突破了资源唯一性限制，每个工序可由多个不同的机器完成，从而使作业车间调度问题更加符合生产实践^[1]。随着计算机技术的高速发展，传统的FJSP问题可以用多种智能算法求解。如改进的人工蜂群算法、蚁群算法、人工鱼群算法、细菌觅食算法以及新型教学优化算法^[2-6]，相对来说用遗传算法求解柔性作业车间问题研究成果比较丰富。赵诗奎等^[7]针对局部搜索能力提出基于工序编码和邻域搜索策略的遗传算法；I Driss 等^[8]改进了交叉和变异策略，提高了遗传算法的收敛性；G Zhang等^[9]利用全局选择和局部选择得到高质量的初始化种群。虽然运用改进的智能进化算法得到了良好的效果，但是鉴于求解模型目标函数较少，无法符合当今生产决策时的需求。

在求解多目标柔性作业车间调度问题时，由于存在多个彼此冲突的目标，如何获取问题的最优解，依然是车间调度关注的焦点问题。Kacem等^[10]提出了基于局部优化方法和EA的混合Pareto方法优化工件完成时间和机器负载。张超勇等^[11]设计改进的NSGA求解FJSP的Pareto解集,并运用层次分析法选出最优妥协解。Roohollah Javadi等^[12]通过使用并行禁忌搜索算法对每个群集的最佳解决方案执行局部搜索，并且最终在其中获得最优解。

本文根据实际加工车间，在建立多目标模型的过程中，综合考虑了生产完工时间、交货期、机器负载以及机器运行成本，此模型更加符合当今生产决策需要。在求解多目标模型过程中，针对目标值的特征，设计一种改进的多目标优化进化算法，该算法不仅避免了处理不同目标函数值之间数量级和量纲的障碍，而且相对其他智能算法具有良好的性能，最后通过对实际加工实例的求解，验证了模型和算法的可行性及有效性，为实际生产中柔性作业车间调度提供参考。

1 柔性作业车间多目标调度模型 1.1 问题描述

现代制造企业面临日益激烈的市场竞争，在生产过程中，既要求生产周期短、交货期短，又要求生产成本较低、机器负载小。忽略任何一部分要求对企业整体的发展都是不利的，如何建立调度模型，寻求合理的生产调度方案成为生产制造的关键。

假设有n个工件要在m台机器上加工，每个工件 ${J_i}$ 由h个工序组成，工件的每道工序可由m台机器中的多台机器加工，并且在不同的机床上加工所需时间不同。在加工过程中还需要满足以下约束条件^[13]：同一时刻同一台机器只能加工一个零件；每个工件在某一时刻只能在一台机器上加工，加工过程不能中途中断；同一个工件的工序间有先后约束，不同工件的工序之间没有先后约束；不同工件具有相同的优先级。

本文研究对象为柔性作业车间调度问题，即从完成时间、交货期、机器负载以及生产成本等方面建立优化目标，提出制造企业的生产调度方案。现假设一个包括3工件、4台机器的柔性作业车间调度的加工时间表如表1所示。

1.2 多目标调度模型

目标函数为

$\quad\quad{f_1} = \min (\mathop {\max }\limits_{j = 1,2,...,n} {C_j}),$

(1)

$\quad\quad{f_2} = \mathop {\min (\max \left| {{C_j} - {d_j}} \right|}\limits_{j = 1,2,...,n} ),$

(2)

$\quad\quad{f_3} = \min \sum\limits_{j = 1}^n {\sum\limits_{i = 1}^{{h_j}} {\sum\limits_{k = 1}^m {{p_{jik}}} } } {X_{jik}},$

(3)

$\quad\quad{f_4} = \min (\max \sum\limits_{j = 1}^n {\sum\limits_{i = 1}^{{h_j}} {{p_{jik}}} } {X_{jik}}),$

(4)

$\quad\quad{f_5} = \min \sum\limits_{k = 1}^m {\left\{ {(\sum\limits_{j = 1}^n {\sum\limits_{i = 1}^{{h_i}} {{p_{ijk}}{X_{ijk}}} )F_k^v} } \right\}} ,$

(5)

$\quad\quad{f_6} = \min \sum\limits_{k = 1}^m {\left\{ {\left[ {{T^*} - (\sum\limits_{j = 1}^N {\sum\limits_{i = 1}^{{n_j}} {{p_{ijk}}} } {X_{ijk}})} \right]F_k^s} \right\}} {\text{。}}$

(6)

约束条件为

$\quad\quad\sum\limits_{k = 1}^m {{X_{jik}}} = 1,{X_{jik}} = 0\text{或}1;$

(7)

$\quad\quad{p_{jik}} {\text{≥}} 0,{p_{j0k}} = 0;$

(8)

$\quad\quad F_k^v {\text{＞}} 0,F_0^v = 0;$

(9)

$\quad\quad F_k^s {\text{＞}} 0,F_0^s = 0{\text{。}}$

(10)

式（1）~（6）为工件最大完工时间最小、最大延期时间最小、机器运行负载总和最小、瓶颈机器负载最小、机器负载运行成本最小以及机器空载运行成本最小。式中， $j = 1,2,...,n$ ， $k = 1,2,...,m$ ； ${C_j}$ 为工件 $J{}_j$ 的完成时间； ${d_j}$ 为其交货期； ${T^*}$ 为某调度方案的最大完成时间； ${p_{ijk}}$ 为工件 ${J_j}$ 的第 $i$ 道工序在第 $k$ 台机器上加工需要的时间； ${X_{jik}} = 1$ 为决策变量，表示 ${J_j}$ 的第 $i$ 道工序是否选择在第 $k$ 个机器上加工， ${X_{jik}} = 1$ 表示选中， ${X_{jik}} = 0$ 表示未选中； $F_k^v$ 为第 $k$ 个机器的动态费率； $F_k^s$ 为第 $k$ 个机器的静态费率。

2 改进的多目标优化进化算法

在多目标进化算法领域，研究人员采用不同的适应值分配策略、选择策略、多样性保持策略、精英策略及约束条件处理策略等，涌现出许多优秀的多目标进化算法^[14]。2002年，DEB等^[15]对NSGA算法进行了改进，提出了NSGA2算法。NSGA2具有运行速度快、鲁棒性好、收敛性好等优点，已经成为处理多目标优化问题的重要基础。但是在运用NSGA2求解多目标柔性作业车间调度问题时，一方面，选择操作会出现个体收敛在种群中大部分非支配解的等级都在等级为1的非支配曲面上，且拥挤距离为0的情况。鉴于此问题，在算法选择过程中引入免疫学原理，通过免疫自我调节功能，计算抗体和抗体之间的亲和度，优先选择等级小的个体，当等级相同，拥挤距离相同时选择抗体浓度大的个体，提高了种群间个体与个体的竞争，改善算法的局部搜索能力。另一方面，在精英保留策略上，出现大部分非支配解都在等级为1的非支配曲面上，而非支配曲面可能远离真正的Pareto最优边界，或者会使进化种群在选择的非支配解全是精英，这将导致种群的提前收敛或者收敛于局部最优解。为保持种群多样性和提高算法收敛性能，在父代种群中限制精英解的数目，适当地选取一些非精英解加入，具体处理方法就是引入一个分布函数来实现。该分布函数表示为

$\quad\quad{n_i} = E \cdot {F_i}{\text{。}}$

(11)

式中， ${n_i}$ 为第i层非支配曲面 ${F_i}$ 上选取的个体的数目； ${F_i}\left({i {\text{≥}} 1} \right)$ 为第i层非支配曲面上个体的数目； $E$ 为常数0.6。

2.1 亲和度评价算子

亲和度评价算子可以描述为函数 $aff(x):$ $S \to R$ ，其中，S为问题的可行解区间，R为实数域。抗体之间的亲和度反映了抗体之间的相似程度，设M为含m个字符的字符集，种群G为N个长度为l的字符串组成的集合，即

$ \quad\quad G = \{ X = {x_1},{x_2},\cdots,{x_l},{x_i} \in M,1 {\text{≤}} i {\text{≤}} l \} {\text{。}} $

(12)

种群中基因座为j的信息熵描述为^[16]

$\quad\quad{H_j}(G,N) = \sum\limits_{i = 1}^m { - {p_{ij}}\log {p_{ij}}} {\text{。}}$

(13)

其中， ${p_{ij}}$ 为M中第i个符号出现在基因座j上的概率。群体G的平均信息熵为^[16]

$\quad\quad H\left({G,N} \right) = \frac{1}{l}\sum\limits_{j = 1}^l {{H_j}(G,N)} {\text{。}}$

(14)

抗体i和抗体j的亲和度为

$\quad\quad{\rm{aff}}(i,j) = H(G,2),G = \{ i,j\} {\text{。}}$

(15)

2.2 抗体浓度评价算子

抗体浓度评价算子可以描述为函数 $ {\rm{den}}(x): $ $ S \to [0,1] $ ，其具体的计算方法通常定义为^[16]

$\quad\quad{\rm{den}}(i) = \frac{1}{N}\sum\limits_{j = 0}^{N - 1} {{\rm{aff}}(i,j)} {\text{。}}$

(16)

其中，N为种群规模；i为种群中的第i个抗体； ${\rm{aff}}(i,j)$ 为抗体i与抗体j的亲和度。

3 基于改进的NSGA2方法求解多目标FJSP问题 3.1 编码

根据柔性作业车间的特点，编码方式采用一种扩展的基于工序的编码^[17],前部分为基于工序的编码，根据工件的序号在染色体中出现的次序编译，第k次出现的工件序号表示该工件的第k道工序；后半部分为机器选择部分的编码，编码中序号代表相应工序的加工机器集合中的序号，此种编码方式操作简易，能产生可行解。如表1中的调度问题，基因串可表示为[2133112312112233]，各工序的加工顺序为 ${O_{21}}{O_{11}}{O_{31}}{O_{32}}{O_{12}}{O_{13}}{O_{22}}{O_{33}}$ ，各工序对应的加工机器号为[12113344]。

3.2 Pareto排序

本文采用Abdullah Konak等^[18]提出的一种快速排序方法构造非支配解集。该方法使得计算复杂度比原来的NSGA算法有所降低，其计算复杂度为 $O(M{N^2})$ （其中，M为目标函数；N为种群大小）。

3.3 改进的选择策略

本文采用二元锦标赛选择，优先选择快速排序过程中得到的个体的等级较低的个体，当个体等级相同时，选择拥挤距离较小的个体，当拥挤距离相同时，选择抗体浓度较小的个体。

3.4 交叉操作

针对FJSP的特点，POX交叉操作能够很好地继承父代优良特征，并且相同条件下，此方法能够得到比其他交叉操作更好的结果，故本文对基于工序编码基因串采用POX交叉^[18]，对基于机器分配编码基因串采用多点交叉^[19]。

3.5 变异操作

对于基于机器分配这部分基因采用互换法进行变异。随机选取两道工序，两道工序的机器集合中选择加工时间少的机器，并将选择的机器号编入对应的基于机器分配编码的基因中，保证得出的解是可行解。在基于工序编码的基因串采用插入变异，即从染色体中随机选择一个基因插入一个随机的位置。

3.6 改进的精英保留策略

根据非支配关系进行排序，先将支配等级低的个体填充到新的父代中，同一级的选择个体浓度小的个体加入，直到种群数量达到N。

算法具体的求解步骤如下，流程图见图1。

步骤1 初始化开始种群 ${P_0}$ 。

步骤2 采用快速排序方法初始化每个个体的 $\rm{rank}$ 值。

步骤3 设 $t = 0$ 。

步骤4 基于抗体浓度的选择。

　步骤4.1 根据抗体和熵原理，计算个体（抗体）的浓度。

　步骤4.2 优先选择等级小的个体，当等级相同，选择抗体浓度大的个体。

　步骤4.3 如果 ${P_{t + 1}}$ 种群个体数达到N，则继续步骤5，否则返回步骤4.1 。

步骤5 在 ${P_{t + 1}}$ 上执行交叉和变异操作，产生新的种群 ${Q_{t + 1}}$ 。

步骤6合并 ${P_{t + 1}}$ 和 ${Q_{t + 1}}$ 产生出组合种群 ${R_{t + 1}} =$ ${P_{t + 1}} \cup {R_{t + 1}}$ 。

步骤7 对 ${R_{t + 1}}$ 进行非支配排序，并通过排挤和改进的精英保留策略选出N个个体，组成新一代种群 ${P_{t + 1}}$ 。

步骤8 如果 $t {\text{＜}} \max {\rm{gen}}(\text{最大进化代数}),$ 则 ${{t}} = t + 1$ ，返回步骤3；否则算法终止。

4 仿真实验与结果分析 4.1 仿真测试

为了方便算法测试，本文采用文献[18]中的标准实例（问题 $8 \times 8$ ,不带释放时间）作为算例进行对比。优化目标为前面提到的最大完工时间 ${f_1}$ 和瓶颈机器负 ${f_4}$ ，算法参数设置与文献[18]中保持一致，参数设置如下：种群规模 ${P_0}$ 取100，最大迭代次数为100，交叉概率为0.8，变异概率设为0.1。所有算法采用Matlab 编程，在Inter Core i3-2310M 2.10 GHz Windows7.0上运行。为了测试算法的有效性，将测试结果和启发式规则、GA、Kacem方法^[10]、Zhang和Gen方法、PSO+GA和HGATS^[12]进行比较。

通过表2可知，改进的NSGA2算法的最大完工时间最好值为14，比文献中启发式规则方法至少减少了5个单位，比GA减少了2个单位，和HGATS中最好值保持相同；瓶颈机器负载的最好值为11,相比启发式规则优势依旧明显，减少了4个单位，比文献中PSO+GA方法减少了1个单位，比PSO+GA和HGATS均少1个单位，优化性能均得到提高，由此可见，改进的NSGA2算法对求解多目标车间调度问题具有良好的效果。

4.2 实例分析

某企业的配件制造车间主要承担汽车配件制造任务，通过对制造车间实际数据的整理，得到10工件6机器的柔性作业车间调度问题的数据。表3给出了各工件的加工机器、加工时间以及交货期，表4给出了机器运行时的负载成本和空载情况下运行成本。算法采用表2的算法，参数设置与表2保持相同。由于6个目标同时优化时，Pareto的解集构成一个超曲面，故无法用图直观地显示可行解，表5给出了一次运行中得到的50个Pareto最优解。决策者可根据车间现场实际情况，在后续的调度管理过程中，选择其中一种方案进行调度。限于篇幅，本文只对第1组数据做出调度控制的甘特图，如图2所示。

5 结束语

根据实际车间加工情况，建立了具有时间、成本以及机器负载等性能指标的多目标柔性作业车间的调度模型，更好符合实际生产需求。如何完善调度模型依然有待进一步研究，比如如何在生产过程中引入低碳和环保方面的优化目标。

基于NSGA2算法在解决多目标优化问题时选择策略和精英保留策略收敛于局部曲面上的问题，引入了一种基于免疫信息熵的选择策略和精英保留策略，建立改进的NSGA2算法。运用改进的NSGA2算法对测试数据和实际加工问题进行多目标优化求解，均能得到满意的Pareto解集，进一步验证了改进的NSGA2算法在求解此类问题的可行性及有效性。