张浩宇

（内蒙古工业大学，内蒙古呼和浩特 010000）

求解Jop-shop调度问题的一种新方法

张浩宇

（内蒙古工业大学，内蒙古呼和浩特 010000）

车间调度问题是制造系统理论研究的基础问题之一。针对Job-shop问题，通过使用新的遗传算法求解。使用了基于工序的编码方法和GT算法进行解码，来产生初始种群。通过对比测试，该算法可以产生较为优秀的初始种群。为了避免产生非法染色体，提升算法运行效率，采用了单亲交叉遗传算子。基准问题的仿真实验结果表明，提出的遗传算法可行。

Job-shop；遗传算法；GT 算法

10.16621/j.cnki.issn1001-0599.2017.09.17

0 前言

调度问题的研究最早始于20世纪50年代，Johnson对针对Flow-shop调度问题进行了相关研究。调度理论的主体于20世纪70年代开始建立。时至今日，随着工业生产能力的日益精进，能源消耗问题日益突出。调度理论在当代社会扮演着越来越重要的角色。基于启发式规则的调度方法，整数规划法，仿真调度方法，基于人工智能等方法均可求得Job-shop问题的满意解。文献[1]提出了一种交互式权重自适应进化算法来解决动态车间调度问题。文献[2]设计了一种进化算法解决一个多目标车间重调度问题。

1 Job-shop问题描述

Job-shop问题可以被描述为：假定加工系统有n个加工顺序不同的工件要在m（＞2）台机器上完成加工，事先已经规定各道工序在各台机器上的加工顺序和加工时间，调度任务是通过确定工件的每道工序的开始加工时间，使得最大完工时间（Makespan）最小。

2 遗传算法设计

2.1 编码方式

用遗传算法求解Job-shop调度问题时，首先需要对Jobshop问题进行编码。最常使用的编码方式是基于工序的编码方式。一条染色体是一条由所有工序的排序所组成的一条序列。含义是，此序列中的顺序决定了工件在不同机器上的加工顺序。其中，每个基因代表一个工序且同一工序的所有工序须使用同一工件序号表示。这种编码方式的优点是所成染色体都可以构成可用调度，同时也不会产生非法解，不需要采取拒绝策略，对存在死锁的非法解予以抛弃，从而提升了算法效率。

2.2 解码方式

利用Giffer和Thompson所提出的GT算法来进行解码。此算法的本质是避免机器在加工工件的过程中有着过长的空闲时间。首先说明工件加工路径相关性约束，给出工序前继、机器前继和冲突集的定义。工序前继：若同一工件的两道工序存在加工工艺路径的相关性，把前面的工序称为工序前继，即工序前继加工完成后，另一道工序才能进行加工。机器前继：若两道工序在同一台机器上加工且存在加工工艺路径的相关性，将前面的工序称为机器前继，即机器前继加工完成后，后一道工序才能进行加工。

冲突集：假设一个工序Q。PJ（Q）和PM（Q）是它的工序前继和机器前继。ES（Q）表示工序Q的开始加工时间。P（Q）表示工序Q的加工时间。C（Q）表示工序Q的加工完成时间。数学描述见（1）和（2）式。

最早可完成操作表示在一个加工序列中，机器中最早完成的工序是，数学描述见（3）式。

假设机器Mr上的2个工序Q*r及Qkr。Qkr是一个未调度工序。冲突集的数学描述为（4）式。

GT算法的步骤是：一个Job-shop问题的技术序列矩阵及加工时间矩阵使用Tjk和Tik表示。

（1）初始化一组工序技术序列D，将工件开始加工时间初始化为0。

（2）寻找D序列中的在机器Mr上最早可完成工序Q*r。根据公（3）和（4）构造冲突集。定义Q*r和Qkr。

（3）调度工序Qkr为机器r上的第i个工序。使用公式Sri=k表示。并更新工序Qkr的开始时间和结束时间。工序Qkr为调度完成工序。

（4）将调度完成的工序从工序技术序列D中去除，并且更新工序序列中其余工序的开始加工时间及完工时间。

（5）从Job-shop调度技术序列中寻找工序Qkr的下一道工序Qks。并将其补充到加工序列D中。

（6）重复步骤（1）到步骤（5）直到所有的工序全部调度完成。为了验证此解码方法的有效性，选用两组基准问题做比较。使用两种方法进行解码。第一种方案是常用的直接染色体解码方案。第二种方案是GT算法解码方案。经验证，GT算法解码方案的解码结果比直接染色体解码方案更加优秀。直接染色体解码结果是：1728，1698，1757，1688。GT 算法解码：1536，1487，1452，1660。

3 适应度函数的选择

制造期Cmax为论文中常见的优化目标，制造期的定义为max（C1，C2，…Cn）。

优化目标见（5）式。

Cmax=min（maxni=（1Ti）） （5）式中，加工工件总数目为n，Ti为工件Ji的完工时间。适应度函数见（6）式。

fitness=1/Cmax（6）

4 交叉和变异

常用的双亲交叉算子容易产生非法染色体。算法后期需要设计相应的策略去除非法染色体，为算法增加了难度，算法运行效率降低。设计单亲交叉遗传算法，即通过单个染色体繁殖后代，此方法避免了非法染色体的产生。变异的目的是维持种群的多样性，变异概率的设计兼顾对种群中重要概率的保留，同时提升遗传算法开辟新搜素空间的能力。因此，采用基于邻域搜索的变异算子，此变异算子能使染色体产生新的不定方向的基因模式，从而加速算法寻优的过程。

5 选择策略

遗传算法的选择算子作为对自然选择过程的模拟，主要用来确定交叉个体以及将产生多少个子代个体。不同的选择策略将对算法的性能有着重要的影响，其中轮盘赌选择是最常用的选择策略。适应度高的个体对应被选择的概率大，相反适应度较低者被选择的概率小。

6 仿真实验

6.1 测试算法的有效性

使用10组基准问题来测试算法的有效性。实验分为两部分：第一部分，为了验证算法的有效性，通过比较GT算法活跃化解码后的结果与通过遗传算法计算后的结果比较验证。第二部分，通过一个基准问题与其他文献的算法所得结果做比较。实验采用MATLAB 2014编写算法程序，运行计算机内存8 G，CPU频率2.6 GHz。

6.2 基准问题仿真实例

为了证明算法的有效性。通过基准问题LA01算例，与使用的POX交叉算法所得最优解对比。所得的最优解为666，使用遗传算法最优解为659。通过对比，算法所得的最优解优于POX交叉算法，从LA01的收敛曲线可以看出，遗传算法收敛速度较快（在10代前收敛到最优解）。通过此实验结果可以看出，本文算法有着更强的搜索能力。

7 结论

通过对Job-shop问题的分析，使用GT算法进行活跃化解码。实验结果对比，此算法产生的初始种群较为优秀。提出一种单亲交叉算法避免非法染色体的产生，提升了算法的运行效率。该算子可以很好的继承父代染色的优秀基因。将该算法应用于LA01基准问题，所得最优解优于POX交叉遗传算法所得的最优解，说明该算法可以较好的用于生产实际。

［1］Hao，X.C.，& Gen，M. （2011）.Multi-objective job shop rescheduling by using evolutionary algorithm.IEEJ Transactions on Electronics， Information and Systems，131（3），674 – 681.

［2］柳林.基于遗传算法的Job-Shop调度问题求解［J］.计算机应用，2006（7）：1694-1696.

［3］马秀明.基于改进遗传算法的车间调度优化及其仿真［D］.大连：大连理工大学，2008.

TP18

B

〔编辑 利 文〕