改进遗传算法在车间调度问题中的应用

2021-07-18方成刚洪荣晶吴伟伟

南京工业大学学报(自然科学版) 2021年4期

杨帆，方成刚，洪荣晶，吴伟伟

(1.南京工业大学机械与动力工程学院，江苏南京 211800；2.扬州大学机械工程学院，江苏扬州 225000)

调度是指在合理的时间内将有限的资源进行分配，以满足一个或多个优化目标的过程。车间调度是整个先进生产制造系统的核心，其中作业车间调度问题(JSP)作为生产过程中的关键模块是典型的调度问题之一[1-2]。在作业车间中，加工系统中有m个功能各不相同的机床、n个加工路线不同的工件，各工件的每道工序按照其工艺路线对应1台机器进行加工。柔性作业车间调度问题(FJSP)与JSP相比,每道工序可选择不同机床进行加工，已被证实是复杂的NP-Hard问题[3]。

柔性作业车间调度作为智能制造的核心技术，对其深入研究具有重大的理论意义和实际价值。目前对于FJSP的研究集中在各种智能算法，例如遗传算法、粒子群算法、模拟退火算法等。王雷等[4]应用遗传算法解决了一种考虑AGV运输时间的柔性作业车间调度问题。陈明等[5]将粒子群算法应用在一个多目标柔性作业车间调度模型并成功得到一组 Pareto 解集。黄海松等[6]提出了一种基于改进模拟退火算法的调度策略。

遗传算法(GA)相比其他算法具有鲁棒性强、搜索能力强等特点，在FJSP这类大规模收敛问题中得到了广泛应用。但FJSP问题是典型的NP-Hard问题，在使用传统遗传算法对其求解时，往往不能得到满意的结果，并且FJSP包括机器选择和工序排序两个子问题。在进行遗传操作时，目前需要对其分别进行操作，这使得在编写算法时工作量较大。

交叉操作是遗传算法中的重要环节，对其进行改进有重要理论价值和实际意义，目前应用在FJSP问题中的交叉操作主要有部分映射交叉、次序交叉、循环交叉、基于位置的交叉等方式[1]，但以上传统交叉方式对父代染色体依赖较强，造成算法的寻优能力较弱，往往得不到理想解。赵诗奎等[7]采用双链编码，使用基于工件的机器交叉和两点混合交叉的方式提出一种新型初始机制的遗传算法解决了FJSP问题。吴秀丽等[8]采用基于工序的编码方式，在解码时引入机器顺序矩阵和时间矩阵，选择线性次序交叉方式解决了柔性作业车间多目标调度优化问题。不论是采用双链编码，或加入机器、时间矩阵，这都大大增加了编程的工作量。针对以上问题，笔者采用基于工序的单链编码，以最大完工时间最小为目标，提出一种基于元胞数组的解码方式和一种新的单点交叉操作。

1 部分柔性作业车间调度的基本描述

1.1 问题描述

部分柔性作业车间调度问题(P-FJSP)描述为：车间内有机器m台，待加工工件n个，每个工件包含一道或多道工序，至少有一道工序可选择车间内多台机器加工且至少有一道工序不能选择所有机器进行加工。P-FJSP要解决的问题是为每道工序选择加工机器并且确定每台机器上各工序加工的先后顺序，具体事例如表1所示。

表1 P-FJSP举例Table 1 An example of P-FJSP

表1中Ji表示工件号，Oi，j表示工件i的第j道工序，Qi表示机器号。表中数字表示此工序在对应机器上的加工时间(本文加工时间默认为min)，符号“—”表示该工序不能在表中对应机器上加工。例如表1中，工件J1的第2道工序O1，2在Q1和Q2上的加工时间分别为15和8 min，但不能在Q3上加工。

1.2 数学模型

定义符号n为工件总数、m为加工机器总数，li为工件i的工序数，P-FJSP可表示为

(1)

式(1)为基于完工时间的目标函数，f是最大完工时间最小性能指标，其中Ci代表工件的加工完成时间。

s.t.Cih≤Si(h+1)

(2)

式中：i=1，2，…，n;h=1，2，…，li。

式(2)表示工艺约束，其中Cih为工件i的第h道工序的加工结束时间，Sih为工件i的第h道工序的加工开始时间。

Cjhk-Cigk+A(1-yijk)≥Pjhk

(3)

