吴正佳 付先旺 望 芸 刘秀凤

(三峡大学 机械与动力学院， 湖北 宜昌 443002)

求解FJSP的改进元胞粒子群算法

吴正佳 付先旺 望 芸 刘秀凤

(三峡大学 机械与动力学院， 湖北 宜昌 443002)

以企业的实际需求为依据，建立了柔性作业车间调度问题的数学模型；针对其特点，提出一种混合元胞粒子群优化算法，通过双层编码，将工件的加工顺序与加工机器位置信息数值化表示；引入遗传算法中的交叉、变异操作，改进了粒子位置更新方法；融入变邻域算法,改善算法局部搜索能力．通过仿真实验，结果表明：算法在求解能力方面有所提升，能够有效地求解柔性作业车间调度问题．

柔性作业车间调度问题； 双层编码； 混合元胞粒子群算法

0 引 言

车间调度在制造企业的组织生产中有着举足轻重的地位，对提高企业的生产效率、降低成本有着十分重要的意义[1]．随着市场竞争压力加剧，企业生产模式逐步向单件小批量转变，柔性制造在企业得到广泛应用，研究柔性作业车间调度问题(Flexible Job Shop Scheduling Problem, FJSP)就显得尤为重要．学者们在探索求解FJSP问题的方法中取得了一定的成果：李俊等[2]在模拟退火算法中引入新求解问题的编码方法，赵诗奎[3]提出一种融合两级邻域搜索和遗传算法的混合算法，刘晓冰等[4]提出了改进的双链量子遗传算法，吴秀丽等[5]提出了一种改进的细菌觅食优化算法，赵敏等[6]提出了一种改进人工鱼群算法．可以看出，利用多种算法进行优势互补构成混合算法是研究的主流．事实上，绝大多数智能算法(元启发式算法)都采用单一的领域结构，很难有效地平衡搜索深度和搜索广度，仅适合求解单一适应度地形问题，很难有效解决复杂柔性作业车间调度问题．

粒子群算法(PSO)[7]是近年发展起来的一种群智能优化算法，该算法能在合理的时间内求得问题的满意解，得到了学者的广泛关注和研究；元胞粒子群优化算法(CPSO)[8]是在PSO基础上，引元胞自动机的原理而形成的新型算法，使解的多样性得以维持，避免了算法早熟现象，但是该算法存在着收敛速度慢、易陷入局部最优解的缺点；变邻域搜索(VNS)[9]通过系统地改变搜索区域，能够很好地跳出局部最优．因此，本文针对柔性作业调度问题的特点，通过将上述算法有机地结合，充分发挥各算法的优势，以提高混合算法的性能，拓宽算法的应用领域．

1 FJSP问题描述与模型建立

1.1 FJSP问题描述

柔性作业车间调度问题一般描述为：将n个工件J={J1，J2，…，Jn}安排至m台机器M={M1，M2，…，Mm}上进行加工．每个工件由一道或多道工序组成，工件的各工序是已知的，每道工序可以在多个备选机器上加工，但加工时间随机器选择的不同而不同．FJSP的调度目标是通过确定各工序的机器选择以及各个机器上各工序的加工顺序和开始加工时间，在满足如下约束的条件下，使某些调度性能指标达到最优[10]．因此，FJSP问题可分解为两个调度子问题：一是确定各工件工序的机器选择，二是确定各个机器上工序的排序问题．

除了考虑工件的数量以及机器的加工时间外，一般满足如下的约束或假设：1)同工件的优先级相同，t=0时刻所有工件都可以被加工；2)所有机器在t=0时刻都可用；3)各工件必须满足既定加工顺序；4)同一时刻，一台机器上只能加工一个工件；5)同一时刻，一个工件只能被一个机器加工；6)忽略扰动因素，即工件一旦开始加工就不能中断．

1.2 数学模型建立

实际中，企业常以生产周期衡量生产效率的高低，因此，本文建立了以工件的最大完工时间最小为目标的柔性作业车间调度问题的数学模型，具体可描述如下：

(1)

(2)

(3)

(4)

其中，min(Cmax)为优化目标；n为工件总数；m为机器总数；M为所有机器的集合；i表示第i个工件；j表示工件i的第j个工序；h为工序j选择的机器编号；ni为第i个工件的工序总数；sijk为工件i在机器k上的开始加工时间；tklh为工件k的工序l在机器h上的加工时间；mij为工序j可选机器集合．

2 求解FJSP的元胞粒子群算法设计

2.1 编码与解码

1)基于粒子位置的双层编码

FJSP包含工件排序与机器选择两个子问题，编码时也需分开处理，因此本文采用如图1所示的双层编码的结构．

图1 双层编码示意图

采用双层编码，使得机器编码与工序的排序相互独立，便于粒子位置信息交叉的有效性和合法性，而且以矩阵的形式表示，减小计算的内存消耗．

2)解码

