应用禁忌粒子群算法的车间调度及其并行化实现

郑天华，王佳斌，蔡宇翔，彭凯

(华侨大学 工学院，福建 泉州 362021)

混流混合车间调度涉及作业车间调度和流水车间调度，生产过程包括零件加工、部件装配、产品总装配.由于作业车间和流水车间联系紧密，对某一个车间进行单独优化都可能导致大量库存和生产周期延长.因此，混流混合车间调度需要考虑作业车间调度和流水车间调度.

目前，对车间调度的研究处于快速的发展阶段.一些学者采用精确算法对车间调度问题进行研究，如拉格朗日松弛算法[1-3]和分支定界算法[4-6].随着车间调度规模扩大，精确算法效率降低，而智能算法得到更广泛的应用.Figielska[7]采用禁忌搜索算法研究两个阶段混合流水车间问题.Marichelvam等[8]采用离散萤火虫算法求解双目标混合流水车间问题.Naderi等[9]采用帝国主义竞争算法求解带有子模块和准备书简窗的车间调度问题.此外，混合人工蜂群算法[10]、混合果蝇优化算法[11]、混合松鼠搜索算法[12]等也都应用于车间调度问题中.

李修琳等[13]采用混合遗传算法，以最小化缓存区库存为目标，研究混流混合车间集成调度问题.鲁建厦等[14]采用博弈粒子群算法，以最小化部件车间齐套性和库存为目标，研究混流混合车间调度.王猛[15]提出免疫遗传算法，以最小化最大完工时间为目标，研究多级车间集成调度问题.Lou等[16]采用免疫克隆算法解决混合车间调度优化问题，并取得有效的解决方案.

Hadoop集群是目前广泛使用的大数据处理主流技术和系统平台，在大规模分布式的存储和批处理上有强大能力.刘佳耀等[17]针对大数据时代下Slope One算法推荐效率不高的问题，改进算法并将其在大数据平台上实现并行化.蔡春晓等[18]结合车牌识别算法和Hadoop集群，实现算法的并行化，有效地改进算法的运行效率.王诚等[19]结合孤立森林算法和大数据平台，实现算法的并行化，提高了算法运行的效率.

三段式[13-14]编码的算法可以有效解决混流混合车间内小批量的调度问题.面对大批量问题时，采用现有的智能算法易陷入局部最优的问题，无法得出最佳的调度的方案.基于此，本文研究禁忌粒子群车间调度算法及其并行化实现.

1 问题的建模

混流混合车间，如图1所示.为研究混流混合车间调度问题，给出以下5个假设[13]：

1) 在流水车间，只对自制件进行加工，不考虑外购外协件；

2) 生产之前，车间内的设备和工位没有制品且已经准备就绪；

3) 加工时间包括准备时间、搬运时间；

4) 车间内相同的零件之间有工序的约束，不同的零件不存在工序的约束；

5) 零件加工车间为部件装配车间、产品总装配车间加工一批零件，部件装配车间为产品总装配车间加工一批部件，装配工将不满足装配工位的零件或部件放在缓冲区中，配送的时间假定为零.

图1 混流混合车间Fig.1 Mixed flow mixing workshop

在加工过程中，零件加工车间要满足工序约束和设备约束.零件在对应的设备机器上按照工序进行加工；部件装配车间和产品总装配车间在装配过程中，要满足工序约束和工位约束，零件在对应的工位上操作，前置工序操作完成才能进行下一步的工序操作.零件加工车间的设备约束为

Ei，j-ti，j+r×ci，h，j≥Ei，h，

(1)

零件加工车间的工序约束为

Eg，i-ti，g+r×di，g，j≥tg，i，

(2)

部门装配车间和产品总装配车间的工位约束为

(3)

部门装配车间和产品总装配车间的工序约束为

(4)

部门装配车间和产品总装配车间的时间约束为

Ex，k=tx，k+max(Ex-1，k，Ex，k-1).

(5)

2 粒子群算法

2.1 传统粒子群算法

传统粒子群算法(PSO)模拟鸟群觅食过程.在这个过程中，每个粒子的解对应粒子相对应的位置.传统粒子群算法对应的速度(vnex)[20]为

vnex=wvcur+c1r1(p*-xcur)+c2r2(g*-xcur)，

(6)

xnex=xcur+vnex.

(7)

式(6)，(7)中：w，c1，c2分别为惯性系数，个体认知系数和社会认知系数；vcur和xcur为当前的速度和位移；vnex和xnex为下一步的速度和位移；p*为个体经历过最好的位置；g*为全局最优位置；r1，r2为一组(0，1)内的随机数.

2.2 禁忌粒子群算法

传统粒子群算法搜索速度快、收敛效率好，但容易陷入局部最优的情况.针对传统粒子群算法中存在的问题，对粒子群算法进行改进.在传统粒子群算法寻优的过程中，加入禁忌算法，对粒子种群进行随机交换组合，加强算法寻优的能力，防止算法陷入局部最优的可能.

图2 禁忌粒子群算法流程Fig.2 Forbidden particle swarm algorithm flow

2.3 禁忌粒子算法流程

禁忌粒子群算法流程，如图2所示.禁忌粒子群算法(TSPSO)算法有如下7个流程：

1) 设置PSO的相关参数，置空禁忌表；

2) 对PSO中的每个粒子计算适应度值，更新个体的最优解及群体的最优解；

