薛冬娟，殷喜龙，潘 颖

（1.大连海洋大学 机械工程学院，大连 116023；2.大连海事大学 交通运输管理学院，大连 116023）

0 引言

离散制造业车间调度问题目前已从相对简单的经典车间调度问题逐渐转化为柔性作业车间调度问题（Flexible Job-shop Scheduling ，FJSP），打破了经典车间调度对某一产品的每个加工工序只能由一台设备加工的约束，FJSP不仅要确定各产品加工工序的顺序，而且要将各工序分配给不同的设备，从而保证所有产品的最大加工时间最短，属于NP-hard难题。谢皓等[1]以最大完工时间最短为目标，采用遗传算法对一个8×8(8台加工设备，8种工件)的问题进行计算，并没有考虑在实际生产中调度问题是典型的多目标优化问题。王硕、曹岩等[2,3]采用了一种改进的蚁群算法对机器编码,控制冗余解的数量，提高算法的计算速度，计算模型则是经典的车间调度模型与实际生产有一定的差距。此外，有部分学者考虑了实际生产中车间调度问题属于多目标优化问题，如刘烽等[4]针对混合流水车间多目标调度问题，以最大流程时间和生产中所消耗的总能量最小为目标函数，建立了混合整数规划模型，采用NSGA2算法计算了12×8的调度问题。魏巍等[5,6]分别以加工成本、加工质量、制造工期最短、设备利用率最大为目建立多目标优化模型，采用智能算法求解小规模的调度问题。曾强等[7,8]针对柔性作业车间调度问题中加工路径的不确定性，以最长完工时间最小和加工费用最少以及设备利用率最高为目标，建立多目标调度问题模型。

综合上述研究发现，现有的文献主要存在两点不足之处，一是在建立车间调度模型时没有考虑足够的约束和目标，大多数研究目标没有考虑到在实际生产中应当尽量减少产品的搬运距离/次数；二是在解决车间调度问题的同时并没有考虑车间加工设备位置布局，造成车间内的物料无效搬运距离/次数增加。

针对上述不足，本文首先建立了以最大完工时间最小、总延期时间最小、总提前期时间最小、设备总负荷最小、单台设备的最大负荷最小、总生产成本最低以及工件搬运次数最少的多目标车间生产优化调度模型。然后，对于优化的pareto解集采用AHP确定其最优调度方案。再次，根据车间调度问题确定的产品加工工艺线路，以加工产品搬运距离最少为目标，对现有的车间设备布局进行优化，使车间无效的搬运量最小。最后，以大连某空调生产车间为例，通过对一个10×10的车间调度进行计算，验证了本文算法和模型的可行性。

1 离散车间多目标调度数学模型

1.1 问题描述

