余鹏飞，袁逸萍，李晓娟

(新疆大学 机械工程学院，乌鲁木齐 830047)

基于混合遗传算法的多目标柔性作业车间调度问题研究*

余鹏飞，袁逸萍，李晓娟

(新疆大学 机械工程学院，乌鲁木齐 830047)

针对柔性作业车间调度问题，提出一种改进的遗传算法，该算法考虑车间生产实际，使交货期短、成本降低、生产效率提高、资源利用率提高等建立多目标优化模型。对传统遗传算法进行一系列改进，在遗传算法的基础上，改进编码方式和遗传算子，结合精英保留策略和小生境技术，使算法的收敛性和多样性进一步优化，采用权重系数变化法计算染色体的适应度。仿真分析表明， 提出改进后的混合遗传算法能有效解决柔性作业车间多目标调度优化问题。

柔性作业车间；多目标调度；遗传算法

0 引言

近十年以来，流水车间调度和作业车间调度得到了较充分的研究，然而对于求解柔性作业车间fJSSP并设计相应的调度算法的却不多。一般来说，柔性调度问题本身比那些没有柔性加工路径的问题更加复杂；随着目标的增多，问题的复杂性也会进一步增加。多目标柔性调度是一种具有挑战性的研究方向，而解决问题的关键是如何提高调度方法的效率。

针对柔性作业车间的调度问题，文献[1-2]提出了基于模糊逻辑和混合算法混合的基础上的Pareto方法以解决fJSSP，该算法利用了模糊逻辑的的知识表达能力和混合算法的自适应能力；文献[3-4]给出了基于GA和移动瓶颈法的混合算法，该算法使用双向量表示方法、先进交叉算子和变异算子以适应染色体的特殊结构和问题的特征；文献[5]开发了一种仿真模型，并使用ACO和局部搜索对模型进行改进；文献[6]采用集成免疫算法和GA的多目标免疫遗传算法求解柔性调度问题，并分析了算法的收敛性。文献[7]利用GA逼近目标函数为最大加工完成时间和最大延迟时间的问题Pareto最优前端。文献[8]利用GP优化复合调度规则的参数和算子空间。以上方法多为单目标柔性作业车间优化问题，而多目标优化的相关文献却不是很多，笔者提出多目标柔性作业车间优化模型，基于混合遗传算法提出一种新的多目标优化方法。

1 问题描述

有n个工件在m台机器上加工，工件集合为J{Ji|i=1,2,…,N}，工件Ji包含hi道工序，一道工序可由多台机器加工，MSij为Ji工件在工序hi的可用机器集合，MSij⊂{1,2,…,m},oijk为i工件的j道工序在机器Mk上进行加工，pijk为i工件的j道工序的加工所需时间，1≤i≤n,1≤j≤hi,1≤k≤m。

fJSSP包含以下两个问题：确定各工序所对应的机器使得总的加工时间最合理；在给定的约束条件下， 完成加工任务使目标函数最优。通过表格实例来描述fJSSP，pijk为表格中的数字，“-”代表oij不能在Mk上进行加工。表1描述了一个3×4 fJSSP。

表1 3×4 fJSSP描述

为了简化问题，作如下假设：①所有机器在t=0时刻都在用；②所有工件在t=0时刻都可被加工；③所有工件的工艺计划都是固定不变的；④在每一台机器上加工的每一道工序的时间是确定的；⑤同一时间，每台机器只能加工一道工序；⑥加工是非抢占式的。

分析fJSSP模型，将该种问题分为两类：

(1)完全fJSSP：对于oij，若|MSij|=m，即任意工件Ji的工序可在所有的机器上加工。

(2)部分fJSSP：对于oij，若|MSij|

多目标优化模型建立应该符合企业生产实际，使交货期短、成本降低、生产效率提高、资源利用率提高等，为此从上面四个方面建立优化目标。

(1)

(2)

(3)

(4)

(5)

(6)

约束条件：

(7)

(8)

pjik≥0,pjok=0

(9)

STijk≥0,STiok=0

(10)

STij≥0,STio=0

(11)

(12)

(13)

2 基于改进混合遗传算法的多目标优化方法

柔性作业车间多目标优化方法通常有三类，即Pareto优化方法、加权优化法和交互优化方法。本文采用Pareto最优解的思想，基于遗传算法提出多目标柔性作业车间的优化算法。混合算法的思路是，在遗传算法的基础上，结合精英保留策略和小生境技术，对遗传算法进行改进，使算法的收敛性和多样性在理想值。具体的流程图如图1所示。

