离散回溯搜索算法求解多柔性作业车间调度

董 海, 徐晓鹏

(1沈阳大学 应用技术学院,辽宁 沈阳 110044; 2.大连理工大学 机械工程学院,辽宁 沈阳 110044)

0 引言

随着柔性化生产的广泛应用，柔性车间调度问题获得大量研究，除传统启发式算法外，一些学者提出采用多种新型算法求解柔性车间调度问题[1～8]。

文献[9～12]对车间生产中的工序顺序柔性开展了全面的研究，总结和提出了描述方法。文献[13～16]在实际车间调度问题中除考虑机器因素外，还要考虑工人的因素，因此引入了人力资源约束。

本文考虑车间中掌握多种技能的工人和并行工序顺序柔性，建立模型，并提出可快速得到处于非支配解集的多种调度方案的求解算法。

1 多柔性作业车间调度问题模型

1.1 问题描述

在实际柔性车间生产中，同一优先级的工序无次序要求，而不同优先级的工序需按顺序加工，如图1所示，其中J1、J2为两个工件，J1的工序为O111、O121、O122、O131、O132，分属F11、F12、F13三个优先级。

车间有数目有限的多能工，不同工人都有其所会操作的机器和所会加工的工序，如图2所示。

综上，本文提出多柔性作业车间调度问题(Multi-Flexible Job-Shop Scheduling Problem，MFJSP):

有n个工件J={J1,J2,…,Jn}，m台机器M={M1,M2,…,Mm}，w名工人W={W1,W2,…,Ww}；加工一个工件Ji的工序分为Li层优先级F={Fi1,Fi2,…,FiL(i)}，优先级Fij中包含Kij道工序Oij={Oij1,Oij2,…,OijK(ij)}；优先级Fij中的工序Oijk只能在优先级Fij-1中所有工序完成之后被加工；每名工人Wv的技能都由一个二进制矩阵Sv表示，矩阵Sv第p行中第a列的元素表示其是否会操作机器Mp完成第a列所对应的工序，如表1所示。

表1 多能工与其所会的机器和工序

1.2 符号定义

除前文已有定义外：

i、e为工件下标，J表示工件；L表示对应工件所包含优先级的数量；j、f为优先级下标；k、q、g为工序下标；p、r为机器下标；v为工人下标；Sv为工人Wv的技能矩阵，元素为0或1表示工人会或不会操作机器完成列所对应的工序；t为加工工序的用时，transTpr为工件从机器Mp转移到到机器Mr的耗时；Pp为机器Mp加工工序时单位时间的耗能；Cijk、Cifg、Cefg为工序Oijk、Oifg、Oefg的完成时间，Ci为工件Ji的完成时间；

模型中决策变量定义如下：

xefgv同上定义。

1.3 建立数学模型

MFJSP数学模型如下:

(1)

(2)

(3)

式(1～3)优化目标：最大完工时间、总耗能和工人工时方差。式(4～9)约束条件：式(4)确保在加工一道工序的过程中不换人和机器；式(5)确保优先级顺序，其中不等式右侧前半部分为前一优先级所有工序均完成且运输到当前工序所在加工机器的时刻；式(6)和式(7)分别确保机器和工人不在同一时间被占用；式(8)确保工序加工的独立性，其中求和的目的是找到加工工序的机器和工人；式(9)通过引入技能矩阵Sv(p,ijk)，确保工人只用他所会的机器加工他所会加工的工序，同时即确保了机器只能加工它所能加工的工序。

1.4 编码与解码

采用整数编码，用四条染色体描述一种调度方案。其中，两个染色体分别编码机器和工人，其上上的基因值分别代表基因位置对应工序所选择的机器和工人，如图3所示。

