基于遗传算法的Job-Shop调度问题研究

陶　泽，张海涛

(沈阳理工大学 机械工程学院，沈阳110159)



基于遗传算法的Job-Shop调度问题研究

陶泽，张海涛

(沈阳理工大学 机械工程学院，沈阳110159)

摘要：研究单目标作业车间调度问题(JSP)，提出了一种基于遗传算法以缩短生产周期为目标的Job-Shop调度问题。通过建立数学模型，设置编码、解码方案，以及确定选择、交叉、变异等遗传算子，充分利用遗传算法的特点解决加工车间静态、动态问题，并通过Gantt图给出调度方案。结合应用实例进行分析，分析结果表明该方法是有效的、可行的。

关键词：作业车间调度；遗传算法；Gantt图

作业车间调度(Job-Shop Scheduling)是车间调度中最常见的调度类型，是最难的组合优化问题之一[1]，对其研究具有重大的现实意义。科学有效的生产调度不但可以提高生产加工过程中操作工人、设备资源的高效利用，而且还可以缩短生产周期，降低生产成本。随着遗传算法在组合优化问题的广泛应用，许多人开始对遗传算法进行深度研究，并应用它求解车间调度问题。

目前，对作业车间调度问题的研究大都集中在静态调度上，对动态调度的研究很少。因为动态调度要比静态调度复杂得多，另外因为在研究动态调度问题时，由于在实际的生产加工过程中不确定以及随机因数太多，任何单一的规则都较难适用于所有的动态环境。

在最近几年，对动态调度问题的研究方法主要有人工智能方法、仿真方法等[2]。这些方法不但开发成本高，而且开发周期也很长，不适应于企业的应用。相比之下，遗传算法作为一种新型仿生算法为求解生产调度问题提供了新的解决思路。

因此，本文提出了一种应用遗传算法求解作业车间动态调度的方法，为了评价这种方法的有效性，以最优完工时间为目标[3]模拟加工车间，通过模拟结果可以观察出应用遗传算法求解此类问题是有效的。

1Job-Shop调度问题的描述

作业车间调度是一个经典的调度问题，如今在国内外受到研究人员们的高度重视，它是对一个可用的加工机器集在时间上进行加工任务集分配，以满足一个性能指标集，问题可以描述为有M台机器、N个工件，每个工件由一系列的操作组成。用MC={mk}表示加工机器集，其中k=1，2，…，M；用JC={jk}表示加工工件集，其中k=1，2，…，N；OP={opik}表示加工工序集，i=1，2，…，N；k=1，2，…，M。每个操作opik必须满足预先给定的加工约束条件以及加工时间，从而使各工件的工序合理地安排到各加工机器上进行操作，并且能够使所有工件的最终完工时间达到较优值。

2遗传算法

遗传算法(GA)是以种群为基础的搜索算法，种群中每个个体代表所求问题的一个解，把要解决的问题编码成字符串染色体，然后从任意的初始群体进行搜索，通过种群中染色体基因的选择、交叉、变异等遗传操作可使种群进化到越来越好的搜索空间，最终收敛“最适应环境的个体”，从而求得问题的最优解或满意解[4]。该算法在解决一些特殊问题上效率不是特别理想，但是应用到一般的优化问题上效率还是优于一些传统随机算法，本文提出的遗传算法流程见图1。

图1　遗传算法流程图

3Job-Shop调度问题的数学模型

由于作业车间调度问题是考虑N个工件在M台机器上加工排序问题，各工件的各工序由Q个操作组成，并且每个操作要求在不同的机器上加工，每个工件的所有操作特点在于加工机器和加工时间是固定的，具体描述如下[5]：

(1)对于工件的加工优先约束条件：在这里让Cik表示工件i在机器k上的完工时间，tik表示工件i在机器k上的加工时间，假设机器h先于机器k加工工件i，则约束条件可描述如下：

Cik-tik≥Cih

(1)

(2)对于机器的操作优先约束条件：假设工件i和工件j在某一时刻都要在机器k上加工，如果工件i先于工件j到来，则约束条件可描述如下：

Cjk-Cik≥tjk

(2)

由于本文的JSP是以工件的最短完工时间为目标,故目标函数为

(3)

约束条件为

Cik-tik≥Cih,(i=1,2,…,N，h,k=1,2,…,M)

Cjk-Cik≥tjk，(i,j=1,2,…,N，k=1,2,…,M)

式中：Cik表示工件i在机器k上的完工时间；tik表示工件i在机器k上的加工时间；Cih表示工件i在机器h上的完工时间；Cjk表示工件j在机器k上的完工时间；tjk表示工件j在机器k上的加工时间；M为机器的数量；N为工件数。

