王家海　吕程

摘要：针对理论上属于NP完全问题的车间离散调度问题，在传统的遗传算法搜索中融入模拟退火算法，同时按照一定的规则生成初始种群。采用机器码和工序码相结合的编码方式，以全局选择、局部选择以及随机生成的方式产生初始种群，同时针对遗传算法局部搜索能力较差、易出现早熟现象的缺点，考虑模拟退火算法提高全局优化概率搜索。仿真结果表明融合了模拟退火算法遗传算法性能具有更快的收敛性和寻优效果。

关键词：车间离散调度；遗传算法；模拟退火

中图分类号：TP301 文献标识码：A 文章编号：1007-9416（2019）01-0133-04

1 概述

FJSP问题是作业车间调度问题（JSP）的扩展[1]，其突出特点是同一个加工任务有多台加工设备可供调度选择。FJSP是典型的组合优化问题，更加接近实际的生产调度环境，但同时问题复杂度相对于JSP也更高，对于此类问题，传统的数学优化方法无法在相对有限的时间内求解，因此采用近年来兴起的智能优化算法成为了一个可行的解决方法。作为智能算法之一的遗传算法在此问题上得到了广泛的应用，Ho等[2]采将启发式算法与遗传算法结合，提出一种混合算法， Teekeng等[3]设计了一种模糊轮盘赌的种群选择操作廖珊[4]采用一种改进的GA算法，设计了自适应的选择、变异、交叉算子，李铁克[5]提出文化GA求解FJSP。

遗传算法虽然具有较强的全局搜索能力，但同时也存在着过早收敛、容易陷入局部最优、适应性较差等缺点。模拟退火算法具有较强的局部搜索能力，其不仅接受使目标函数变好的解，还能以一定的概率接受使目标函数变差的解，因此该算法具有跳出局部最优解的能力。可以发现，将模拟退火算法和遗传算法紧密结合起来，可以克服各自不足，提高算法寻优性能，从而取得更优解。

基于以上观点，本文在遗传算法的基础上将模拟退火算法融合，提出一种改进版的GA算法。

2 问题描述及数学模型

2.1 问题描述

柔性作业车间调度问题（FJSP）的描述如下：n个工件（J1，J2，…，Jn）要在m台机器（M1，M2，…，Mm）上加工；每一个工件包含一道或者多道工序；工序顺序是预先确定的；每道工序可以在多台不同的加工机器上进行加工；每道工序的加工时间随着加工机器的不同而不同；调度的目标是为每道工序选择出合适的机器，确定每台机器上各道工序的最佳加工顺序以及开工时间，使整个系统的某些性能指标达到最优。因此FJSP问题包含两个子问题：确定各工序的加工机器（机器选择子问题）以及确定各个机器上的加工先后顺序（工序排序问题）。

本文建立的调度问题模型包含了以下约束：（1）同一台机器在某一时刻只能加工一个工件；（2）同一工件的同一道工序在同一时刻只能被一台机器加工；（3）每个工件的每道工序一旦开始，加工便不能中断；（4）不同工件的工序之间没有先后约束，同一工件的工序之间有先后约束；（5）所有机器在t = 0时刻都可用，所有工件在t=0时刻都可加工；（6）同一工件不同工序的加工顺序和在不同机器上的加工时间都是固定的。

2.2 数学模型

定义以下符号：

n：工件总数；

m：机器总数；

i，e：机器序号，i，e=1，2，3，…，m；

j，k：工件序号，j，k=1，2，3，…，n；

hj：第j个工件的工序总数；

l：工序序号，l=1，2，3，…，hj；

Ojh：第j个工件的第h道工序；

Oijh：第j个工件的第h道工序在机器i上加工；

pijh：第j个工件的第h道工序在机器i上的加工时间；

sjh：第j个工件的第h道工序加工开始时间；

cjh：第j个工件的第h道工序加工完成时间；

L：一个足够大的正数；

Cj：每个工件的完成时间；

Cmax：最大完工时间；

Xijh：若工序Ojh选择机器i上加工，则Xijh=1，否则Xijh=0；

Yijhkl：若Oijh先于Oikl加工，则Yijhkl=1，否则Yijhkl=0。

优化模型：

minCmax=min（maxCj）# （1）