图1 多目标柔性作业车间的优化算法流程图

(1)编码和解码

fJSSP优化采用基于工序的编码方式，每个染色体用n×max{hj}个自然数组成，其中各工件均出现max{hj}次。如上述3×4 fJSSP例子，染色体的实例为2 1 1 1 1 1 3 3 3。

对此本文采用间隙挤压法产生活动调度。首先给出两个定义。

定义1：机器顺序JM。JM(i,j)表示加工工件Ji的第j道工序的机器号，JM(i,.)表示工件Ji的所有工序按优先顺序加工的各机器号的排列。在fJSSP中，任意工件Ji的第j道工序的可用机器不止一个，所以该排列的长度等于(maxhj)×m(j=1,2,…,n)，每道工序的可用机器集用m个机器号表示，称为一个子片段。部分fJSSP中部分机器不可用时，用0补齐m个子片段(机器编号从1开始)。当各个工件的总的工序的数值不相等时，将该工件的最大工序数作为片段数，而对于那些工件的工序数值比最大工序值小的工件，按照以上规则排列出机器序号，接着补齐数全为0的(maxhj)-hj个片段，从而构成(maxhj)×m×n的二维矩阵。对于前面描述的3×4 fJSSP例子：

(14)

定义2：加工时间矩阵T。T(i,j)为工件Ji在机器Mi上的加工时间。对于fJSSP，T(i,j)与JM(i,j)一一对应，当JM(i,j)为0时，T(i,j)也为0。描述的3×4fJSSP例子的加工时间矩阵为：

(15)

间隙挤压法的解码算法如下：

令k[i]=1,2,…,n；

Fori=1 ton×max{hi}

得到加工工件Ji的机器号JM(i,k[i])；

令k[i]=k[i]+1；

把Ji工件在机器JM(i,k[i]-1)的工序以最早允许时间加工。从刚开始加工到当前时刻，对各个机器有加工空闲的进行判断，看是否能将该工件插入加工。判断能够插入，在对应的加工空闲的机器中将工件插入加工，并且将机器上的加工队列重写。若不能插入加工，则将此工件排在该机器的队尾进行加工。

End for

算法中，工件Ji能在机器空闲时间段[t1,t2]插入加工的条件为：

max(t(i),t1)+pti≤t2

(16)

其中，时间t(i)为Ji工件能够加工的最早时间；pti是该工件在机器上加工当前工序的时间。按照这种解码方法，使得那些在某些时间段空闲的的机器继续工作，各个机器上的加工任务安排的紧凑，总的加工时间也得到缩短。

(2)适应度计算

适应度计算其实就是目标函数的不断优化问题。对目标函数的优化，本文权重系数变化法计算个体的适应度：对于每代个体，在该个体的各个目标按照一定的比例给予不同的权值，将各个目标相加得到该个体的适应度。计算公式如下：

(17)

(3)遗传操作

采用轮盘赌的选择方法。在遗传操作中，因为交叉操作和变异操作致使优秀个体丢失，所以我们使适应度高的优秀个体不参与交叉操作和变异操作，直接跳过这些操作在下一步代替那些较劣的个体。

在Pareto最优解的多样性方面，在遗传操作过程当中，用小生镜技术解决适应度很接近的个体。在Hyun[9]基础上对小生镜技术进行改进，提高解的多样性。某个个体所在的小生境域的定义为：把个体作为中心，个体边界的计算公式见式(18)，遗传的概率与小生镜阈的概率有关，密度越大遗传下去的概率越小。

(18)

式中，maxflt和minflt分别是混合到第t代时第l个目标的最大值和最小值，M为目标个数，N为种群规模，l=1,2,…,M。

仿真分析表明，发现边界条件不精确，可能造成最优解的丢失，因此不断进行仿真实验，对边界条件不断修正，最终的公式如下：

(19)

采用线性次序交叉方式。采用互换操作变异方法，随机交换染色体中两个不同的基因的位置。

3 仿真分析

运行环境：在处理器为Intel(R)Gore(TM) 2.3GHz、内存为2G的WIN7操作系统下，利用Matlab2012b进行编程。通过与文献[9]的对比分析得出本文方法的优劣。具体比较数据如表2所示。

表2 8*8问题不同调度方法的比较

