考虑调整时间的柔性作业车间调度问题研究*

张国辉，朱宝英，杨洋洋，孙靖贺

(郑州航空工业管理学院，郑州 450015)

0 引言

随着社会的发展人们对个性化的需求越来越高，车间加工方式越来越呈现多品种小批量的趋势，车间管理的柔性化、精细化程度不断提高[1-2]。传统柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)进行优化时将调整时间、加工时间等时间作为整体或仅考虑加工时间。根据福特汽车公司的统计，在实际加工过程中，工件的安装与定位、机器的调整、工作台的清扫与清屑等时间占总加工时间的90%以上。辅助性的调整时间和加工时间需要作为独立因素同时进行考虑，以提高优化后调度方案的有效性。

目前针对柔性作业车间调度问题的研究文献很多，集中在以加工时间为对象的多目标调度、动态调度等[3-4]，然而考虑到工件调整时间，并将其与加工时间作为独立因素同时考虑的文献极少。文献[5]针对单机调度问题提出带调整时间加权成套订单数排序问题并采用遗传算法进行求解。文献[6]将调度问题转化为经典的旅行商问题，并采用基于优先级的比例选择、实数两点交叉及模式变异算子的改进遗传算法对含有调整时间的作业车间调度问题求解。文献[7]提出通过改变工序调度次序前移存在调整时间综合调度工序的算法，实现提高设备利用率，提前产品最终完工时间。文献[8]提出了一种考虑调整时间的作业车间调度与预防性维修集成方法。文献[9]以拖期最小为目标优化含调整时间的柔性作业车间调度问题。文献[10]采用禁忌搜索算法求解带有调整时间的柔性作业车间调度问题。

本文将调整时间与加工时间作为独立影响因素进行考虑，通过对传统的遗传算法进行改进，在进行解码时提出考虑调整时间的活动调度解码方案、自适应函数进行交叉和变异，实现对求解过程的快速寻优。运用Matlab编程对实验数据进行测试，实验结果进一步验证了考虑工件调整时间的柔性作业车间调度模型更加符合实际生产情况。

1 带调整时间的FJSP模型建立

带调整时间的FJSP问题数学模型的描述及定义为：工件集J={J1,J2,J3,…,Jg,…Jn}，Jg是第g个工件(g=1,2,3,…,n)；机器集M={M1,M2,M3,…,Mi,…,Mm},Mi是第i台机器(i=1,2,3,…,m)；Ojh是工件j的第h道工序，并定义Oj(h-1)为第Ojh的上一道工序，Oj’h’表示为Ojh所在机器的前一道工序；Pjh表示工件j的第h道工序加工完成时间；Tijh表示工件j的第h道工序在机器i上加工时所需要的时间；Sijh表示为工件j的第h道工序在机器i上的加工开始时间；Cijh表示为工件j的第h道工序在机器i上的加工结束时间；Installtimei表示在机器Mi安装、定位等调整时间；Cj表示为工件j的完工时间；Cmax表示为最大完工时间。在建立数学模型时，假设以下条件：

(1)所有机器在零时刻均可用，所有工件在零时刻均可被加工。

(2)任意一道工序只能在一台机器加工，且工序在加工过程中不允许被中断。

(3)任意一台机器在同一时间仅能加工同一工件的同一道工序。

(4)不同工件之间没有加工顺序约束，同一工件的不同工序间有先后加工顺序约束。

以最大完工时间最小为优化目标，其目标函数及约束条件分别为：

Cmax=min(max1≤j≤n(Cj))

(1)

Cijh=Sijh+Tijh

(2)

Cijh-Cij′h′≥Tijh+Adjustmenti

(3)

(4)

式(1)表示总目标函数，即最大完工时间最小化；式(2)表示工序加工的完成时间等于工序开始时间与工序加工时间之和；式(3)表示机器的资源约束，同一机器在同一时刻只能允许加工一个工件；式(4)表示如果工序所在机器的开始加工时间(空隙开始时间)小于上一道工序的调整时间，则受调整时间约束；否则(空隙开始时间大于上道工序结束时间)，加工工序受当前加工机器的资源约束。所以，若某一工件的相邻工序在同一机器上加工时，仅受机器资源约束；对于同一工件内的相邻两道工序而言，考虑了调整时间，替代了传统加工模型中的工序顺序约束。为了方便理解，给出具体的柔性作业车间调度问题实例，如表1所示。

表1 部分柔性作业车间调度问题实例

2 改进遗传算法求解带有调整时间的FJSP

2.1 FJSP的染色体编码和解码

在使用遗传算法求解目标问题时，编码与解码是遗传算法首先要解决的问题，如前文所述，FJSP包含两个子问题：机器选择与工序排序。机器选择是用来解决每道加工工序在可选机器集中选择哪台机器进行加工；工序排序是用来解决所有工件在选择完加工机器后，工序排序和开工时间的问题。采用文献[11]中的编码方式进行编码，将两个子问题编码到一条染色体上，即表示FJSP的一个可行解,见图1。