s. t.

sjh+xijh×pijh≤cjh# （2）

cjh≤sj（h+1）# （3）

sjh+pijh≤skl+L（1-Yijhkl）# （4）

cjh≤sj（h+1）+L（1-Yiklj（h+1））# （5）

=1# （6）

=Xikl# （7）

=Xijh# （8）

sjh≥0，cjh≥0# （9）

其中，式（1）表示目标函数，式（2）和式（3）表示每一个工件的工序顺序约束，式（4）和式（5）表示同一台机器在同一时刻只能加工一道工序，式（6）表示机器约束，同一时刻同一道工序有且仅能被一台机器加工，式（7）和式（8）表示机器存在循环操作，式（9）表示参数必须是正数。

3 算法设计

3.1 染色体编码

编码拟采用文献所提出的两段式编码方法，在编码时，将染色体基因分成机器码与工序码，解释如下：

工序码：工序码部分的总长度等于所有待排工件的所有工序之和，每個基因位用工件号表示，该工件号在工序码部分中第n次出现，则表示该工件的第n道工序，工件号出现的次数为该工件包含的工序数量。

机器码：机器码部分的总长度为所有待排工件的所有工序之和，每个基因位的编码表示对应于工序码部分相同位点的基因所表示的工序选择的机器编号。

3.2 种群初始化

初始化种群的质量因其往往影响着遗传算法的收敛速度与求解结果的质量所以十分重要，本文对工序码部分和机器码部分采用不同的初始化方法。

工序码：采用随机初始化的方法产生各个位点基因。

对于机器码部分的初始化，我们拟采用三种初始化方法：选取加工时间最小的机器的初始化方法（全局选择），平衡机器负荷（局部选择）的初始化方法以及随机选择机器的初始化方法。随机选择机器的初始化方法同工序码部分类似。针对前两种初始化方法的解释如下：

（1）选取加工时间最小的机器的初始化方法：即针对每一道工序在其可加工机器集合中选取加工时间最短的机器；

（2）平衡机器负荷的初始化方法：将机器所占用的时间累加，选取时间最短的机器作为该道工序的加工机器。

3.3 选择

本文采用最大完工时间最小作为评价指标，即公式（1）作为适应度函数，适应度小的个体即为优良个体，在对每一个个体进行适应度评价后，采用轮盘赌策略与精英保留策略对种群个体进行选择。

3.4 染色体交叉

采用改进的POX（基于工件优先顺序的交叉）方式进行工序码部分交叉操作，具体过程如下：

Step1 产生两个工件集JP1与JP2，JP1与JP2均为工件集合J的子集，两个子集中所含工件的个数小于或等于总工件个数的1/2，并且JP1∩JP2=。

Step2 将父代染色体P1中与JP1相关的工序基因按照与父代P1相同的位置填入子代染色体C1中，在选取父代P2中与JP1无关的工序基因按照原有顺序依次填入C1的空位基因处。

Step3 将父代染色体P2中与JP2相关的工序基因按照与父代P2相同的位置填入子代染色体C2中，在选取父代P1中与JP2无关的工序基因按照原有顺序依次填入C2的空位基因处。

对于机器码部分的交叉操作描述如下：

Step1 产生两个随机数r1与r2，（0

Step2 将父代染色体P1中基因位点为[r1，r2]之间的所有基因复制给子代C1，同时保证基因的位置顺序均不发生改变。将父代染色体P2中基因位点为[1，r1）与（r2，n]的所有基因复制给子代C1，同时保证基因的位置顺序均不发生改变。

Step3 将父代染色体P2中基因位点为[r1，r2]之间的所有基因复制给子代C2，同时保证基因的位置顺序均不发生改变。将父代染色体P1中基因位点为[1，r1）与（r2，n]的所有基因复制给子代C2，同时保证基因的位置顺序均不发生改变。

3.5 染色体变异

对于机器码部分，在对应工序的可用机器集合中选取另一台可加工设备替换当前选择的加工机器。

工序码部分采用互换变异，随机选取工序码中的两个基因，将其互换。基于工序的编码方式使得通过互换变异得到的仍为可行解。

3.6 模拟退火操作