多目标FJSP是指在m台设备（M={mk|1,2,…,m,k=1,2,…,m}）上加工n个工件（J={ji|j1,j2,…,jn,i=1,2,…,n），每个工件包含Ni个事先确定加工顺序的工序，每个工序可以在多台设备上加工，mij表示工件ji的第j道工序可使用的加工设备集合。Sijk为工件ji的第j道工序在设备k上开始加工时间，Eijk为工件ji的第j道工序在设备k上结束加工的时间，工件ji的第j道工序在设备k上的加工时间为tijk，Ti表示工件ji的最后一道工序的完工时间，Di表示工件ji的交货时间，α表示单位时间延期交货费用为。工件ji的原材料费用为Ci，不同设备单位时间的加工费用用pk表示，单位时间的调整费用为sk，用wijk表示工件ji的第j道工序在设备k上的调整时间。Xijk为决策变量，当工件ji的第j道工序在设备k上加工时，取值为1，否则为0；Yikk为决策变量，当工件ji的第j道工序与第j-1道工序都在设备k上加工时，取值1，否则为0；车间调度的目的是在有限的资源条件下，将各个工序分配到相匹配的设备上，从而达到车间生产的多个目标组合最优。

根据上述描述，本文作如下假设：1）一台设备同一时刻只能加工一个工件；2）若某一工件加工的上一道工序加工完毕后，对应的设备处于空闲状态，则立即开始加工下一道工序；3）工件在每台设备上的加工时间、装卸时间都确定，并都作为加工时间计算；4）工序在每台设备上的调整时间已知；5）工件加工一旦开始，就不能中断，除非设备出现故障；6）所有设备一开始均处于正常状态，即最初不存在故障设备；7）设备的故障率是通过长时间对设备的观测和维护所到的统计值，数据真实可靠；8）同一个工件，只有在上一道加工工序结束后才能进行下一道工序；9）工件的加工顺序不能改变。

1.2 目标函数

1）最大完工时间最小：

2）总延期时间最小：

3）总提前期时间最小：

4）总生产成本最低：

5）设备总负荷最小：

6）单台设备的最大负荷最小：

7）工件搬运次数最少：

约束条件如下：

其中，式(8)表示：在同一时刻任意工件的某一工序只能由一台设备加工；式(9)表示：同一工件的下一道工序的开工时间必须大于或等于该工件上一道工序的结束时间；式(10)表示：任意工件的结束时间大于等于该工件的开始时间、加工时间以及调整时间之和；式(11)表示：任意设备上新任务的开始必须在上一任务结束之后；式(12)工件的最后完工时间的；式(13)同一工件前后加工工序在同一设备的约束。

2 算法设计

由于车间调度问题属于NP-hard难题，每个目标之间存在复杂的关系，而且属于非线性优化模型，传统优化方法计算难度较大，因此本文采用一种基于双层（加工工序和加工设备）编码的改进遗传算法求解该问题。与传统遗传算法相比，确保染色体包含信息的全面性和完整性，同时采用最优保存策略、锦标赛选择、序值以及拥挤距离选择的方法，选择种群个体中适应度较高的遗传给下一代。交叉和变异操作均采用随机的两点交叉和变异。为了保证下一代种群中个体的多样性和防止搜索解陷入局部最优解的循环中，本文将适应度函数通过线性尺度转换方法。

2.1 染色体编码

本文采用基于加工工序和加工设备的两层编码的方式对染色体进行编，确保染色体包含信息的全面性和完整性。染色体编码采用整数编码，每个染色体长度为（n表示加工工件数，Ni表示第i个工件的工序数）。染色体分为两部，前半部分表示工件的加工工序，后半部分表示加工工件的加工工序所对应的加工设备顺序。

2.2 适应度函数

本文把适应度函数与目标函数的转化关系式定义如下：

在传统遗传算法的实际操作中会出现某一代中有一部分个体的适应度值很高，是到目前为止所有种群中适应度最高的个体，但是这些个体未必就是待优化问题的最优解或者近似最优解，而可能是解空间中的局部最优解。当出现这种情况时，如果仍然按照原种群中个体适应度函数来确定个体是否遗传到下一代中，就会出现从下一代开始，以后各代的个体几乎都不会改变。因为从上一代开始，在进行选择操作时，由于种群中适应度较高的个体会排斥适应度较低的个体，所以，以后每一代种群中适应度较高的那些个体占据种群的绝大部分。根据个体进化规则和选择操作中最优保存策略，这些适应度较高的个体直接遗传给下一代。所以，这种个体进化会使种群基因的多样性减小，甚至会出现上一代和下一代个体完全重合，这样就会使搜索解停留在某一局部最优点上。本文对某些适应度较高的个体进行人为的修订，降低其适应度，减小与其他个体适应度的差异，限制这些个体的遗传代数，增加适应度较小的个体被选择遗传的概率，从而增加种群基因的多样性，来避免这一现象的发生，达到使搜索解跳出局部最优点的约束。

本文对适应度函数采用线性尺度转换方法，转换公式如下：

其中，F为原适应度函数，F'为转换后的适应度函数，a，b为转换系数，一般c的取值范围是1.2～2，本文取1.15，为所有个体适应度的平均值，Fmax为所有个体中适应度最高个体的适应度值。

2.3 选择操作

本文采用MATLAB工具箱中的锦标赛选择函数（Selection tournament），采用最优保存策略，通过计算个体的序值和拥挤距离，选择种群中序值较小的个体遗传给下一代，当种群中两个个体的序值相同时，为了保持种群个体基因的多样性，选择拥挤距离大的个体遗传给下一代。当种群中个体的序值和拥挤距离都相等时，选择子目标中权系数较大的个体。通过多层次的比较、分析逐步对个体进行适应度排序，淘汰适应度小的个体，选择种群个体中适应度较高的遗传给下一代。

2.4 交叉操作

种群中的个体通过按一定的交叉概率，将染色体上的基因随机的交叉，得到新的个体，增加了种群基因的多样性。随机从种群中选择两个染色体，根据染色体编码的方法，先取出染色体的前半部分，其长度为，采用双点交叉的方法，随机的设定两个交叉点进行交叉操作。交叉后会出现某些工件的工序多余，某些工件的工序缺失，因此，需要按照原有基因将交叉后的基因对应的设备顺序进行调整。

2.5 变异操作

2.6 解码操作以及终止代数的确定

本文采用的染色体解码方法是全自动动解码方法。对于给定的一个染色体S而言，先计算其基因个数，然后取其基因的前半部分，根据解码公式进行解码。例如染色体S[3214132423431224]，共有16个基因，因为采用的是基于加工工序和加工设备的两层编码方式，所以取其基因的前半部分，共有8个基因分别为[32141324]。从上述基因中可以看出有4种工件，工序总数为8，分别根据下面程序进行解码。

2.7 改进遗传算法

传统的遗传算法采用的是隐性精英解保留策略，虽然保证了种群个体基因的完整性，但是在求解多目标问题的时候，可能会使Pareto解集出现过早收敛的现象。本文对Pareto解集采用改进的是三层评判标准的选择策略，首先通过计算序值，其次计算拥挤距离，最后根据各目标的模糊评价决策得到的综合评价指标进行排序，选择最优的Pareto解集。改进的遗传算法流程图如图1所示。

图1 改进的遗传算法流程图

3 实例分析

本文以大连市某企业空调制造车间为例，该车间某一时刻的10个工件需要在10台设备上加工，每个工件都要经过6道加工工序，具体数据如表1～表5所示：

表1 工序可选设备表

表2 工序加工时间表

表3 工件的原材费用表

表4 工件交货日期表

表5 设备单位时间加工费用表

本文的遗传算法参数为：种群中个体数目500，种群进化代数500，种群代沟0.8，交叉概率0.6，变异概率0.1。

经计算所得，传统遗传算法得到的pareto解集中最优解对应的最小加工时间为60分钟。

采用基于最优保存策略、序值排序、拥挤距离计算、综合指标排序、适应度函数转化以及工件加工工序和设备的两层编码方式的改进遗传算法的实例测试如图2和图3所示。

图2 采用改进遗传算法的种群解的变化

图3 采用改进遗传算法的零件加工甘特图

由于篇幅有限，本文只摘取6组比较优越的pareto解，如表6所示，然后通过AHP综合评价选择最佳的调度方案。各子目标的权重为：ω=（0.358， 0.2003，0.0872，0.2396，0.0461，0.0257，0.0431）T，最终选择调度方案3。

表6 pareto解集

经计算所得的，改进遗传算法得到的pareto解集中最优解对应的最小加工时间为53分钟。根据计算结果可知，改进后的遗传算法的综合评价指标比改进前的优越。所以本文的调度方案更加适应解决离散车间多目标调度问题。

本文对车间的设备进行环形布局优化，建立如下数学优化模型。

其中，wij为设备i到设备j的当量物流量，是根据工件加工工艺线路转化的，例如，工件1的加工工艺路线为3-1-2-7-8-5，则 w31= w12= w27= w78=w85=1。xij为0,1变量，如果设备i在生产线上的位置排在设备j前，取值为1，否则为0。目标函数(19)在保证所有工件加工完的前提下，使整个车间的逆向搬运物流量最小；约束(20)设备相对位置的约束，约束(21)确保设备位置在传递过程中不出现矛盾。

经计算得到图4加工设备环形布局图，其中(1)和(2)两个方案工件总的逆向搬运物流量都为17，总的无效搬运量都为237。与优化前的车间布局（设备摆放位置为1-2-3-4-5-6-7-8-9-10）相比，总的无效搬运量从270减为237。

4 结束语

本文首先采用传统的遗传算法对空调制造车间10×10的案例进行求解，然后采用本文所提出的改进的遗传算法对上述给定的案例进行求解，通过对比两个方案的综合评价指标，可以证明本文提出的改进的遗传算法在求解同一车间调度问题中的优越性。最后根据车间调度确定的工件加工工艺路线，实现了对现有车间制造设备进行环形布局优化。

图4 加工设备环形布局图

[1]谢皓,应保胜,袁波.基于遗传算法的路径柔性作业车间调度优化[J].武汉科技大学学报,2012,35(6):465-468.

[2]王硕,顾幸生.基于改进蚁群算法的作业车间调度[J].青岛科技大学学报,2012,10(5):489-494.

[3]曹岩,雷蕾,房亚东.蚁群算法在离散型车间派工中的应用[J].西安工业大学学报,2011,12(7):611-615,643.

[4]刘烽,游海,丁一钧,杨涛,聂电开.基于NSGA2算法的混合流水车间多目标调度问题研究[J].电脑编程技巧与维护,2012,(24):86-87.

[5]杨开兵,刘晓冰.流水车间成组工件调度问题的多目标优化算法[J].计算机应用,2012,12(12):3343-3346.

[6]Rubiyah Y,Marzuki K,Gan T H.Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm[J].Applied Soft Computing,2013,11(8):5782-5792.

[7]曾强,沈玲,杨育,宋红娜.多目标等量分批柔性作业车间调度集成优化方法[J].计算机工程与应用,2012,48(16):237-243.

[8]Cowling P I,Johansson M.Using real-time information for effective dynamic scheduling[J].European Journal of Operational Research,2012,139(2):230-244.