邹泽桦,曾九孙,蔡晋辉

(中国计量大学 计量测试工程学院,杭州 310000)

改进遗传算法求解柔性作业车间调度问题

邹泽桦,曾九孙,蔡晋辉

(中国计量大学 计量测试工程学院,杭州 310000)

针对柔性作业车间调度问题中最大完工时间、机器最大负荷和总机器负荷三项性能指标，提出一种改进的自适应交叉和变异的混合遗传算法;在基本遗传算法染色体编码的基础上，设计一种基于海明距离的调度个体差异判别方法，并通过自适应交叉阈值和动态变异概率计算提高遗传算法整个种群调度个体的多样性，防止算法过早的进入早熟;在遗传算法进化期间，对每个调度个体的进化采用变邻域搜索算法，扩大调度个体的邻域搜索范围;最后，使用文献中相同的调度实例将文章的计算结果与其它文献中的测试结果进行比较，验证了所提出的算法的可行性和有效性。

柔性作业车间调度; 海明距离; 遗传算法; 变邻域搜索算法

0 引言

柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)是传统作业车间调度问题(job-shop scheduling problem，JSP)的扩展，由Bruker和Schile[1]于1990年首次提出。目前，对柔性作业车间调度问题的算法研究比较普遍。如Liao等[2]采用禁忌搜索法；Birgin等[3]采用列表排程和集束搜索相结合的方法；安玉伟[4]设计了一种基于拉格朗日松弛的分解方法，在确定计划问题后再对调度问题求解；黄敏[5]等在考虑设备带有恶性条件的情况下使用嵌套分割算法与单亲遗传算法相结合的方法。同时，将排程算法应用到工厂的实例也越来越多，郑克波[6]通过遗传算法实现对某轴承企业的生产排程；王犇[7]采用TOC约束理论实现对飞机复合材料的生产排程；王延斌[8]先采用蚁群算法解决工序的设备选择问题之后根据启发式规则解决设备上各工序加工的先后顺序等。其中，遗传算法由于鲁棒性与通用性好、全局搜索能力强的特点得到了广泛应用，利用遗传算法求解FJSP的例子也较多，如廖珊等[9]设计一种自适应的遗传变异算子，改善了遗传算法后期停滞不前的现象；Teekeng等[10]设计了一种模糊轮盘赌选择与配对方法改进遗传算法的选择操作；Ishikawa等[11]采用分层混合空间遗传算法方法在设备和工序两个层次空间下使用遗传算法，交替优化。尽管这些方法在计算效率等方面较传统方法有了较大改进，但以上文献多在初始化和选择阶段对遗传算法进行改进而遗传算法过早进入早熟与局部搜索能力弱的缺点依旧存在。

为在遗传算法进化的同时保持种群个体的多样性，本文在FJSP的基础上提出了一种自适应交叉和变异方法。在改进当前遗传算法的同时，设计了三张邻域搜索结构，将每一代种群的调度个体作为变邻域搜索的初始解，设计了具有3种结构集的变邻域搜索方法，在算法进化期间每个调度个体都可以搜索自己邻域范围内的最优解，从而在防止早熟的同时加快收敛速度。

1 柔性作业车间调度问题FJSP描述

柔性作业车调度问题可以描述为:n个工件J={J1,J2,J3,......Jn}要在m台机器M={M1,M2,M3,...，Mm}上加工。每个工件相互独立且包含一道或多道工序，工序加工顺序及工艺路线则是根据每个工件的自身情况而确定的.调度目标是为每个工件的各个工序选择最合适的机器、并且确定每个工件的各个工序的在其所属的机器上的加工开始时间，使整个系统的某些性能指标达到最优或近最优状态。如表 1所示即为一个柔性作业车间调度实例。

表1 柔性作业车间作业工件工序加工时间表

注：J1标示工件1，O11标示工件1的第1道工序，符号‘-’标示该工序无法在相应机器上加工。

在FJSP的求解过程中，需要一定的目标函数或者说评价指标来判断调度方案的优劣。下面列出了常见的几个评价指标：

最大完工时间最小:

(1)

式中,Cj表示各个工件的完工时间。

机器最大负荷最小:

(2)

式中，hj表示工件所包含的工序数量，Tijh表示工件j的h工序在机器i上的加工时间，xijh表示工件j的h工序是否选择机器i加工，1表示选择机器i加工，0表示不选择机器i加工。

机器总负荷最小:

(3)

以上几种性能指标比较常用，不同的情况下会有不同的生产调度要求，从而选择不同的调度策略，一般情况下会选择最大完工时间最小作为调度目标，目的是尽可能早的完成加工任务。在保证最大完工时间最小的同时，也会考虑平衡各机器负荷，使各机器总负荷最小，最终使整个调度目标在时间的度量下达到最优或近最优。