式中：i，j=1，2，…，n;h=1，2，…，lj;g=1，2，…，li;k=1，2，…，m；n、m分别代表工件数和机器数，为最大变量值。

式(3)是工序唯一性约束，表示某台机器在同一时刻只能加工一道工序，其中Cjhk、Cigk分别为工件j的第h道工序和工件i的第g道工序在机器k上的加工完成时间，Pjhk为工件j的第h道工序在机器k上的加工时间，A为一个足够大的正数。

(4)

式中i=1，2，…，n;h=1，2，…，li。

式(4)是机器唯一性约束，表示某道工序在同一时刻只能被一台机器加工，其中mih为工件i的第h道工序可选的机器集。

Sih+xihkPihk=Cih

(5)

式中：i=1，2，…，n;h=1，2，…，li;k=1，2，…，m。

式(5)表示某道工序在加工过程中不可中断。

2 改进遗传算法设计

2.1 算法流程

本节的设计过程均以表1中实例为对象。算法流程图如图1所示，利用元胞数组储存各工件的工序、加工时间、可选机器等信息，并引入随机算子进行解码，在遗传操作中加入保优策略并引入新的交叉方式，算法的终止条件为是否达到迭代次数。

图1 P-FJSP求解算法流程Fig.1 Algorithm solving process of P-FJSP

2.2 种群初始化

编码采用基于工序的单链编码，编号链代表遗传算法中操作的染色体。以工件号表示的工序码代表遗传算法中操作的基因位，工件号出现的次数代表该工件包含的工序数，同工件出现的顺序表示工序顺序。以编码122313312为例，第三个基因位的‘2’表示工件2的第2道工序。

2.3 解码操作

针对元胞数组的P-FJSP解码过程为

1)步骤一。按顺序取出染色体中的基因乘10，按照上述种群初始化规则加上工序号，将其储存在一行向量P中，如132113223中的第4个基因处理完后为12，在后续操作中对其分别进行取整和取余操作即可得到工件号和工序号；

2)步骤二。引入随机算子在元胞数组中随机取出对应工序的某个加工机器，存入一行向量M中，并将此工序的随机算子保存；

3)步骤三。取出步骤二中加工机器的对应加工时间，存入行向量T中。

2.4 适应度计算

根据约束条件将上述各机器上的工序进行排列，计算出最长加工时间,即为该条染色体的目标函数值，根据目标函数可知,种群中目标函数值越小，该条染色体质量越高。

2.5 选择操作

利用轮盘赌规则对种群中的各条染色体进行选择，目标函数值越小的被选择的概率越大。引入精英保留策略，将父代种群中最优的染色体直接放到子代种群中，并且不参与接下来的交叉、选择操作，直到有更优的个体替换它。采用此种选择方式可避免优质解的丢失，加快种群的收敛。

2.6 交叉操作

引入随机算子提出一种单点交叉加随机打乱的方式，以减小子代染色体对父代的依赖，扩大种群的多样性，步骤为

1)步骤一。取出相邻的两条染色体A和B，随机生成交叉点。

图2 交叉操作步骤一Fig.2 First step of the cross operation

2)步骤二。交换A、B后半段染色体得到C、D。

图3 交叉操作步骤二Fig.3 Second step of the cross operation

3)步骤三。为避免不合法的染色体出现，用各个工件的实际工序数减去后半段各工序出现的次数，得到交叉点前合法的工序数并按顺序填入。

图4 交叉操作步骤三Fig.4 Third step of the cross operation

4)步骤四。为增加种群多样性随机打乱交叉点前部分染色体顺序，得到交叉后的染色体新A、新B。

图5 交叉操作步骤四Fig.5 Fourth step of the cross operation

2.7 变异操作

为了避免非法染色体的产生，变异操作采用同一染色体的两个基因交换的方式，即随机在染色体上选择两个基因位，判断这两个基因位上的基因是否相等，若相等则重新选择，若不相等则直接交换。

3 实例验证

为验证所提出的改进遗传算法在P-FJSP中的有效性和优越性，利用传统单点交叉方式和改进方式对具体算例进行对比验证。用Matlab编程实现，计算机内存8 GB，处理器为Intel(R) Core(TM)i5-8250U，主频1.6 GHz。算例采用高亮等[9]在著作中提出的8×8部分柔性作业车间调度问题算例，结果见表2。遗传算法中种群规模设置为40、交叉概率Pc为0.7、变异概率Pm=0.1，最大遗传代数根据文献[10]提出的规则设置为100。