黄 辉，李梦想，严 永

(西北工业大学 管理学院，陕西 西安 710072)

0 引言

随着经济社会的发展，技术水平和生活方式的革新与转变，产品模式消费需求逐渐开启了差异化个性化定制化的征程，相应的生产模式将更多的转向多品种小批量的混合流水生产。目前，在生产周期，设备利用率，生产成本等各项指标下，混合流水生产企业正面临着越来越复杂的生产调度问题，因此针对混合流水生产调度的研究也显得愈发迫切与重要。

Naderi B等[1]研究了存在工序跳跃的混合流水车间调度(Hybrid Flow Shop Scheduling，HFSS)问题，以最小化最大完工周期为目标建立模型并求解。Dios M等[2]研究了存在工序跳过的混合流程车间调度问题，重点分析了存在工序跳过的HFSS问题的难度并设计了新的启发式算法进行求解。Ebrahimi M等[3]研究了混合流水车间中依靠序列设置时间的调度问题，同时考虑交货期的不确定性和随机性，建立模型并求解。Nikjo B和Zarook Y[4]提出了一种新的考虑工件间设置时间的以最小化最大完工时间为目标的动态流水车间制造单元调度问题的数学模型并求解。徐建有等[5]和杨开兵等[6]考虑设置时间建立了多目标流水车间调度优化模型并进行求解。喻明让等[7]研究了考虑调整时间和机械故障的作业车间调度问题。周炳海和王腾[8]研究了考虑换模时间约束的混合流水车间调度问题。张煜等[9]研究了考虑设置时间和存在批处理机的HFSS问题。Visalakshi P和Sivanandam S N[10]研究了以负荷均衡为调度目标的动态车间调度问题。Pach C等[11]研究了以完工时间，能耗和资源转换的数量为多目标的柔性制造车间的调度问题。贺利军等[12]研究了以最大完工时间，最小化拖期时间，最小化库存成本以及最小化拖期成本为多目标的流水车间调度问题。蒋增强和左乐[13]研究了以能源消耗，加工质量，最大完工时间，和加权成本为多目标的柔性作业车间调度问题。施进发等[14]研究了以最小机器总负荷，最小提前/拖期完工的惩罚值，最大设备利用率和成品合格率为多目标的柔性作业车间调度问题；顾泽平等[15]研究了以最小化最大流程时间、设备负荷均衡以及最大化设备利用率为优化目标的柔性作业车间调度问题。

通过已有研究，可以发现在混合流水生产的研究中，针对带有工序跳跃问题或序列设置时间约束的调度问题的研究相对较少，同时绝大部分文献都是研究单目标的，其中以最小化最大完工时间为目标的最多，仅有少部分研究了多目标问题。而在实际的混合流水生产中，工序跳跃问题，设置时间问题以及调度的多目标化是非常常见的问题，且绝大多数生产系统都同时存在这三种问题，因此忽略这三个问题去研究生产系统调度，会由于与实际生产存在较大偏差而大大降低其研究价值和意义。本文在现有的研究基础之上充分考虑这三个问题，建立相应的数学规划模型并运用启发式算法进行求解，更加贴合实际的生产调度系统，对丰富混合流水生产的研究内容和指导实际的生产调度都有很大的参考价值和意义。

1 混合流水车间调度模型构建

1.1 问题描述

混合流水线调度问题(hybrid flow-shop scheduling problem, HFSP)最早由Salvador于1973年提出。标准的HFSP可描述为：n个工件在m个阶段的流水线上加工，各阶段均有一台或多台机器且必须有不少于一个阶段拥有两台及以上机器，同一阶段上各机器的处理性能相同，各个工件必须且只需在每个阶段的任意一台机器上加工一次[16]。

在实际生产中，标准HFSP相对较少，大多是标准HFSP的变形，其中有些工件在加工时存在工序跳跃的现象比较常见。这时为了使所有任务在加工时都能符合混合流水生产的标准模式，不妨假设那些需要跳跃的工序也需要进行加工作业，即设置虚拟作业并将其加工作业时间设置为0，同时为了减小对其他作业顺序的影响，可以设置虚拟的专用机器用于虚拟作业的加工，这样企业的生产状况就能符合混合流水生产的标准。相应的也就可以应用混合流水生产调度的方法和理论来针对企业现有的现状和问题进行改进优化研究。

1.2 模型假设

基于上述分析，本文可以构建企业的混合流水生产多目标调度优化模型。为使构建的模型更加科学严谨，还需要对其他未被考虑的因素做出如下假设条件：

(1)不同调度方案的生产成本无差异；

(2)同一阶段各加工设备属相同并行机；

(3)每个加工任务在第一阶段的发布时间均为0，且在其余阶段均无时间窗限制；