2 自适应混合遗传算法设计

2.1 自适应遗传算法设计

遗传算法(genetic algorithm, GA)是对达尔文著《物种起源》的人工化种群模拟，最早在1975年由Michigan大学的Holland[12]教授开始对其进行系统化的研究。

2.1.1 编码

在染色体编码方面，本文采用文献[13]中所采用的分段编码的方式，将染色体基因分为机器选择基因块与工序排序基因块两块。

机器选择基因块：该基因块长度为各工件所有工序之和OALL,每个基因位用机器编号表示，每个基因位表示当前工序可选机器集中所选择的机器号。

图1 机器选择基因块

工序排序基因块：该基因块长度为各工件所有工序之和OALL. 每个基因位用工件号表示，工件号在此基因块中出现的次数等于工件所包含的工序数量，对于第h次出现的工件号，表示该工件第h道工序，以表1调度实例为例的工序排序基因块如图2所示，工序加工顺序O11-O31-O21-O32-O12-O33-O22。

图2 工序排序基因块

2.1.2 初始化种群

为保证初始种群的多样性，每个调度个体的机器选择基因块和工序排序基因块均采用随机初始化的方式初始化染色体的各个基因位。

2.1.3 选择

本文首先采用最大完工时间最小即公式(1)的指标来对调度个体的适应值进行评价，即个体适应值小的为优良个体。当两调度个体的最大完工时间相同时，再考虑机器最大负荷即公式(2)和总机器负荷即公式(3)。

在计算完每个调度个体的适应值后，采用精英保留策略和锦标赛法相结合的方法进行个体选择。

2.1.4 交叉

交叉操作在遗传算法属于关键步骤。为判断两个编码染色体之间的差异程度，本文提出一种基于海明距离的调度个体差异判别方法。海明距离(hammingdistance)指相同长度的编码在同一位置上不同码值的个数总和。

海明距离的确定：

Step1：判断两个父代调度个体中机器选择基因块中相同工序不同机器选择基因的个数总和；

Step2：通过对工序排序基因块中基因的解码，得到各工序的顺序号。

表2 工序排序基因块海明距离计算

如表2所示，两个父代调度个体工序排序基因块分别是1-3-1-3-2-3-2，2-1-3-3-2-1-3通过对各工序的顺序计算得出工序排序基因块海明距离Hp为6；

Step3：将Hm和Hp相加得到两个父代调度个体的海明距离H。

确定海明距离后，通过与交叉阈值的比较，从而确定两调度个体是否进行交叉。本文提出的交叉阈值公式为：

(4)

式中,TALL为染色体总长度，即两倍的工序总和，g为当前进化代数，G为总群进化总代数。交叉阈值过大将会导致种群进化缓慢，而过小则极易使种群陷入早熟。由交叉阈值公式(4)可知，在种群进化初期，两个父代调度个体的交叉阈值接近于染色体总长度的三分之二，只有两个父代调度个体之间的海明距离达到交叉阈值时才可进行交叉，在进化后期，交叉阈值约为染色体总长度的三分之一，这也与后期调度个体间差异逐渐变小的状况相符合。

在两个父代调度个体的海明距离达到交叉阈值后，根据编码规则，交叉方法分为机器选择基因块交叉和工序排序基因块交叉。在机器选择基因块交叉中，确定一定数量的工序，将父代调度个体一中剩余工序的机器选择号与父代调度个体二中剩余工序的机器选择号进行交换；在工序排序基因段交叉中，确定一定少于工件总数数量的工件号，将两个父代调度个体中剩余工件号的基因位进行互换。

2.1.5 变异

