面向作业车间调度问题的遗传算法改进

郑先鹏 王雷

摘 要：为了获得遗传算法在作业车间调度问题上的最优化解，提高算法的迭代速度，研究了遗传算法的改进方法，以工件的加工时间最短为目标建立调度模型。在算法上提出了基于概率改进的具有自适应能力的交叉与变异算子，以求作业车间调度问题的最优解。在遗传算法上采用精英保留策略方法，并结合改进的自适应算子对问题进行求解。以基准案例LA01和FT06作为实验仿真对象，获得了相应的甘特图以及搜索过程曲线。仿真结果表明，与未改进的算法相比，该算法能够更加快速地获得最优解。改进后的算法在搜索上更加快速有效，在求解作业车间调度问题上具有一定的可行性，更加适合工业加工生产。

关键词：最优化;机械车间;作业车间调度;自适应算子;精英策略;改进的遗传算法

中图分类号：TP278   文献标志码：A   doi：10.7535/hbkd.2019yx06006

Abstract： In order to obtain the optimal solution of genetic algorithm for job shop scheduling problem and improve the iteration speed of the algorithm， the improved method of genetic algorithm is studied. The scheduling model is established with the shortest processing time of the workpiece as the target. An adaptive crossover and mutation operator based on probability improvement is proposed to get the optimal solution of the job shop scheduling problem. The elitist retention strategy and the improved adaptive operator are used in the genetic algorithm， to solve solve job shop scheduling problem. The benchmark cases LA01 and FT06 are used as simulation objects. The corresponding Gantt chart and the search process curve are obtained. The simulation results show that the improved algorithm can get the optimal solution more quickly with the unmodified algorithm. The improved algorithm is more efficient and faster. It is feasible to solve job shop scheduling problem， and is more suitable for industrial production.

Keywords：optimization; machinery workshop; job shop scheduling; adaptive operator; elitist strategy; improved genetic algorithm

作业车间调度问题（ job shop scheduling problem，JSP）主要是确定各工件的加工次序和机器，是典型的NP-hard 问题[1]。随着市场经济的发展， 企业间的竞争越来越激烈，如何合理安排作业车间调度显得至关重要[2]。随着科学技术的蓬勃发展，工业工程中车间生产规模逐渐扩大，作业车间调度越来越复杂，作业车间调度的组合优化问题已成为当今工业工程领域发展研究的热点问题之一[3]。对于该问题，研究者们主要是通过各种启发式研究方法进行求解，常用于主流求解的方法有粒子群优化算法、遗传算法、神经网络算法、禁忌搜索算法等[4-10]。 其中，遗传算法因简单通用、高效、容易取得较好的结果，已经广泛应用在优化调度问题、组合问题优化等方面[11]。在求解实际的工业工程生产调度问题上，遗传算法被普遍关注和使用，遗传算法的运算反映了优胜劣汰操作的基本原则[12]。当今虽然有许多国内外学者应用遗传算法对作业车间调度问题的求解进行了大量研究，然而在遗传算法求解车间调度问题上依然有很多未知的改进方法未被人们发掘。由于作业车间调度问题在实际工业生产环境中存在复杂性，如何求得满足要求的准最优解是一个亟待解决的问题，因此对它的研究具有非常重要的现实意义[13-14]。

本文提出了一种改进的自适应遗传算法，并利用其对作业车间调度问题进行目标求解。改进的算法在交叉和变异概率选择操作上能够实现自适应改变，可应用于作业车间调度问题的求解。

1 作业车间调度建模

作业车间调度可描述为，有一批待生产加工工件，这一批工件总共有n个，每个工件有m道工序需要加工[15]，并且加工这批工件的设备总共有m台。加工这批工件的要求是：

1）在刚开始加工的时候，每一个工件都有被选中加工的可能;

2）车间中的任何一台加工设备在任一时刻只能加工一个工件;

3）如果加工工作开始，就不能中断;

4）在车间中进行加工的同一时刻，要求每一个被加工工件只能由一臺加工设备加工;

5）每一个工件在开始加工之前没有先后顺序的约束，然而同一工件的加工工序在加工时有先后顺序的约束;

6）每一個工件必须按照加工的工艺路线加工;

7）不考虑加工工件时在运输、装夹等辅助工序上产生的运输时间。