(4)各加工任务经过其序列设置时间后立即开始加工；

(5)加工任务按照其优先权进行排序，优先权大的工件序号排在前面，在同等条件下可优先进行加工；

(6)缓冲区容量为无穷大且操作允许等待，即加工任务的前一工序未完成，则后面的工序需要等待；

(7)每个任务的加工时间和序列设置时间事先给定，且在整个加工过程中保持不变；

(8)在加工任务存在工序跳跃的工序设定虚拟机器进行虚拟作业。

1.3 参数设置

(1)索引

i为加工任务索引，i∈{1,2,3,…,N}；

s为工序索引，s∈{1,2,3,…,S}；

k为工序s的机器索引，k∈{1,2,3,…,Ms}；

r为工序s下一加工工序snext的机器索引，若对应工件下一工序跳过则表示下下工序，以此类推，r∈{1,2,3,…,Ms}；

l为各工序各机器设备的位置索引，l∈{1,2,3,…,Ns,k}。

(2)参数

N为加工任务总数量；

S为总工序数量；

Ms为工序s的实际机器数量，不包括加工虚拟作业的虚拟机器；

Ns为工序s加工的任务数，若该工序不存在工序跳跃则Ns=N，反之Ns等于N减去跳跃的任务数；

Ns,k为工序s上机器k加工的总加工任务数；

ti,s,k为加工任务i在s工序的设备k上的加工时间；

ps,m,l-1,l为在s工序k机器上第l-1位置的加工任务到第l位置的加工任务的加工的序列设置时间，通常为换模时间。

(3)变量

Ui,s,k,l当加工任务i安排在工序s的机器k上的第l位置加工时Ui,s,k,l=1，反之，则Ui,s,k,l=0;

ci,s,k为加工任务i在s工序的k机器上的完工时间，若s=S则表示该加工任务的完工时间；

si,s,k为加工任务i在s工序的k机器上的开始加工时间；

si,snext,r为加工任务i在snext工序的r机器上的开始加工时间；

1.4 生产调度数学模型

本文充分考虑工序跳跃问题，设置时间问题和调度的多目标化三个重要指标，构建更加符合企业实际生产状况的混合流水生产多目标调度优化的数学模型如下:

minf1=Zp=min(max(ci,s,k))

(1)

(2)

公式(1)表示调度的目标函数1最小化最大完工时间，即最后一道工序的最大完工工时间最小；公式(2)表示调度目标2设备负荷均衡指标，即各工序内各机器设备的加工时间的标准差的均值；公式(3)表示机器约束，任意加工任务在任一工序只能在一台机器设备上加工一次，若该任务在该工序存在工序跳跃，即使用虚拟机器进行虚拟作业，则可以忽略不记；公式(4)表示任务约束，即任意加工任务都必须在每个工序进行加工，不包括虚拟加工；公式(5)表示时间约束，只有前一工序的加工完成后才能开始下一工序的生产；公式(6)表示加工任务的完工时间等于开始时间加上加工任务的加工时间和序列设置时间；公式(7)表示设备只有上一加工任务加工结束后才能开始下一加工任务的加工；公式(8)表示工序内每台机器设备的平均加工时间，不包括虚拟机器。

2 NSGA-II算法设计

参考同类研究可以发现多目标的GA更适合求解本文所研究的具体问题，常见有多目标遗传算法(MOGA)，小生境Pareto遗传算法(NPGA)，非支配解排序遗传算法(NSGA和NSGA-II)等，其中在多目标的研究中，NSGA-II普遍具有更好的性能和效率。但是标准的NSGA-II在求解不同问题时也存在一定的不足之处，如在进行交叉变异操作时，其交叉变异参数固定不变，不利于最优解搜索；精英保留策略选择下一代时完全按照等级排序来选择，未考虑进化后期会出现大量重复个体以至于种群多样性大大减小，从而影响算法后期的搜索能力等。为了获得更加准确的Pareto最优解，本文针对NSGA-II的不足之处，设计了一种改进的NSGA-II算法来进行求解。

2.1 编码设计