由于机器码的产生依赖于工序码，故只需对工序码进行解码，一般解码方式只能得到半主动调度，得不到主动调度．采用插入式贪婪解码方法，以确保得到的调度为主动调度．其操作步骤为：按粒子的位置编码信息，从左到右依次读取各工序，将其依次插入到对应机器上最早可以加工的时间上，直到所有的工序都被安排．

2.2 粒子位置信息更新方法

针对FJSP问题特点，改变中粒子的信息共享与继承机制，本文提出离散的元胞粒子群位置更新方式．当前粒子依据上一代、历史最优以及全局最优的位置信息，融入遗传算法的交叉思想实现粒子位置信息的更新，重新定义一种新的位置更新方法，如公式(5)所示：

(5)

图2 基于工序编码的IPOX交叉操作

Fibt=min(fitness(Pibt)，fitness(Pi1bt)，

(6)

2.3 混合元胞粒子群算法设计

2.3.1 FJSP邻域结构设计

柔性作业车间调度问题中最基本的邻域是通过在工序排序部分随机选择两个位置，采取逆序、插入、交换等操作构造，这些邻域结构在一定程度上丰富了解的邻域，但它们包含了大量的无效移动，导致算法后期搜索缓慢，运算效率低．因此本文在这些邻域的基础上加入更高效的基于关键块的邻域结构，有下几种：

1)N5邻域结构：N5邻域结构由Nowicki和Smutnicki[11]提出，其操作对象为关键路径中的关键块．对于首关键块，交换块尾两个工序；尾关键块，交换块首两个工序；中间关键块，块首两个工序与块尾两个工序都需要交换，如图3所示．

图3 N5邻域结构

2)块内工序与块首或块尾交换的邻域结构：N5邻域仅对块首前两个和块尾后两个进行交换操作，较为单一，将关键块内的工序分别与块首或块尾工序交换，极大地丰富关键块的邻域，如图4所示．

图4 与块首或块尾交换的邻域结构

3)N6邻域结构：N5邻域很小，搜索范围受到一定限制，为发掘更多有效移动，Balas和Vazacopoulos[12]提出了N6邻域结构．在不产生回路的前提下，将块内工序插入到块首前面或插入到块尾后面，如图5所示．

图5 N6邻域结构

2.3.2 元胞粒子群和变邻域混合策略

在元胞粒子群算法中，粒子通过追随自身历史最优位置学习邻居最优位置，不断地更新自身位置，使种群优质信息均匀传播，维持了种群的多样性，算法的全局搜索能力得以保障，这样的操作直接导致了收敛精度低，算法很难收敛．变邻域搜索(VNS)算法的局部搜索能力较强，但是VNS在变换邻域结构时具有一定的盲目性，很容易错过较优解所在的区域，求解质量很大程度上依赖于初始解和邻域结构．

基于以上分析，综合分析CPSO和VNS算法的特点，提出一种CPSO与VNS混合算法，称之混合的元胞粒子群算法(Hybrid CPSO, HCPSO)．

在CPSO系统中，多个粒子通过与共同邻居最优值Lbt同时进行信息交流，这种信息流动方式单一．在多个Lbt的作用下，粒子朝着最优解的方向进化，显然，Lbt对CPSO算法的性能有很大的影响．为提高CPSO算法的搜索性能，粒子群每次更新后对Lbt执行变邻域搜索，以增强算法对全局最优解的探索能力，因而混合元胞粒子群优化算法求解FJSP步骤如图6所示．

图6 HCPSO流程图

3 仿真实验与分析

3.1 仿真设计

本文选用文献[13]中的Brandimarte算例，验证设计算法的有效性．文中元胞粒子群算法的主要参数设置如下：种群大小N=50，粒子邻居结构为Moore型，粒子适应度值连续不变的最大步数MaxStep=20，最大迭代次数MaxCount=50，交叉概率c1=c2=0.45，变异概率Pm=0.01．变邻域搜索算法的主要参数设置如下：外循环步长outstep=20,内循环步长instep=100．

在Matlab 2012b版本软件中编程，针对不同算例，将HCPSO,CPSO和PSO 3种算法独立运行50次，得到的仿真结果见表1．

表1 标准算例计算结果

3.2 结果分析

如表1所示，m×n表示问题的工件总数和机器总数，LB,UB分别表示到目前为止已知的最优值下界和最优值上界，Cmax表示优化目标的最优值，Avg表示算法运行20次中所得平均最优值．分析求解的结果可知：对于FJSP问题，无论是最优解还是平均解，HCPSO的求解能力优于其他两种算法，这是因为在元胞粒子群优化算法中混入了VNS算法，由于VNS算法通过系统地改变邻域结构，提高了算法的局部搜索能力，避免算法过早陷入局部最优值．而CPSO因种群粒子邻域结构太单一，局部搜素能力较差，算法易陷入局部最优值，但整体上要比未采用任何改良机制的传统PSO要优．

进一步探讨HCPSO,CPSO和PSO 3种算法的收敛性，3种算法在求解Mk03问题最优值的迭代过程如图7所示．

图7 3种算法迭代过程图