4Job-Shop调度的算法实现

4.1编码

根据车间作业实际情况，本文采用基于工序的编码方式[6]，这种编码方法是把调度编码为工序的序列，个体中的每个基因代表一道工序，对于{m1，m2，…，mM}台机器和{j1，j2，…，jN}个工件的车间作业调度问题的染色体编码为

[g1，g2，g3，…，gM×N]

式中，gi表示工件的编号，工件编号在染色体出现的次数表示执行工件在该次数的加工工序，例如，g2在染色体中第二次出现表示执行第二类型工件的第一道工序，这样很容易看出染色体的任意排列总能产生可行调度，而且这些可行调度之中一定含有最优调度。例如以3×3调度问题为例，介绍编码实现过程，根据上述编码策略，该调度问题的编码方案见表1。

表1　编码方案

4.2解码

解码过程是将染色体 [g1，g2，g3，…，gM×N]中的每一个基因(工件号)根据其在染色体中出现的次序解码成各工件的工序。例如，对上述3个工件3台机器(3×3)的调度问题的编码进行解码，根据表1编码方案可知其染色体的随机初始化为[2 2 1 3 3 1 1 3 2]，故可以解码为：首先加工工件2的第一道工序，接下来工件2的第二道工序，然后是工件1的第一道个工序，接着是工件3的第一道工序…。根据工件每个工序所要求的机器号得出每个基因所对应的机器顺序，比如工件2所需机器号分别为M1、M2、M3，则表示工件2的第一个工序在M1上加工，第二个工序在M2上加工，第三个工序在M3上加工。然后根据各个工件的加工时间得到相应的加工时间，就可以完成一个调度方案。

4.3适应度函数

在遗传算法中采用适应度函数对染色体的优劣进行评价，染色体的适应值越高被遗传到下一代种群的概率越高，反之则相反。另一方面，若适应度函数设计不当，将难以体现个体的差异，选择操作的作用就很难体现出来，从而造成早熟收敛等特点。所以适应度函数的合理确定在优化过程中起着至关重要的作用，根据目标函数要求的是最小化最大完工时间问题，所以用染色体解码后的最大完工时间的倒数为适应值。设xkmax表示第k个染色体的最大完工时间，则可以定义适应度函数为

F(xk)=1/xkmax

(4)

当xkmax减小时，则F(xk)增加，即染色体的最大完工时间越小，适应值越大。

4.4遗传算子的设计

(1)选择操作即在计算出种群中各个体的适应值的基础上对所有个体由优到劣进行排列，然后以一个具体的方式把一定的选择概率分配给各个体。设M为种群大小，Fit为个体i的适应度，则个体i被选中的概率为

(5)

(2)交叉操作当选择操作执行完以后，交叉操作将两个配对的染色体部分基因交换从而形成两个新的染色体，该操作不能过多破坏个体中表现优良的编码串。例如，父代1:α[p1]=a、b、c、d、e ;父代2：β[p2]=c、d、e、b、a，从两父代染色体中随机选取基因a、b、e，然后将这两个基因从中选取出来，并且使它们与原父代中的位置一致，得到的子串基因分别为：f[p3]=a、b、e，h[p4]=e、b、a，此时两父代种群出现三个空缺位置，随之将子串f[p3]→α[p1]、h[p4]→β[p2]，即可得出子代α1[p5]=e、b、c、d、a，β[p6]=c、d、a、b、e。

(3)变异操作 为了增强遗传算法的局部搜索能力并且能够提高种群的多样性，变异操作将染色体编码串中的某些基因进行改变，从而使遗传算法以良好的搜索性能来完成最优化的过程。所以采用如下变异方法：

变异前

父代 ( A, B, C, D, E, F )

变异后

子代 ( A, B, F, E, D, C)

具体的执行步骤是：首先从父代中随机选择第3位到第6位的所有基因即得到基因串C、 D、 E、 F，然后按逆序排列就可得到子代。

5算例仿真

5.1静态算例仿真

该次测试中以静态调度为例，以工件生产周期最短为目标。采用Delphi7.0软件编程实现上述算法，采用面向对象的编程策略。当工件加工顺序、加工时间确定以后在加工过程中不考虑任何紧急事件的发生，待加工工件依次进入加工系统，工件的加工顺序以及各项加工参数不变即加工环境为一个静态过程。在仿真实例中，以6×6调度问题为例，算例相关参数为：工件种类JC={j0，j1，j2，j3，j4，j5}，机器种类MC={m0，m1，m2，m3，m4，m5}，每个工件在相应的机器上的加工顺序与加工时间见表2所示。

