李　浩　毕　利　靳彬锋

(宁夏大学　宁夏 银川 750021)

0　引　言

车间调度问题(JSP)在生产管理和组合优化等领域一向都是热门问题[1]。车间调度问题在数学上已被证明是NP困难问题[2]。目前解决NP问题的方法主要有两种：利用数学方法求最优解，往往有整数规划、动态规划、分支定界法和回溯剪枝法等非智能算法；利用智能算法求解其近似解(如：遗传算法、hopfield神经网络、禁忌搜索、模拟退火、蚁群算法和粒子群算法等[3])。求解JSP的方法通常是求解一组工件的工序在一组机器上的分派[4]，而FJSP一般指的是机器选择问题和工序调度问题这两个问题的集合，是JSP的一个扩展[5]。因为加入了机器选择的考虑，因此FJSP较之JSP更加困难。在实际的生产环境下，FJSP更具有普适性，故FJSP具有重要的理论意义和研究意义。

近些年来，多目标FJSP因为更切合制造业实际生产中的需求而引起众多学者的关注，并衍生了多种用于处理FJSP的智能算法[6]。目前解决FJSP的方法有加权法和利用pareto优化策略求解非劣解集。前者的处理过程是将不同的目标函数赋值以不同的权重，从而使得多目标问题转换为单目标问题后来进行求解；后者是在一组多个目标之间折衷的均衡解，也就是非劣解，求解多目标问题的关键就是找到数量足够多的且分布均匀的又具有代表性的非劣解集[7-8]。Rim等[7]在针对FJSP时提出了分布式和并行的处理方式，并且得到了较好的实验结果。Manas等[8]通过对粒子的不确定性来避免算法早熟，并证明QPSO算法的优越性。

随着时代的发展，离散车间制造业已逐渐转型，向半自动和全自动发展，但是到目前为止，众多学者在考虑离散制造业的车间调度问题时，还是会忽略加工工件的过程中的运输时间，即不考虑加工机器到下一个加工机器的运输时间问题。本文引入小车的概念，针对当前离散车间制造业半自动化(或者自动化)的特点，用来描述离散车间制造业中的半成品运输问题。

与遗传算法[9]相比，二者都需要进行种群的初始化和选择合适的适应度函数来评价系统，但粒子群算法是根据自己的速度来决定搜索方向的，只和pbest和gbest有关。整个搜索过程是跟随着当前最优解移动的过程，并且收敛于最优解的速度更快[10]。与hopfield神经网络算法[11]相比，二者都有参数需要调整，但是PSO的结构和参数更加简单，因为参数数量少，所以调参更加容易。但是如果参数设置不合理会导致PSO收敛速度过慢或者在最优解附近来回震荡导致算法不收敛。同时PSO算法也存在着容易陷入局部最优解和早熟等的不足。因此，本文采用变参数策略、交叉变异机制，提出基于变参的交叉变异粒子群算法CAPSO(Cross and Aberrance Particle Swarm Optimization)，来避免陷入局部最优和早熟等问题。

1　FJSP多目标优化

1.1　FJSP描述

FJSP可以描述为：N个待加工工件在M台机器上加工，每个待加工工件有多步工序，每道工序可以在多台机器上加工，但是工序的前后顺序有要求，每台机器可以加工不同工件的不同工序，调度的目标就是把待加工工件的加工工序合理地分配到各个机器上去，在满足某些特定的约束条件的情况下使得车间调度的性能指标最优。

1.2　FJSP多目标优化模型

首先，FJSP需要满足如下条件：

(1) 系统开始运行时，每台机器都可以被使用。

(2) 系统开始运行时，任一待加工工件的第一步都可以被加工。

(3) 每种待加工工件的任一工序在可用机器上的加工时间是确定的。

(4) 每种待加工工件的加工工序是有先后顺序的。

(5) 工件的加工时间应当包括该工件在机器上的准备时间和加工时间。

(6) 在相同时间内，每个待加工工件有且仅能在一台可用机器上加工。

(7) 在相同时间内，可用机器要么继续闲置，要么最多只能加工待加工工件的一道工序。

(8) 从前一个加工机器运输到下一个加工机器的运输时间是确定的。

(9) 每个待加工工件的任何一道工序有且只有在前一道工序加工结束并且运输到下一个机器上后，这一道工序才可以在可用机器上进行加工。

本文选取的三个目标为：最大完工时间、最小成本和机器最大负荷。

(1) 最大完工时间：

minF1=min{max{maxcj}+cartime}