车间调度优化问题常采用实数编码，混合流水生产调度问题是车间调度问题的一种，因此本文也选用十进制编码。由于混合流水生产需要把每个任务在每个阶段的操作都表示出来的特殊性，在编码时可以采用基于机器的矩阵编码，这样能更加清晰明了的把每个任务在每个阶段的加工设备显示出来，且能够使解码操作更加方便，不足之处是矩阵编码不利于遗传操作。为解决这个问题，本文选择以矩阵思想设计编码，即先构建虚拟矩阵，再运用函数将其转化为行数组，数组与矩阵对应位置的特征相同，然后按照转化的行数组特征来生成初始种群，并在解码时可将其转化为矩阵，最后在进行遗传操作时仍在原数组进行。具体编码方式为构建一个虚拟的N×S的矩阵(N为加工任务的数量，S为加工阶段的数量)，如公式(9)所示，X为该调度问题的一个编码(染色体)，表示该调度问题的一个可行解，即一个个体，矩阵中的xij表示任务i在j加工阶段所使用的机器设备编号，其取值范围取决于该工序的机器数量，若该工件在该工序的机器固定则只取一个固定的整数，若该工件需要跳过该工序，则取值为0。编码时运用该矩阵转化的行数组X′(如公式(10)所示)的特性生成数组形式的染色体，再在解码时把行数组转化为矩阵X″，如公式(11)所示。

(9)

X′=reshape(X,1,N×S)

=[x1,1,x2,1…xN,1,x1,2,

x2,2…xN,2…x1,S,x2,S…xN,S]

(10)

X″=reshape(X′,N,S)=X

(11)

2.2 NSGA-II算法的改进

2.2.1 种群初始化改进

种群初始化通常都是使用相应的函数根据设计好的染色体编码随机生成种群规模数量的染色体，这些染色体均为优化问题的可行解，他们作为初始个体共同构成了初始种群P0。在生成初始种群时，为保障随机概率性，各基因位的取值范围设为实数区间，如有4台机器设备，其取值范围为「1,5)，在解码时对实数进行向下取整，获取相应的机器设备编号。此外，为了提高算法性能，往往还需要进行以下处理：一是让初始种群尽可能均匀地分布在解的空间之内，以避免陷入局部最优；二是采用一些简单的方法对产生的初始解进行初步的筛选，剔除质量最差的一部分解。

针对本文所设计的染色体特征，可在初始化的染色体进行以下筛选以提高算法的搜索效率和质量：种群中每个个体的染色体需满足每个工序中每个机器均被使用，否则该染色体需要重新生成，直到满足该条件为止。

2.2.2 替换操作改进

基本NSGA-II算法的精英保留策略能够保留各代种群中最好的个体，使算法性能和效率大大提升，但是随着进化代数的增加，子代种群中逐渐会出现大量与父代种群相同且等级较高的个体，导致种群的多样性也会迅速下降，进而出现早熟或者陷入局部最优解的现象[17]。为弥补精英保留策略的这种不足之处，保证种群的多样性以确保搜索方向朝着真正的Pareto解发展，本文针对基本的精英选择策略进行了一定的改进，在执行精英保留策略选择下代种群时只选择各等级种群中拥挤度不为0的个体，这样就能保证相同个体最多只能选取两个，这样既保证了种群的多样性，又在一定程度上提高了算法的搜索效率。

2.2.3 交叉参数改进

本文中交叉概率和变异概率相互补充，交叉概率越大，则变异概率越小，反之则变异概率越大。通常在算法求解的前期应优先保证新个体的产生，因此交叉概率应相对较大，而后期算法相对收敛应扩大搜索范围以避免陷入局部最优，与此同时采用精英保留策略又能很好的消除变异率过大带来的负面影响。据此本文设计一种自适应交叉概率参数，其交叉概率随着遗传代数的增加而自适应的降低，而变异概率则自适应的提高，交叉概率的具体取值如公式(12)所示：

(12)

式中t表示种群当前迭代数，T是指种群最大迭代次数，T1是指第一阶段的最大迭代数，这里选择为0.25T，T2是指第二阶段的最大迭代数，这里选择为0.75T，β为进化后期阶段交叉率的调节系数，该系数的设置可以保证非支配集个体的交叉率在进化后期阶段渐近于后期阶段起始值的倍，其取值范围为(0,1]，本文在进化后期为了避免交叉率过小，设置为β=0.8[18]。

3 算例验证

3.1 算例数据

本文结合具体的混合流水车间生产的实际情况，根据车间实际数据来假定仿真的算理数据，主要包括生产资源数据和生产任务数据。在生产资源数据方面，混合流水车间共有4个工序，其各工序的设备数量如表1所示，在该生产车间中部分生产任务在工序2或者工序3存在工序跳跃。

表1 生产设备数量表

根据该车间历史生产任务，假定了一定周期内的生产订单作为仿真的任务，同时根据各个订单的产品类型获取这些生产任务在各工序的生产加工时间以及各任务之间的序列设置时间。本文共选取了20个生产任务进行仿真分析，其在各工序的加工时间数据如表2所示，各任务在各工序的序列设置时间表因篇幅原因不再展示。

3.2 基于改进NSGA-II算法的调度结果与分析