表2　工件在机器上的加工顺序及加工时间

在仿真过程中设置各个机器的加工开始时刻为0，为了验证算法的有效性，取仿真次数为1、2、3、4、5、6、7、8，种群数目100、交叉概率pc=0.8、变异概率pm=0.1，由于篇幅有限只给出Delphi7.0软件一部分操作界面见图2。

Delphi7.0软件仿真次数与相应的结果见表3所示。

图2　软件界面

次数12345678结果5558545756575353

通过仿真结果可以清楚地看出，每次运行的结果略有差别，但是上下浮动不大，稳定性相对平稳。安晶等人提出的算法[7]研究结果是55个单位时间(生产周期)，本文提出的算法得到的最佳调度结果为53个单位时间，很明显得到的结果优于前者2个单位时间。算法得到最优调度Gantt图见图3。

图3　静态调度Gantt图

5.2动态算例仿真

在实际生产加工车间中，加工环境是一个动态的过程有许多不确定因素[8]，例如，紧急订单、操作工人离岗等都会扰动原调度计划，因此，生产调度人员必须考虑重新安排调度，假设在生产加工进行4小时，紧急订单即工件6需要进行加工，这里要考虑两个要求：已经加工完工的工件工序不予考虑、正在进行加工的工件不予考虑，工件6加工时间矩阵T=[367]，加工机器矩阵M=[251 ]。由图3可知，当紧急订单到来时，已完工工件和正在加工工件信息见表4。

表4　完工工件及正在加工工件

表中mk(i，j)表示第i个工件的第j道工序在机器k上进行加工或已完成加工。通过仿真得到的动态系统的Gantt图见图4，由图4可以看出，动态调度系统的最优完工时间(56)和紧急工件到来之后各工件在各机器上分配关系，同时图4也明显地反映出动态调度系统要比静态调度系统复杂得多[9]，由仿真结果不难看出应用遗传算法求解车间作业动态调度问题是有效和可行的。

图4　动态调度Gantt图

6结束语

提出了运用遗传算法优化动态调度问题，在动态方面主要考虑了紧急订单，通过确定算法的编码、解码以及遗传算子的设计，在建立调度模型的基础上，由模拟仿真先优化出静态结果，在此基础上进行重调度即动态调度。仿真结果表明该方法是可行的并且能够得到较好的效果。

参考文献：

[1]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2002.

[2]吴云高,王万良.基于遗传算法的混合Flowshop调度[J].计算机工程与应用,2002,38(12):82-84.

[3]陈振同.基于改进遗传算法的车间调度问题研究与应用[D].大连:大连理工大学,2007.

[4]刘晓霞,谢里阳,陶泽,等.柔性作业车间多目标调度优化研究[J].东北大学学报:自然科学版,2008,29(3):362-365.

[5]Liu T,Tsai J,Chou J.Improved genetic algorithm for the job-shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2006,27(9-10):1021-1029.

[6]蒋丽雯.基于遗传算法车间作业调度问题研究[D].上海:上海交通大学,2007.

[7]安晶.一种基于遗传算法的车间调度算法求解[D].盐城:盐城工学院,2007.

[8]陈勇,胡婷婷,鲁建厦.基于遗传算法改进的动态车间调度[J].浙江工业大学学报,2012,40(5):537-543.

[9]徐雯雯.基于遗传算法的车间动态粗调度研究[D]济南:山东大学,2010.

(责任编辑：马金发)

Studies on Job-Shop Scheduling Problems Based on Genetic Algorithms

TAO Ze，ZHANG Haitao

(Shenyang Ligong University,Shenyang 110159,China)

Abstract：The single target job-shop scheduling problem (JSP is focused on)；First of all，a genetic algorithm is proposed to shorten the production cycle of job shop schedule；Secondly，through mathematical model establishment，genetic algorithm of characteristics is applied to solve the processing plant static and dynamic problems by setting the encoding and decoding scheme and determining the selection，crossover and mutation genetic operators，and genetic algorithm of characteristics is applied to solve the processing plant static and dynamic problems，which is given by the Gantt chart scheduling scheme；Finally，with the analysis of example，the results show that the method is effective and feasible.

Key words：job shop scheduling；genetic algorithm；Gantt chart

中图分类号：TP311

文献标志码：A

文章编号：1003-1251(2016)02-0060-05

作者简介：陶泽(1977—)女，副教授，研究方向：微制造与信息处理技术。

收稿日期：2015-04-09