本文以加工工件的最短时间为目标进行研究。其目标函数如式（1）所示：f（x）=min1≤k≤m{max1≤i≤n{Cik}}，（1）式中：Cik表示工件i在机器k上的完工时间。式（1）的倒数为适应度函数。

2 遗传算法的改进设计

2.1 染色体编码和解码

目前遗传算法的编码方式有很多种，如浮点数编码、二进制编码、整数编码、符号编码、矩阵编码等[16]。对于遗传算法而言，基因编码在算法中起着至关重要的作用，编码的方式直接影响遗传算法的运行速度以及能否找到全局最优解[17]。本文针对作业调度问题，采用了比较受青睐的基于工序的编码方式。

在基于工序的编码方式上，染色体上的基因表示确定的工序在机器上的加工顺序，因此可以得到调度问题的解。染色体上的基因表示如下：染色体上每一个位置上的基因用于表示对于加工工序的选择，每个基因位置上的数字用来表示对应序号的相应加工工件，染色体上出现相同的数字出现第几次就用来表示该工件被加工的工序号。同一数字在该段的染色体上出现的次数就表示该工件的总工序数。在染色体上不同的位置，若出现不同的序号则表示不同的工件加工顺序。编码示例见表1。

染色体解码是在染色的基因部分所包含的基因信息转化为工件加工流程信息[18]。根据加工工序开始依次加工，然后得到机器加工工件从开始加工到结束加工所用的时间，从而得出整个加工系统的调度甘特图。

2.2 选择和交叉操作

2.2.1 选择操作

选择操作的目的就是为了挑选出种群中的较优个体，使较优个体在种群中逐渐增加，在迭代的过程中使种群往更好的方向发展。对种群中的个体进行选择操作时，依据个体适应度值的大小来决定在进化下一代时它是被淘汰还是其他操作。在遗传算法的选择操作中个体会被选中的概率与它的适应度函数值呈现一种正比例关系。

2.5 终止准则

设置算法的最大迭代次数，如果迭代次数过少则会影响算法的有效性，在有限的迭代次数内得不到近似最优解[20]。在本文中，当搜索次数达到最大次数时，算法停止运行，并输出最优解。

2.6 改进的遗传算法流程图

改进的遗传算法运行流程图如图2所示。

3 仿真实验

3.1 算法实例

为了验证改进算法的可行性，首先对LA01基准案例进行仿真。

利用Matlab对改进的自适应遗传算法进行编程求解。算法的基本参数如下：种群规模Z=100，k1=k2=0.9，k3=k4=0.1，进化代数G=200。利用改进算法对案例LA01求解的甘特图如图3所示，算法进化过程如图4所示。由图3可知，使用改进的遗传算法获得的最少加工时间为666 s，实验仿真结果与目前已知该案例的最优解完全相同。仿真实验结果有力证明了改进的遗传算法是可行和有效的。

另外，针对基准案例FT06进行仿真实验，得到该案例的实验甘特图如图5所示，搜索进化过程如图6所示。改进的遗传算法运用于该基准案例获得的实验仿真结果为55 s，与目前已知该案例的最优解完全相同，进一步说明了改进算法是可行的。

3.2 算法对比

为了进一步验证改进算法的有效性，针对FT06基准案例，将改进的遗传算法与基本遗传算法进行比较，结果如图7所示。改进算法仅需9代便可以获得实验的最优解，未改进算法在第73代才获得最优解，因此改进的遗传算法具有非常高的搜索能力，从而证明了改进的遗传算法是有效和可行的。

4 结 语

针对求解作业车间调度问题，将最大完工时间最短作为调度的最终求解目标，应用改进的遗传算法对该目标问题进行求解，设计了自适应交叉和变异概率算子，在选择操作上加入了精英保留策略，以保留最优个体不会遭受破坏。对基准案例LA01和FT06的实验仿真结果表明，在进化过程中，改进的遗传算法不仅具有十分优良的搜索能力，还具有更快的收敛能力，因此，其在求解作业车间调度问题上是有效和可行的。

本研究的不足之处在于该改进的遗传算法仅适用于传统的作业车间调度问题，未来还需对多目标、环境多变、复杂的柔性作业车间调度问题进行研究。

参考文献/References：