本文采用MATLAB软件实现了基于改进NSGA-II算法的混合流水生产企业多目标优化研究的算法设计及编码求解，在实验过程中，计算机的基本配置如下：(1)操作系统为Windows7 X64旗舰版；

(2)CPU为Intel core(TM)i5-2400，3.1GHz；

(3)内存RAM为4GB。

表2 各工序加工时间数据表(单位：小时)

基于上述企业的生产数据运行改进NSGA-II算法可求解出完成该生产任务的Pareto最优调度方案，运行结果可得到负荷均衡指标Tlb进化收敛曲线图，如图1所示；最大完工时间目标Zp进化收敛曲线图，如图2所示；本次求解共求得10个Pareto最优解集，如表3所示。

图1 负荷均衡指标Tlb收敛曲线图

图2 最大完工时间Zp收敛曲线图

图1和图2中最上方曲线分别表示各代种群中负荷均衡Tlb和最大完工时间Zp两个目标的最大值收敛曲线，中间部分曲线分别表示各代种群中这两个目标的均值收敛曲线，最下方曲线表示各代种群中两个目标的最小值收敛曲线。由图中可知：

(1)整体来看，在进化前期两个优化目标无论是均值还是最大值和最小值，都在迅速的减小并逐渐收敛，这表明了算法具有较好的性能，而在进化后期两个目标的均值和最小值基本不变或稍微减少，最大值却存在一定的波动，这表明算法在保留最优解的同时还具有较强的持续搜索能力，在局部范围内波动时两者的波动存在一定的相关性，即两个目标的最大值基本不同时减少，往往是在一个目标保持不变或者增大时迅速地减小，这表明在两个目标在进化过程中不断地相互均衡取舍，并最终达到相对的平衡；

(2)随着进化代数t的增加，各代种群的负荷均衡目标Tlb和最大完工时间目标Zp的平均值先迅速减少然后逐渐趋于平稳，并于100代之后分别收敛于18和375左右，在进化后期，各代种群中负荷均衡目标Tlb和最大完工时间目标Zp的均值始终更接近于最小值，这表明种群中的各可行解主要集中于最小值附近，而最大值的适当保留又表明了各代种群的多样性，能够提高进化过程的进化空间，有效的避免陷入局部最优。

表3 Pareto最优解集

本次优化共生成10组帕累托最优解，表3共展示有代表性的6组解，Pareto最优解各行对应的是该工序上各加工任务所使用的机器编号，Zp和Tlb对应的是两个目标值，单位为小时，从表中可以看出：

(1)从Pareto最优解1～6可以看出，相邻解的差异非常小，各任务中大部分任务在各工序的加工机器是完全相同的，仅有3～5个任务在部分工序上选择的机器不同，即便是最优解1和6这两个目标距离最远的解，也有一半的任务在各工序的加工机器完全相同，这表明算法在局部搜索时具有优异的性能；

(2)在这6个解中，Pareto最优解1的最大完工时间目标Zp最小，Pareto最优解6的负荷均衡目标Tlb最小，在进行最优调度方案选择时，若决策者更加看重负荷均衡目标Tlb，则最佳决策方案更可能为Pareto最优解6，反之若决策者更加注重最大完工时间目标Zp，则最佳决策方案更可能为Pareto最优解1，若两者之间相对平衡，则最优解更可能为中间其他解；

根据所求解的Pareto最优解集，可以绘制各个解的甘特图，这里以Pareto最优解6为例，其对应的甘特图如图3所示，虚线白框，黑框，实线白框和灰框依次对应第一道工序加工时间，第二道工序加工时间，第三道工序加工时间和第四道工序加工时间。从图3中可以更加直观的看到各加工任务在各工序加工时所使用的机器编号，起始加工时间以及各加工任务的完工时间，其中最后完工的加工任务为17号加工任务，其加工完工时间即为所有加工任务的最大完工时间。

图3 Pareto最优解6的甘特图

4 结论

目前，在生产周期，设备利用率，生产成本等各项指标下，混合流水生产企业正面临着越来越复杂的生产调度问题，针对混合流水生产调度的研究也显得愈发迫切与重要，其中结合具体企业的研究更有理论意义和实用价值。因此本文结合混合流水车间多品种生产的特性，基于各个加工阶段各加工设备在加工不同品种的产品时，需要一定的序列设置时间来完成设备设置、换模或调试等任务以及某些产品在加工时存在工序跳跃这两种特征为主要约束条件，建立以能够直接反映生产周期的最大完工时间和能够有效反映生产效率的负荷均衡指标为双目标的多目标调度优化模型。并基于一定数据进行算例验证分析，证明模型的有效性。该模型能够有效的解决此类调度优化问题，并为企业的实际调度提供一定的参考。