(1)

(2) 最小成本:

(2)

(3) 最大负荷：

(3)

其中：

F1：工件的完工时间；

F2：加工成本；

F3：机器负荷；

Cj：工件j的完工时间；

cartime：小车运输时间;

CV:机器运转成本;

CS:机器闲置成本;

tijk:工件i的第j道工序在机器k上的加工时间;

Xijk: 决策变量，表示工件J的第i道工序是否选择在机器K上进行加工；Xijk=1表示机器k被选中，在机器K上进行加工；Xijk=0表示机器k未被选中；

T*:多次实验获得的完工时间的值；

FDK: 第K台机器的动态耗费率；

FSk: 第K台机器的静态耗费率。

对最大完工时间、最小成本和最大负荷这三个目标函数进行量纲归一化处理：

(4)

(5)

1.3　约束条件

(1) 时间约束：

tijk≥0且ti0k=0

(6)

Stijk>0且Sti0k=0

(7)

Stij>0且Sti0=0

(8)

(2) 资源约束:

(9)

(3) 工序约束:

(10)

1≤j≤nj

(11)

1≤i≤n

(12)

1≤k≤m

(13)

(4) 费用约束:

FDk>0且FD0=0

(14)

FSk>0且FS0=0

(15)

2　CAPSO算法

2.1　编码和解码

本文采用工序和机器分别编码的方式进行编码[12]，例如:

Xi=[2 1 3 2 1 3 1 2 3 2 3 2 3 4 1 2 1 3 2 4]

即等价于：

Xprocess=[2 1 3 2 1 3 1 2 3]

Xmachine=[2 3 4 1 2 1 3 2 4]

式中：Xprocess代表的是加工工序，Xmachine代表的是对应工序中所选择的机器；Xprocess中“1”出现三次，表示工件1的加工工序一共有三步， “1”、“2”、“3”、“4”四个不同的数字出现表示一共有四种工件需要进行加工；Xprocess中“1”出现两次，表示选择机器1作为加工机器的工序一共有两道；Xprocess中第一次出现的“1”表示工件1的第一道工序，对应到Xmachine中的“3”，表示工件1的第一道工序选择在机器3上进行加工，Xprocess中第二次出现的“1”表示工件1的第二道工序，对应到Xmachine中的“2”，表示工件1的第二道工序选择在机器2上进行加工，以此类推。

2.2　位置和速度的更新

在标准的PSO算法中，粒子在空间中搜索的速度和位置由式(16)和式(17)确定：

vt+1=w×vt+r1×rand()×(Pt-xt)+

r2×rand()×(Gt-xt)

(16)

xt+1=xt+vt

(17)

式中：w为惯性权重；r1、r2为加速常数；rand()为区间[0,1]上均匀分布的伪随机数；Pt和Gt分别为t时刻粒子的自身最好位置和全局最好位置。Pt为粒子群自身飞过的最好位置，而Gt为粒子所对应的全局最好位置，它是整个群体所经历的最好位置。Xt=(xt1,xt2,…,xtn)与Vt=(vt1,vt2,…,vtn)为时刻t的位置和速度。

2.3　算法的改进

粒子群算法的运行过程是由信息传递的作用导致的粒子运动位置的变化。在该过程中，粒子的搜索能力，包括全局搜索能力和局部搜索能力是由惯性权重w、加速常数r1和r2以及最大速度Vmax三种参数共同作用的结果。其中惯性权重w使粒子拥有惯性运动，从而使其有能力搜索未知的求解区域。最大速度Vmax决定当前位置的解的效果的精度:若Vmax过大，粒子可能会飞过最优解的范围而来回震荡；若Vmax过小，粒子不能跳出局部较好区间，导致其陷入局部最优值。另外，加速常数r1和r2代表每个粒子靠近Pt和Gt位置的统计加速项的权重，若值过低会让粒子的迭代速度过慢，容易进入局部最优从而无法进入最优解区域，反之则粒子有可能突然冲向或越过最优解区域。因此，为了防止粒子陷入局部最优，本文利用交叉算子令粒子可以跳出局部最优。为了防止粒子冲过目标区域，每迭代一定次数，将设置r1和r2缩小一定的倍数来使得粒子的步长降低，同时设置最大速度限制，若粒子速度超过最大速度则重新设置速度。

2.4　CAPSO算法流程图及流程

图1为CAPSO算法的流程图。

图1　CAPSO算法流程图

具体步骤如下：