由于遗传算法易陷入早熟，导致无法获得最优解，同时考虑到模拟退火算法具有较强的局部搜索能力，因此将遗传算法与模拟退火算法融合。对当前温度T与阈值温度Tmin进行对比，若Tmin>T，则对种群个体进行如下变换：选取种群中另一个个体，将该个体与将要变换的个体的机器码进行互换，得到新的个体，并参照Metropolis准则得到个体接收概率，接收概率如下：

P=# （10）

式中，Fb（T）为个体变换前的个体适应度，Fa（T）则为变换后的个体适应度。通过公式（10）计算出新个体的接收概率，与此同时产生一个随机数r∈[0，1]，若r

T=α×T# （11）

式中，α为控制参数，一般取值范围为0.5～0.99之间。

3.7 算法执行过程

Step1 算法的参数设置。包括种群大小、最大迭代次数、机器染色体三种初始化方法所占的种群比例、精英个体的数量、交叉与变异概率、模拟退火初始温度、阈值温度、温度衰减参数。

Step2 按照设置的参数进行种群初始化，生成第一代种群个体。

Step3 对种群中每一个个体进行解码操作，同时评价种群适应度大小。

Step4 判断迭代次数是否达到最大迭代次数或种群最优解连续几代均为发生改变，若满足，输出种群最优解，否则执行Step5。

Step5 执行染色体选择操作操作，结合精英主义选取下一代种群。

Step6 执行染色体交叉、染色体变异、模拟退火操作，得到新一代种群。同时返回Step3。

该算法的执行流程图如图1所示。

4 实验计算结果

为了验证本文所设计的改进的遗传算法（Improved Genetic Algorithm，IGA）的性能，采用文献[6]提出的8 ×8 的柔性作业车间算例进行测试，算法运行环境64bit Visual Studio 2017，处理器为Intel（R） Core（TM） i7-6700HQ CPU @ 2.60GHz 2.59GHz，程序采用C#编程语言编写。算法参数设置为：种群规模为100，最大迭代次数200，交叉概率0.8，变异概率为0.05，初始温度3000，阈值温度为1000，温度衰减参数为0.9。图2为本文提出的算法所求得最优解的甘特图，图3为基本遗传算法求得的解，表1对比了本文提出的算法与其他算法求解结果的对比。

通过图2、图3以及表1中的数据结果对比可知：在融合了模拟退火算法后，改进后的遗传算法寻优能力更强，得到的结果也更优。

5 结语

本文对柔性作业车间问题进行研究，并提出了一种改進的遗传算法，在种群初始化时考虑各台机器保持负荷相平衡，提出了机器码生成的三种初始化方式，同时对于遗传算法本身易早熟的特点，将模拟退火操作融入遗传算法当中， 提高全局搜索能力，增加了搜索精度，从而达到全局最优。通过实例计算表明改进后的遗传算法寻优效果好，搜索精度高，对柔性作业车间问题具有一定的指导作用。

參考文献

[1] Ham A.Flexible job shop scheduling problem with parallel batch processing machine[C]// Winter Simulation Conference.IEEE，2017.

[2] Ho N B，Tay J C，Lai E M K.An effective architecture for learning and evolving flexible job-shop schedules[J].European J of Operational Research，2007，179（2）：316-333.

[3] Teekeng W，Thammano A.Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems[J].Procedia Computer Science，2012，12（Complete）：122-128.

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

[5] 李铁克，王伟玲，张文学.基于文化遗传算法求解柔性作业车间调度问题[J].计算机集成制造系统，2010，16（4）：861-866.

[6] Kacem I，Hammadi S，Borne P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems， Man and Cybernetics， Part C （Applications and Reviews），2002，32（1）：1-13.

Abstract：Aiming at the discrete scheduling problem of the workshop which belongs to the NP-complete problem in theory， the simulated annealing algorithm is incorporated into the traditional genetic algorithm search， and the initial population is generated according to certain rules. Using the combination of machine code and process code， the initial population is generated by global generation， local generation and random generation. At the same time， the local search ability of genetic algorithm is poor and prone to premature phenomenon. Using the simulated annealing algorithm to improve the global search ability. The simulation results show that the performance of genetic algorithm combined with simulated annealing algorithm has faster convergence and optimization effect.

Key words：workshop scheduling；genetic algorithm；simulated annealing algorithm