图1 染色体编码

(1)机器选择部分：该部分染色体长度为总工序数L，每个基因位用整数表示，从左到右依次按加工工件的工序顺序排列，每个整数表示加工工件的当前工序在可选择的机器集中的顺序编号。以表1为例，如图1左半部分所示，该基因串为4-2-3-1-3-2，表示工序O11在可选加工机器集中第4个机器上进行加工，即实际加工机器为M4；工序O12在可选加工机器集中第2个机器上进行加工，即实际加工机器为M3，以此类推。

(2)工序排序部分：该部分染色体长度为总工序数L，每个基因用工件号进行编码，工件号出现的次数就表示该工件的工序数。如图1右半部分所示，该基因串为2-1-2-1-2-1，对应的加工工序为O21-O11-O22-O12-O23-O13。

在解码过程中，由于染色体包含两部分，即机器选择子问题和工序排序子问题。首先对机器选择进行解码：从左到右依次读取机器部分染色体，并转换到机器顺序矩阵中和时间顺序矩阵中。其次对工序排序进行解码：从左到右依次读取工序染色体部分，根据机器选择部分解码得到的机器矩阵、加工时间矩阵以及调整时间矩阵，依次得到每个工件的加工工序所对应的加工机器、加工时间以及调整时间。

为了确保染色体解码后产生活动调度，本文提出考虑调整时间的工序左移插入式解码方法。解码原则如下：

(1)如果工件j的工序Ojh在机器Mi上是第一道工序，则直接从它的前一道工序Oj(h-1)加工完毕后即可进行调整并加工工件；

(2)如果工件j两道工序即工序Ojh与Oj(h-1)在相同的机器上进行加工，并且两道工序紧邻，即它们之间没有其它工件进行加工，此时仅考虑一次调整时间；否则，分别考虑各自的调整时间；

(3)如果工序Ojh是工件j的第一道工序，那么直接从所在机器的零时刻开始调整工件然后加工即可。否则，从所在机器左边开始查找所有空闲时间段[TSi,TEi]，TSi表示空闲时间段的开始时间，TEi表示空闲时间段的结束时间。考虑到工件调整时间，按照式(5)得到工序Ojh最早加工开始时间ta，能满足工件加工工序的顺序约束。

ta=max{Pj(h-1),TSi}

(5)

按照式(6)判断空闲间隔时间段能否满足插入条件，如果满足则插入到当前空闲时间段中；否则，按照式(7)的时间tb在机器Mi上进行加工，其中TMi表示当前机器Mi最后一道加工工序的结束时间。以此类推，依次读取工序部分染色体，直至染色体结束。

ta+Adjustmenti+Tijh≤TEi

(6)

tb=max{Pj(h-1),TMi}

(7)

2.2 FJSP的初始化方法

在使用遗传算法求解目标问题时，初始解的优劣直接影响到算法的求解质量和解的收敛速度。由于FJSP不仅要解决机器选择问题，而且还要解决加工工序排序问题。针对FJSP这些特点，机器选择部分采用文献[11]提出的GLR机器选择方法。该方法包括：随机选择(Radom Selection, RS)、局部选择(Local Selection, LS)和全局选择(Global Selection, GS)。为了保证初始种群的多样性，增加种群的选择性，使其在计算过程中不至于提前结束，工序排序部分采用随机选择(Radom Selection, RS)的初始化方法。

2.3 FJSP的交叉和变异

2.3.1 自适应交叉算子

交叉操作是根据自然界生物交配的原则，对种群中的染色体随机配对，以一定的概率交换种群之间的基因片段。在交叉过程中，以一定的方式交换两个配对染色体的部分基因，产生两个新的染色体。交叉方法包括：单点交叉法、两点交叉法，多点交叉法，均匀交叉法等。依据本文研究的带有调整时间FJSP问题特点，并满足交叉时的计算效率和产生的染色体对所求问题的解的可行性。

机器选择部分：为保证交叉后产生的基因的先后顺序不变，采用均匀交叉法。

(1)在区间[1，L]内随机的产生一个整数r。

(2)根据随机数r，随机生成r个不等的整数。

(3)根据(2)产生的随机整数r将父代染色体中的P1/P2中包含的基因复制到子代C1/C2中，保持顺序和位置不变。

(4)父代染色体中的P1/P2中余下的基因复制到子代C2/C1中，保持顺序和位置不变。

工序排序部分：采用改进的顺序交叉法，对每个染色体的多个工件进行操作。更好的继承的父代染色体中的优良基因。

(1)父代染色体P1/P2随机产生工件集Job。

(2)将父代染色体中的P1/P2中包含有Job的基因复制到子代中，保持顺序和位置不变

(3)将另一个父代染色体P2/P1中删除Job所包含的基因，按照从左到右的原则填入子代染色体中的空白基因位。