从表2可以看出，本文方法的最小制造周期比表中其它方法降低了，总的负荷优化不是很大，但是最大负荷相比其它方法降低了，总体来说算法的性能得到了提高。因此，本文的算法对解决多目标柔性作业车间的调度问题有所改进。下面通过一个具体的例子来分析本文方法的可行性和合理性。

采集某作业车间的生产数据并进行处理，已知有该车间有6台机器加工6个工件，每个工件具有10道工序的fJSSP，并对其进行仿真实验。混合GA的参数：种群大小N=100，交叉概率pc=0.6，变异概率pm=0.1，最大代次数为3000。调度问题的原始数据和已知参数见文献[9]，已知参数如表2，为了简化，所有ηij均取0.001。对这6个目标同时进行优化，Pareto方法得出的解在空间形成一个超曲面，解集通常不能用表直接表示，因此，我们近似Pareto解集，得到20个Pareto最优解，如表3所示。

表3 近似Pareto解集

续表

从表3可以看出，近似Pareto解集包含多组最优解，决策者可以结合车间具体的生产实际选择最优解。

4 结束语

基于混合遗传算法的多目标柔性作业车间调度相对于传统作业车间调度问题更符合车间生产实际，具有更大优势，为柔性作业车间的调度提供了理论指导和依据。本文对遗传算法进行了一系列的改进，包括遗传操作以及用小生镜技术提高解的多样性等。通过与其它方法进行对比分析，证明本文提出基于混合遗传算法的多目标柔性作业车间调度方法对柔性作业车间调度问题进行优化求解时的合理性与正确性，最后仿真实例验证了算法的有效性。

[1] Kacem I,Hammadi S, Borne P. Approach by localization and multi-objective evolutionary optimization for flexible job shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics, PART C,2002, 32(1): 1-13.

[2] Kacem I,Hammadi S, Borne P. Pareto-Optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation,2002,60:245-276.

[3] 吴秀丽,孙树栋,余建军,等. 多目标柔性作业车间调度优化研究[J]. 计算机集成制造系统,2006,12(5):731-736.

[4] Gao J, Gen M, Sun L,et al. A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems[J]. Computers and Industrial Engineering, 2007,53:149-162.

[5] Xing L N, Chen Y W, Wang K W. Multi-objective flexible job shop schedule: Design and evolution by simulation modeling[J].Applied Soft computation,2009,9:362-367.

[6] Wu X L, Sun S D, Niu G G,et al. The performance analysis of multi-objective immune algorithm for flexible job shop scheduling[J].International Federation for Information Processing,2006,25(12):1480-1483.

[7] Vicot G, Billaut J C, Esswein C. A genetic algorithm for a bicriteria flexible job shop scheduling problem[C]. 2006 International Conference on Service Systems&Service Manage-ment,2006:1240-1244.

[8] Tay J C, Ho N B. Evolution dispatching rules using genetic programming for solving multi-objective flexible job shop problems[J].Computers and Industrial Engineering, 2008,54(3):453-473.

[9] HYUN CJ，KIM Y，K1M Y K．A genetic algorithm for multiple objective sequencing problems in mixed model assembly Lines[J]．computers & operations Research，1998，25(7):675-690.

(编辑李秀敏)

ResearchofMulti-objectiveFlexibleJobShopSchedulingProblemBasedonHybridGeneticAlgorithm

YU Peng-fei, YUAN Yi-ping, LI Xiao-juan

(School of Mechanical Engineering ,Xinjiang University, Urumqi 830047,China)

Aiming at flexible job-shop scheduling problem, an improved genetic algorithm was proposed and the algorithm considering actual production in workshop and make delivery time short, reduce cost, improve efficiency and optimizing resource utilization multi-objective optimization model is established. A series of improvements on traditional genetic algorithm on the basis of genetic algorithm, improve the methods of coding and genetic operators, combined with elite reserved strategy and niche technology, make the algorithm convergence and the diversity of further optimization, the variation weight coefficient method to calculate the fitness of chromosomes. The simulation analysis shows that the proposed hybrid genetic algorithm can effectively solve the flexible job shop multi-objective scheduling optimization problem.

flexible job shop; multi-objective scheduling; genetic algorithm

TH186；TG506

：A

1001-2265(2017)09-0157-04

10.13462/j.cnki.mmtamt.2017.09.041

2016-12-09；

：2016-12-21

国家自然科学基金(51365054)；新疆维吾尔自治区自然科学基金(2014211A008)

余鹏飞(1991—)，男，河南信阳人，新疆大学硕士研究生，研究方向为工业工程，(E-mail)1512994226@qq.com。