Step1初始化粒子群种群即随机产生所有粒子的位置和速度并确定其pbest和gbest。

Step2将每个粒子的当前位置与pbest进行比较，取较优解作为新的gbest。

Step3将每个粒子的当前位置与gbest进行比较，取较优解作为新的gbest。

Step4若满足变异条件则执行变异操作，否则执行Step5。

Step5更新粒子的速度和位置。

Step6判断是否满足终止条件，若满足则终止算法，gbest为最优解，若不满足则返回Step2。

3　实验结果

本文利用8×8的8工件8机器3工序的部分多目标FJSP例子加以描述。具体加工时间见表1。

表1　8×8F JSP车间调度

同时给出小车在不同机器上的运输时间，由于从自身到自身不需要运输时间，为了方便表示，故对从自身到自身的运输时间均为0。具体见表2。

表2　小车在8个机器间的运输时间

我们得出的实验结果见表3。从表3可以看出，CAPSO算法在解决离散车间制造业中多目标车间调度问题时，其产生的非劣解集中解的个数明显多于PSO算法和ACO算法。同时该算法在最大完工时间、最小成本和最大负荷均优于PSO算法和ACO算法。

表3　不同算法结果的比较

观察图2-图4，可以看出，CAPSO算法的非劣解相较之PSO算法和ACO算法来说，解的分布较集中、数量较多并且质量高。

图2　CAPSO算法的非劣解集

图3　PSO算法的非劣解集

图4　ACO算法的非劣解

4　结　语

随着社会的发展和进步，离散车间制造业的自动化已是必然趋势。本文正是基于此提出了“FJSP+小车”的思路来解决离散车间制造业自动化的实际问题。在传统的PSO算法中引入了交叉变异因子来降低粒子陷入局部最优的概率，同时通过对最大速度的限制和步长周期性的降低来使得粒子降低震荡的频率，并给出了CAPSO算法求解多目标柔性车间调度的算法步骤和流程图。经过仿真实验测试，验证了本算法在FJSP中的有效性。

[1] 熊锐, 吴澄. 车间生产调度问题的技术现状与发展趋势[J]. 清华大学学报(自然科学版), 1998(10):55-60.

[2] 徐俊刚, 戴国忠, 王宏安. 生产调度理论和方法研究综述[J]. 计算机研究与发展, 2004, 41(2):257-267.

[3] 杨开兵, 刘晓冰. 一种求解多目标组合优化的遗传局部搜索算法[J]. 计算机应用与软件, 2009, 26(8):16-17,119.

[4] 何霆, 刘飞, 马玉林,等. 车间生产调度问题研究[J]. 机械工程学报, 2000, 36(5):97-102.

[5] 侯晓莉, 刘永, 江来臻,等. 多目标FJSP的一维编码粒子群优化求解方法[J]. 计算机工程与应用, 2015, 51(13):47-51,71.

[6] 刘丽琴, 张学良, 谢黎明,等. 多目标柔性作业车间调度的Pareto混合粒子群算法[J]. 中北大学学报(自然科学版), 2013(2):48-53.

[7] Zarrouk R, Ettouil M, Bennour I, et al. Towards an Embedded Distributed Implementations of PSO Solutions for the Flexible Job Shop Problem[J]. Procedia Computer Science, 2015, 73:146-153.

[8] Singh M R, Mahapatra S S． A quantum behaved particle swarm optimization for flexible job shopscheduling[J]． Computers and Industrial Engineering, 2016,93(C)：36-44.

[9] 张静, 王万良, 徐新黎,等. 混合粒子群算法求解多目标柔性作业车间调调度度问题[J]. 控制理论与应用, 2012, 29(6):715-722.

[10] 魏巍, 谭建荣, 冯毅雄,等. 柔性工作车间调度问题的多目标优化方法研究[J]. 计算机集成制造系统, 2009, 15(8):1592-1598.

[11] 刘晓冰, 焦璇, 宁涛,等. 基于双链量子遗传算法的柔性作业车间调度[J]. 计算机集成制造系统, 2015, 21(2):495-502.

[12] 彭建刚, 刘明周, 张玺,等. 基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J]. 中国机械工程, 2015, 26(5):620-626.

[13] 王万良, 吴启迪. 基于Hopfield神经网络求解作业车间调度问题的新方法[J]. 计算机集成制造系统, 2001, 7(12):7-12.

[14] 刘胜, 于海强. 基于改进遗传算法的多目标FJSP问题研究[J]. 控制工程, 2016, 23(6):816-822.