3) 更新粒子群中的位置及速度；

4) 将粒子群中的每个粒子进行随机交叉变异，计算变异后的粒子适应度；

5) 若新的适应度比群体最优解好，则更新禁忌表中，更新群体最优解，若不满足，就转到流程6)；

6) 若新的解比变换前的粒子对应的解更好，则将这个粒子及对应的解放入禁忌表，即更新禁忌表；

7) 若迭代次数大于所设定的最大迭代次数，则将这个最优解输出，若不满足，则转到流程2)中.

2.4 禁忌粒子群车间调度算法

2.4.1 编码 对3个车间的零件和部件及产品进行编码，编码完成后，对车间进行统一优化调度.首先，确定产品总装配车间、部件装配车间及零件加工车间产品数量最小比例，对其进行统一编码.其次，用字母代表产品、部件和零件，相同字母代表同样的产品、部件和零件.如零件加工车间所生产的零件为A，B，C；部件装配车间的部件为D，E；产品总装车间的产品为F，G，H，那么，算法编码为(A，B，C，D，E，F，G，H).

2.4.2 适应度函数 适应度函数(G)为

G=min(Ei，j+Ex，k+Ey，s).

(8)

式(8)中:Ey，s代表产品总装配车间所有产品y在设备s完成装配的最大完工时间约束.

2.4.3 粒子更新 采用式(6)，(7)对粒子种群进行更新.将禁忌算法加入传统粒子群算法中，对粒子群进行随机的交换组合，增强算法寻优的能力，防止算法进入局部最优的可能.

图3 算法并行化思路Fig.3 Idea of algorithm parallelization

2.4.4 算法并行化实现 采用Java软件编写对应的Map函数和Reduce函数，并调用Hadoop集群环境，结合禁忌粒子群算法和Hadoop集群，解决混流混合车间调度的问题.禁忌粒子群算法在运行过程中，读取相关的车间数据，设定启动多个Map函数和Reduce函数进行处理.在Map函数阶段，计算禁忌粒子群算法中每个粒子，即根据所设置的目标函数，计算相对应的适应度；在Reduce函数阶段，输出粒子群中最优的适应度.算法并行化思路，如图3所示.

3 实例验证

3.1 混流混合车间调度实例

以装载机制造车间为例[15]，对算法进行验证.装载机制造车间是由零件加工车间、部件装配车间、产品总装配车间组成的.产品需求矩阵，如表1所示.表1中：Q1，Q2，Q3，Q4为生产的产品.A～H为零件；X，Y为部件；-表示产品和需求的部件没有关系；1表示产品和需求的部件有对应关系.

表1 产品需求矩阵Tab.1 Product demand matrix

零件按A，B，C，D，E，F，G，H的顺序进行加工，零件加工时间(tp)，如表2所示.表2中：M1～M10分别表示设备.

表2 零件加工时间和工序Tab.2 Part processing time and processing sequences

部件装配车间主要负责的是部件X，Y的装配，部件装配时间(tc)，如表3所示.

产品总装配车间流水线共有33个装配工位，工序按工位的顺序进行排序，产品总装配时间(tt)如表4所示.

表3 部件装配时间Tab.3 Assembly time of components

表4 产品总装配时间Tab.4 Total assembly time of products

图4 算法进化曲线Fig.4 Algorithm evolution curve

生产计划期内产品Q1，Q2，Q3，Q4的任务分别为320，160，320，320 台，最小生产循环为2∶1∶2∶2.根据已知条件，部件X，Y分为480，640个，最小的生产循环为3∶4；零件A～H分别为480，640，480，640，480，640，480，640个，最小生产循环为3∶4∶3∶4∶3∶4∶3∶4.

Hadoop集群由4台机器组成，选取其中一台机器作为Master节点，其他3台作为Slave节点.设置禁忌粒子群算法的有关参数如下：种群的大小为20；迭代次数为300次；w为0.1；c1，c2都为1.TSPSO运行的最优解为15 583 s；遗传算法(GA)的最优解为15 700 s；免疫遗传算法(IA)[15]的最优解为15 679 s.实验结果表明，禁忌粒子群算法(TSPSO)可有效避免局部最优的可能.算法进化曲线，如图4所示.图4中：tb为最优解；k为迭代次数.

3.2 算法对比

在种群大小为20，迭代次数为50的情况下，分别用最优解(tb)、平均值(tvar)对比3种算法的性能.结果表明，TSPSO收敛性能好、收敛的速度快且不易陷入局部最优.3种算法性能对比，如表5所示.

禁忌粒子群算法和遗传算法及免疫遗传算法的每个车间运行时间(tr)对比，如表6所示.表6中：δ为对比差比例.

表5 3种算法性能对比Tab.5 Performance comparison of three algorithms

表6 3种算法的每个车间运行时间对比Tab.6 Running time comparison of each workshop of three algorithms

由表6可知：TSPSO在产品批量大的情况下，在零件加工车间、产品总装配车间车间所得出的效果都比GA和IA更优.因此，TSPSO在大批量的情况下可对总体的调度进行优化.

4 结束语

并行化的禁忌粒子群算法，在面对产品批量较大的情况下，可以有效地避免陷入局部最优的问题，解决了批量大的情况下车间调度的问题.未来考虑对3个车间进行独立编码，进一步对车间调度进行优化，得到更好的调度的方案；对粒子群算法进一步改进，结合大数据平台提高算法的效率.