可以看出，在前20代，3种算法收敛速度都较快，而传统的PSO比CPSO,HCPSO的收敛速度更快．当运行至20代至36代之间时，PSO开始趋于最终的收敛，CPSO和HPSO算法收敛速度变慢，但仍具有较好的局部搜索能力．由于融合了变邻域搜索，改变了解的结构，使得HCPSO比CPSO具有更强局部开挖能力，到37代以后，PSO因没有挖掘到更好的解而局部最优，HPSO算法和CPSO算法的收敛速度变慢，仍然保留一定的局部探索能力，最终由于HCPSO中融入变邻域搜索算法使得问题收敛到了全局最优值．

4 结 语

本文以生产实际为背景，建立柔性作业车间调度问题的优化模型，针对柔性作业车间调度问题包含了工件排序与机器选择两个子问题的特点，设计了高效的双层编码方式，提出适合求解该问题的元胞粒子群算法．通过改进粒子位置信息更新方法、粒子邻域结构选择策略以及各粒子更新策略，设计了元胞粒子群算法求解FJSP流程；探索了适合该问题的高效邻域结构，提出了求解FJSP问题的混合元胞粒子群算法．最后，采用标准的算例对改进的混合元胞粒子群算法做性能测试，比较了3种算法在多种类型问题上的求解性能．结果表明：所改进的混合元胞粒子群算法得到的解的质量较高，算法收敛性较好，可以广泛应用于其他优化问题的求解中．

[1] 赵学燕．钢结构企业生产调度优化研究[D]．天津:天津师范大学，2015．

[2] 李 俊，刘志雄，张 煜，等．柔性作业车间调度优化的改进模拟退火算法[J]．武汉科技大学学报，2015，38(2):111-116．

[3] 赵诗奎．求解柔性作业车间调度问题的两级邻域搜索混合算法[J]．机械工程学报，2015，51(14):175-184．

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

[5] 吴秀丽，张志强，杜彦华，等．改进细菌觅食算法求解柔性作业车间调度问题[J]．计算机集成制造系统，2015，21(5):1262-1270．

[6] 赵 敏，殷 欢，孙棣华，等．基于改进人工鱼群算法的柔性作业车间调度[J]．中国机械工程，2016(8):1059-1065．

[7] 李艳鹏．基于粒子群和禁忌搜索算法求解作业车间调度优化问题[D]．大连：大连交通大学，2013．

[8] Shi Y， Liu H, Gao L, et al． Cellular Particle Swarm Optimization[J]．Information Sciences, 2011,181(20):4460-4493．

[9] MladenovicN, Hansen P． Variable Neighborhood Search[J]．Computers & Operations Research, 1997,24(11):1097-1100．

[10] 吴正佳, 何海洋, 黄灿超, 等．带机器故障的柔性作业车间动态调度[J]．机械设计与研究, 2015，31(3):94-98．

[11] Nowicki E, Smutnicki C． A Fast Taboo Search Algorithm for the Job Shop Problem[J]．Management Science, 1996,42(6):797-813．

[12] Balas E, Vazacopoulos A． Guided Local Search with Shifting Bottleneck for Job Shop Scheduling[J]．Management Science, 1998,44(2):262-275．

[13] Brandimarte P． Routing and Scheduling in a Flexible Job Shop by Tabusearch[J]．Annals of Operations Research, 1993，41(3)：157-183．

[14] Pezzella F, Morganti G, Ciaschetti G． A Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]．Computers & Operations Research, 2008,35(10):3202-3212．

[15] Gao J, Sun L, Gen M． A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems[J]． Computers & Operations Research, 2008,35(9):2892-2907．

[16] 蔡保健．基于元胞粒子群算法的柔性作业车间调度问题研究[D]．宜昌:三峡大学, 2015．

[责任编辑 张 莉]

Improved Cellular Particle Swarm Optimization for Flexible Job Shop Scheduling Problem

Wu Zhengjia Fu Xianwang Wang Yun Liu Xiufeng

(College of Mechanical & Power Engineering, China Three Gorges Univ., Yichang 443002, China)

A mathematical model of flexible job-shop scheduling problem has developed based on the actual demand of the manufacturing enterprises. Aiming at its characteristics, a hybrid cellular particle swarm optimization (HCPSO) algorithm is proposed. A double-layer coding strategy is adopted to express the position information numerically for the order of the workpiece and machine.The crossover and mutation operation of genetic algorithm are introduced to improve the method of update with the particle position in the base of cellular particle swarm optimization. At last, the variable neighborhood algorithm is infused to enhance the ability of local exploration, The experiment results indicate that the solving ability of HCPSO has improved, so as to solve the flexible job shop scheduling problem effectively.

flexible job shop scheduling problem； double-layer coding； cellular particle swarm optimization algorithm

2016-09-18

湖北省自然科学基金(ZRY2014001091)

吴正佳(1964-)，男，教授，博士研究生，研究领域为生产管理、调度优化．E-mail：zjwu@ctgu.edu.cn

10.13393/j.cnki.issn.1672-948X.2017.03.019

TP18

A

1672-948X(2017)03-0084-05