[1] 徐华， 程冰. 混合遗传蝙蝠算法求解单目标柔性作业车间调度问题[J]. 小型微型计算机系统，2018， 39（5）： 1010-1015.

XU Hua， CHENG Bing. Hybrid genetic bat algorithm for single-objective flexible job shop scheduling problem[J]. Journal of Chinese Computer Systems， 2018，39 （5）： 1010-1015.

[2] 吴再新. 基于粒子群算法的动态车间调度问题研究[D]. 上海：东华大学，2016.

WU Zaixin.Research on Dynamic Job Shop Scheduling Problem Based on Particle Swarm Optimization[D]. Shanghai： Donghua Univer-sity，2016.

[3] 曹磊， 叶春明， 黄霞. 变邻域杂草算法在多目标柔性作业车间调度中的应用[J]. 计算机应用研究， 2018，35（1）： 150-154.

CAO Lei， YE Chunming， HUANG Xia. Application of variable neighborhood weed algorithms in multi-objective flexible job-shop scheduling[J]. Application Research of Computers， 2018，35（1）： 150-154.

[4] 王雷， 蔡勁草， 唐敦兵， 等. 基于改进遗传算法的柔性作业车间调度[J]. 南京航空航天大学学报， 2017，49（6）： 779-785.

WANG Lei， CAI Jincao， TANG Dunbing， et al.Flexible job shop scheduling based on improved genetic algorithms[J]. Journal of Nanjing University of Aeronautics & Astronautics， 2017， 49（6）： 779-785.

[5] ARIYASINGHA I D I D， FERNANDO T G I. A performance study for the multi-objective ant colony optimization algorithms on the job shop scheduling problem[J]. International Journal of Computer Applications， 2015， 132（14）：907638.

[6] FLOREZ E， GOMEZ W， LOLA B. An ant colony optimization algorithm for job shop scheduling problem[J]. International Journal of Artificial Intelligence & Applications， 2013， 4（4）： 53-66.

[7] PENG B， LU Zhipeng， CHENG T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem[J]. Computers & Operations Research， 2015， 53： 154-164.

[8] SPANOS A C， PONIS S T， TATSIOPOULOS I P， et al. A new hybrid parallel genetic algorithm for the job-shop scheduling problem[J]. International Transactions in Operational Research， 2014， 21（3）： 479-499.

[9] NASIRI M M. A modified ABC algorithm for the stage shop scheduling problem[J]. Applied Soft Computing， 2015， 28： 81-89.

[10] KARIMI-NASAB M， MODARRES M， SEYEDHOSEINI S M. A self-adaptive PSO for joint lot sizing and job shop scheduling with compressible process times[J]. Applied Soft Computing， 2015， 27： 137-147.

[11] 周明， 孙树栋. 遗传算法原理及应用[M]. 北京：国防工业出版社，1999.

[12] 王进业， 宋宇博. 旁通式自动化立体仓库拣选作业和出口选择的组合优化[J]. 河北科技大学学报， 2015， 36（1）： 36-44.

WANG Jinye， SONG Yubo.Combination optimization of picking operation and export selection in bypass automated three-dimensional warehouse [J]. Journal of Hebei University of Science and Technology， 2015， 36（1）： 36-44.

[13] 薛宏全， 魏生民， 张鹏， 等. 基于多种群蚁群算法的柔性作业车间调度研究[J]. 计算机工程与应用，2013，49（24）： 243-248.

XUE Hongquan， WEI Shengmin， ZHANG Peng， et al.Research on flexible job shop scheduling based on multi-population ant colony algorithms[J]. Computer Engineering and Applications， 2013， 49（24）： 243-248.

[14] 王凌， 邓瑾， 王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策，2016，31（1）： 1-11.

WANG Ling， DENG Jin， WANG Shengyao.A review of distributed job shop scheduling optimization algorithms [J]. Control and Decision， 2016， 31（1）： 1-11.

[15] 刘洪铭， 曾鸿雁， 周伟， 等. 基于改进粒子群算法作业车间调度问题的优化[J]. 山东大学学报，2019，49（1）： 75-82.

LIU Hongming， ZENG Hongyan， ZHOU Wei， et al.Job shop scheduling problem optimization based on improved particle swarm optimization [J]. Journal of Shandong University， 2019，49（1）： 75-82.