另两条染色体将用于编码工序排序：一条染色体的基因为工件下标，其排列顺序为加工次序；另一条的基因为从1到工序总数的不同整数，其基因位置对应不同工序，如图4所示。可将图4中工序排序1染色体中的相同工件按顺序和各优先级的工序数分成各优先级，如图5所示。对图5中的相同优先级中的工序按图4中工序排序2中染色体上的基因从小到大的顺序进行排序即可得到实际的加工顺序，如图6所示。

本文的编码方式，可从编码上去除不符合加工顺序要求的情况，节省检查编码是否满足加工顺序的计算资源。

2 离散回溯搜索算法

为对算法做离散化处理并更好地从整体上反映对多目标优化问题的优化结果，本文将用于连续优化问题的回溯搜索算法(Backtracking Search Algorithm，BSA)做离散化处理，并基于Pareto优化和快速非支配排序方法对其进行改进，提出了离散回溯搜索算法(Discrete Backtracking Search Algorithm，DBSA)以求解所提出的模型。

2.1 回溯搜索算法简述

BSA是一种新型算法[17]，过程如下:

(1)初始化P(当前种群)和OldP(历史种群)；

(2)通过公式(10)、公式(11)更新OldP；

(10)

OldP=permuting(OldP)

(11)

(3)根据公式(12)生成Mutant;

Mutant=P+F×(OldP-P)

(12)

(4)使用P和Mutant根据公式(13)生成V；

(13)

(5)根据公式(14)从V中选择个体进入P；

(14)

(6)重复步骤(2)～(5)，直到满足条件。

以上步骤中，步骤(2)和步骤(5)分别被称为选择I和选择II，步骤(3)和(4)分别被称为变异和交叉。

2.2 精英化历史种群

为三个目标函数选取l,m,n个权重值，则可由三个单独的目标函数加权得到l×m×n种新函数，在OldP中用每种函数下的最优个体替换其它个体。该过程同时确保OldP的质量和多样性。可以使OldP在变异步骤中更好地引领P的进化。

2.3 离散化变异交叉过程

本文引入遗传算法中的交叉算子，使BSA中的变异交叉过程可以处理离散编码。将oldp中机器选择和工人指派染色体上的基因交换到p上；在工人能力约束下更改p中工人指派染色体上的基因；遴选工序顺序1染色体上的基因位置，对比oldp和p在这些位置上的工件编号，选取oldp和p其它位置的基因进行补充，使oldp的基因交换到p上后，p中染色体上各工件编号的总数不变；对工序顺序2染色体，分别以等概率选择采用基于位置的交叉算子和线性次序交叉算子[18]交换oldp的基因到p上。

2.4 对选择Ⅱ的改进

本文在步骤选择Ⅱ中将P和V混合，用快速非支配排序方法[19]将个体分归不同非支配等级，按非支配等级从低到高逐层将其中个体更新到P中。相较将P和V中的个体随机配对进行选择，该方法从Pareto优化角度看，可以在每次迭代中获得更优质的解集。

3 算法验证/仿真实验

MFJSP问题首次被提出，故本文实验基于自己创建的数值实例，分别使用遗传算法(GA)[20]、粒子群算法(PSO)[21]、人工蜂群算法(ABC)[22]和DBSA，对其进行求解，并选取相同时间下各算法的结果进行对比，图7中为四种算法对最大完成时间的收敛曲线；图8为DBSA运行30min后所得的Pareto非支配解集。

由图可得，DBSA相对其它智能算法，收敛速度快，跳出局部最优解能力强，且最终可获得解均匀分布的Pareto非支配解集。图9为解集中一解对应车间调度方案的甘特图，由图可以看出其满足约束条件。

4 结束语

本文针对同时具有机器、工人和工序柔性的作业车间调度问题，建立了多目标优化模型，并给出四染色体整数编码方案，可在编解码过程直接满足模型的约束条件；在BSA的基础上，重新设计了交叉变异步骤，利用快速非支配排序方法更新当前种群，并提出精英化种群方法。新算法在求解数值实例时，与多种智能算法相比，具有更快的收敛速度和更强的跳出局部最优解的能力。