根据不同调度个体的交叉操作结果和其适应值大小，本文提出一种自适应变异概率计算方法。如表 3所示，对调度个体适应值优于种群平均适应值(f

表3 变异概率选择表

表3中，xH表示该个体是否参与交叉的标志，当xH=1时，表示该个体参与交叉；否则，该个体没有参与交叉。Pmax和Pmin为最大变异概率和最小变异概率，为防止过大的变异概率破坏种群调度个体的优良模式，这里分别取0.1和0.01，favg即为种群平均适应值，f为该个体适应值，fbest为种群中最佳适应值，fworst为种群中最差适应值。

当调度个体满足变异概率要求时，则随机产生一新个体替换当前变异个体。

2.2 变邻域搜索算法设计

在自适应遗传算法进化期间加入变邻域搜索算法，平衡算法在搜索过程中的广泛性和集中性。本文结合文献[14]不同的邻域搜索结构，设计了3种邻域搜索方法。

2.2.1 邻域结构VNS1

邻域结构VNS1采取随机改变工序排序基因块中某一工序排序的方法，具体操作步骤为：

Step1：设置邻域结构VNS1最大循环次数Gmax，并将初始化为1；

Step2：在工序排序基因段中随机选择一个工序，若该工序在满足同一工件工序约束的前提下可以随机跟处于同一设备的加工工序交换位置；

Step3：将G设置为G+1，若G

2.2.2 邻域结构VNS2

在邻域结构VNS2中，随机选择两工件号，交换这两个工件号所对应的所有工序，从而改变工序排序基因块中工序的加工顺序，具体操作步骤为：

Step1：从所有工件号中随机选择两个；

Step2：提取工序排序基因块中相对应的两个工件的所有工序号，若两工件的工序数量相等，则将对应工序交换即可，若两个工件的工序数量不相等，则先将两者中工序数较少的工件A工序依次移到工序数较多的工件B基因位置上，然后在空缺的基因位上填入工件B的工序，产生新的邻域解。

2.2.3 邻域结构VNS3

在邻域结构VNS3中，采取改变机器选择基因块中某一基因所选机器的方法，具体操作步骤为：

Step:1：设置邻域结构VNS3最大循环次数Smax，并将设置为1；

Step2：在机器选择基因块中随机选择一个基因，判断该基因所对应的工件工序，然后依次选择该工序可选加工机器集中的机器，选取可使适应值最小的机器。

Step3：将S设置为S+1，若S

2.3 算法整体流程

当自适应遗传算法在执行完交叉变异操作后为扩大每个调度个体的局部搜索范围，结合以上3种变邻域搜索，具体流程如下：

Step2：令n←1，l←1；

Step3：若l=1，则对x进行VNS1邻域结构变换(Gmax=2)；若l=2，则对x进行VNS2邻域结构变换；若l=3，则对x进行VNS1邻域结构变换(Gmax=4) ；若l=4，则对x进行VNS3邻域结构变换(Smax=1)；若l=5，则对x进行VNS1邻域结构变换(Gmax=6) ；若l=6，则对x进行VNS3邻域结构变换(Smax=2)，进过相应邻域结构变换后的解为x′；

Step5：若n

自适应混合遗传算法总体流程如图 3所示。

图3 自适应混合遗传算法总体流程图

3 实验结果及分析

为比较算法的寻优性能，分别采取8个工件8台机器的部分柔性作业车间调度问题(8×8)、10个工件10台机器(10×10)的和15个工件10台机器(15×10)的完全柔性作业车间调度问题的FJSP实例进行测试。大邻域搜索次数，最大迭代次数。当算法寻求8×8P-FJSP实例的最优解时，其收敛曲线如图4所示，算法在进化到第十代即可寻得最大完工时间的最优解。

图4 8×8 P-FJSP实例的收敛曲线

表 4列出了本文所提出的自适应混合遗传算法与其他算法在8×8P-FJSP调度实例、10×10和15×10T-FJSP调度实例问题上3个目标函数：最大完工时间最小，机器最大负荷最小和机器总负荷最小的最优值比较。表中比较对象分别为混合目标模拟退火算法(MOSA)[15]、平行变邻域算法(PVNS)、粒子群与模拟退火混合算法(PSO+SA)[16]以及在预先选择设备下使用遗传算法(AL+CGA)[17]。从表 4可以看出，本文所提出的自适应混合遗传算法取得了较好的计算结果。在求解8×8P-FJSP调度实例时，在少许增加的情况下，和的目标值都等于或优于其它4种算法。在求解10×10F-FJSP调度实例时，与Xia的方法相比，在和的目标值相等的情况下，的目标值缩短了2小时，与Kacem的方法相比，在的目标值相等，的目标值增加1小时的情况下，的目标值缩短了3小时。在求解15×10P-FJSP调度实例时，在的目标值和 的目标值与Xia和Kacem的方法相等的情况下，的目标值分别缩短了1小时和13小时。图 5、图 6和图 7分别表示8×8P-FJSP调度实例问题、10×10和15×10T-FJSP调度实例问题相应的甘特图。实验结果表示本文所提出的自适应混合遗传算法在求解柔性作业车间问题时可以取得较好的调度解。

图5 8×8 P-FJSP调度实例解

图6 10×10 T-FJSP调度实例解

图7 15×10 P-FJSP调度实例解

4 总结

本文针对FJSP柔性作业车间调度问题，对现有设备选择基因块和工序排序基因块进行分析，提出了一种基于海明距离个体间差异判别方法，将两父代个体间的海明距离与交叉阈值进行比较后决定是否进行交叉操作，而父代个体是否进行交叉操作也将影响其变异概率，有效防止相似父代个体交叉所导致早熟的出现。同时，针对遗传算法局部搜索能力较弱的问题，改进了3种邻域搜索方法，加强了遗传算法的局部搜索能力。最后通过3个调度实例的实验比对，验证了所提出的方法可行性和有效性。

[1]BruckerP,SchilieR.Job-shopschedulingwithmulti-purposemachines[J].Computing, 1990, 45(4): 369-375.

[2]LiaoLM,HuangCJ.Tabusearchheuristicfortwo-machineflowshopwithbatchprocessingmachines[J].Computers&IndustrialEngineering, 2011, 60(3): 426-432.

[3]BirginEG,FerreiraJE,RonconiDP.Listschedulingandbeamsearchmethodsfortheflexiblejobshopschedulingproblemwithsequencingflexibility[J].EuropeanJournalofOperationalResearch, 2015, 247(2): 421-440.

[4] 安玉伟, 严洪森. 柔性作业车间生产计划与调度集成优化求解策略[J]. 自动化学报, 2013, 39(9): 147-1491.

[5] 黄 敏, 付亚平, 王洪峰, 等. 设备带有恶化特性的作业车间调度模型与算法[J]. 自动化学报, 2013, 41(3): 551-558.

[6] 郑波克. 基于MES的轴承制造企业生产排程优化及算法研究[D]. 洛阳：河南科技大学, 2012.

[7] 王 犇. 飞机复合材料MES计划排程系统研究与开发[D]. 南京：南京航空航天大学, 2011.

[8] 王延斌. 面向模具的制造执行系统关键技术研究[D]. 哈尔滨：哈尔滨工业大学, 2007.

[9] 廖 珊, 翟所霞, 鲁玉军. 基于改进遗传算法的柔性作业车间调度方法研究[J]. 机电工程, 2014, 31(6):729-733.

[10]TeekengW,ThammanoA.Modifiedgeneticalgorithmforflexiblejob-shopschedulingproblems[J].ProcediaComputerScience, 2012, 12(12): 122-128.

[11]IshikawaS,KubotaR,HorioK.Effectivehierarchicaloptimizationbyahierarchicalmulti-spacecompetitivegeneticalgorithmfortheflexiblejob-shopschedulingproblem[J].ExpertSystemswithApplications, 2015, 42(24): 9434-9440.

[12]HollandJH.Adaptioninnaturalandartificialsystems[M].AnnArbor:TheUniversityofMichiganPress, 1975.

[13] 张国辉. 柔性作业车间调度方法研究[D]. 武汉：华中科技大学, 2009.

[14]YazdaniM,AmiriM,ZandiehM.Flexiblejob-shopschedulingwithparallelvariableneighborhoodsearchalgorithm[J].ExpertSystemswithApplications, 2010, 37(1): 678-687.

[15]KaplanogluV.Anobject-orientedapproachformulti-objectiveflexiblejob-shopschedulingproblem[J].ExpertSystemswithApplicationsAnInternationalJournal, 2016, 45(C): 71-84.

[16]XiaW,WuZ.Aneffectivehybridoptimizationapproachformulti-objectiveflexiblejob-shopschedulingproblems[J].KongzhiYuJuece/control&Decision, 2005, 48(2): 409-425.

[17]KacemI,HammadiS,BorneP.Pareto-optimalityapproachforflexiblejob-shopschedulingproblems:hybridizationofevolutionaryalgorithmsandfuzzylogic[J].MathematicsandComputersinSimulation, 2002, 60: 245-276.

Improved Genetic Algorithm for Flexible Job-shop Scheduling Problem

Zou Zehua, Zeng Jiusun, Cai Jinhui

(China JiLiang University, Hangzhou 310000, China)

To deal with the flexible job-shop scheduling problem, a self-adaptive hybrid genetic algorithm is proposed by considering the performance index of maximum completion time, maximum machine load and total load. On the basis of the chromosome coding of basic genetic algorithm for the flexible job-shop scheduling problem, a new method for discriminating differences between scheduling individuals is designed based on the Hamming distance, and the population diversity is improved by the self-adaptive threshold value for the operation of crossover and the dynamic calculation of the probability of the operation of the mutation to prevent premature convergence. During the evolution of the genetic algorithm, each individual executes variable neighborhood search to enhance the local search of genetic algorithm. The self-adaptive and hybrid genetic algorithm is tested on examples taken from the literature and compared with their results. The computation results show that the self-adaptive and hybrid genetic algorithm is feasible and effective.

flexible job-shop scheduling; Hamming distance; genetic algorithm; variable neighborhood search

2016-11-02；

2016-11-26。

国家自然科学基金(61203088,61673358)。

邹泽桦(1991-)，男，浙江绍兴人，硕士研究生，主要从事智能制造、智能生产方向的研究。

曾九孙(1982-)，男，浙江杭州人，副教授，硕士研究生导师，主要从事信号分析与处理，统计过程控制方向的研究。

1671-4598(2017)04-0167-05

10.16526/j.cnki.11-4762/tp.2017.04.046

TP18

A

蔡晋辉(1974-)，男，浙江杭州人，教授，硕士研究生导师，主要从事检测技术与自动化装置方向的研究。