在交叉过程中本文采用自适应交叉概率以提高优良个体信息的保留。随着种群迭代次数的增加，为了减少对优良解个体信息的破坏，交叉概率逐渐降低。自适应交叉概率公式为：

(8)

Pc表示自适应交叉概率，Pc_max表示最大交叉概率CurInterStep表示当前迭代次数，MaxIterStep表示最大迭代次数。

2.3.2 自适应变异算子

变异操作是根据自然界生物变异的过程，以一定的概率改变种群增加种群的多样性。以很小的概率来改变染色体中基因的遗传片段。

对于机器选择部分，为保留优良个体的信息，保证机器顺序不被破坏。在变异染色体中随机选择r个位置。然后依据选择的每一个位置，对其位置上的机器设置为当前机器集中加工的时间最短的机器。

对于工序排序部分，本文采用邻域搜索变异操作，即在变异过程中在邻域范围内搜索产生多个子代，选择其中性能较好的子代为变异后的个体。具体步骤如下：

(1)在[0，1]内产生一个随机数r，若r小于变异概率Pm，转到(2)，否则转到(4)；

(2)随机在父代工序排序染色体中产生3个基因位，对此基因进行排序，将每一个排序的结果作为该位置上子代的基因，得到另外5个子染色体；

(3)计算当前6个染色体的适应值，选取其中最优的子染色体作为变异结果；

(4)结束。

本文采用自适应变异计算方法来改善进化性能，已达到尽量的保留较优的个体。自适应变异公式为：

(9)

Pm表示自适应交叉概率，Pm_max表示最大交叉概率CurInterStep表示当前迭代次数，MaxIterStep表示最大迭代次数。

2.4 算法流程

如图2所示，为采用自适应交叉算子和变异算子的遗传算法流程图。

图2 算法流程图

3 实例仿真

某模具公司的CNC生产车间是典型的柔性作业车间调度问题，在实际加工过程中，工件在不同机床上进行加工时都存在安装、定位等调整时间，在满足工件工艺的前提下尽可能的缩短生产周期，并尽可能的提高设备利用率。

依据上述改进的遗传算法，采用Matlab7.0编程，运行环境为P4 CPU，主频1.9GHz，内存4G的个人计算机。设置遗传算法的主要参数如下：种群规模40，交叉概率Pc_max0.8，变异概率Pm_max0.6，最大迭代代数为100代。

表2表示某加工车间7个工件在6台机器上的FJSP实例，表中括号外的数字表示该工序在对应机器上的加工时间，括号中的数字表示工序在当前加工机器上的调整时间，“-”表示该工件的工序不能在相对应的机器上加工。例如，表2中O11与M2对应的数值6表示工件J1的第一道工序在M2上的加工时间为6，调整时间为1。

表2 工件在机器上的加工时间和调整时间

图3、图4分别是在Matlab仿真平台中通过改进的遗传算法对未考虑调整时间和考虑调整时间的柔性作业车间调度问题进行运算的输出结果的甘特图。图3中的完工时间为37，图4中的完工时间为55，可以明显看出调整时间在实际生产过程对调度方案存在较大影响。图3中不同的颜色代表不同的工件。图4中浅灰色部分代表对应工序在机器上的调整时间，其它颜色和图3中一样代表各道工序在相应机器上的加工时间。对比两图可看出带有调整时间的调度更复杂，更加符合实际机件加工，使柔性作业车间调度问题更加满足实际需求。

图3 未考虑调整时间的调度甘特图

图4 考虑调整时间的调度甘特图

图5 考虑调整时间FJSP求解过程收敛曲线

图5为改进遗传算法求解带调整时间的表1和表2问题时的收敛曲线。实现为每代中最优解的迭代过程，虚线为每代种群中个体目标值的平均值收敛过程。每代最优解的收敛曲线是不断下降，逐渐收敛到最终结果；而种群均值前期是快速下降，后期呈现波浪式的上下跳动，并没有明显的下降趋势。这个问题也是后期研究工作中需要从问题本身特征进行分析，设计更加符合问题本身的算法，使其能够更快速的进行收敛。

4 结束语

实际生产过程中，工件在加工设备上进行加工时存在调整时间，为了能够更有效的指导实际生产。本文将调整时间和加工时间作为独立因素进行考虑，以最大完工时间最小为优化目标，建立了考虑调整时间的柔性作业车间调度问题模型。通过对遗传算法进行改进对提出的模型进行求解，设计了考虑调整时间的工序左移插入式解码方法，解码成活动调度，提高算法运行效率。最后，在Matlab仿真环境中对实际案例进行运算，通过对未考虑调整时间和考虑调整时间的结果比较，验证了考虑调整时间的问题模型更加符合实际生产，同时也验证了建立的模型和改进的算法是可行的和有效的，能够更有效的指导实际生产。