粒子群算法求解具有机器灵活性的FFSP

大家好，欢迎来到IT知识分享网。

摘 要： 对柔性流水车间调度问题（FFSP）进行了分析阐述，在此基础上对某饲料厂的饲料生产过程建立了具有机器灵活性的柔性流水车间调度模型，该模型中存在多台制粒机，既能加工大颗粒饲料，又能加工小颗粒饲料，但是必须在开始加工之前确定各台机器的用途，增加了柔性流水车间调度的难度。利用新型的粒子群算法以最小化最大完工时间为目标对该模型求解，为了克服粒子群算法易陷入局部极值的缺点，提出基于位置相似度的邻域结构，并对邻域内的较优粒子采用基于最大完工时间排序的学习方式进行局部搜索。实验结果表明，该方法有利于克服粒子群算法的早熟缺陷，有效地解决了饲料生产调度问题，有一定的应用价值。

0 引言

柔性流水车间调度问题（Flexible Flowshop Scheduling Problem，FFSP）是一种更加复杂也更贴近实际的流水线调度问题，属于典型的NP难问题。由于该问题具有重要的学术价值和应用价值，在将近半个世纪的研究中已取得较大的进展。早期对柔性流水车间调度问题的求解主要是利用精确算法[1]和启发式方法[2]。精确算法在理论上可以得到调度问题的最优解，但是在求解时间上无法让人接受，一般只用来解决小规模问题。而启发式方法能够在较短时间内给出解决方案，但是解的质量无法保证。近年来智能算法[3-6]得到广泛青睐，如模拟退火算法、禁忌搜索算法、免疫算法、遗传算法、蚁群算法、蜂群算法、粒子群算法等。

本文对某饲料厂的饲料生产过程进行调研以后，发现目前的饲料行业普遍还采用人工调度，调度计划的优劣完全取决于调度人员的经验。而饲料生产过程可抽象为柔性流水线，于是本文建立了一种带机器灵活性的柔性流水车间调度模型，利用智能算法——粒子群优化（Partical Swarm Optimization，PSO）算法对其进行求解。设计了一种有效的编码及解码方式，因为粒子群算法存在其固有的早熟缺陷，在柔性流水车间调度问题上的应用效果还有待提高，因此本文提出基于位置相似度的邻域结构，并对邻域较优粒子采用基于最大完成时间排序的学习方式进行邻域搜索，改善解的质量，实验结果表明本文提出的方法是有效的，有一定的应用前景。

1 具有机器灵活性的柔性流水车间调度问题描述

具有机器灵活性是指：以柔性流水车间调度问题[2]为基础，在某道或多道加工工序中存在多用途的机器，但是该机器具体用于哪种用途需要在加工开始前确定，一旦加工开始，其用途就不可再改变。下面以某饲料厂生产过程为例介绍。

对某饲料厂一个生产车间的生产状况进行调研以后，将饲料生产的两个主要流程抽取出来建立一个调度模型。饲料在类型上主要分为颗粒饲料和膨化饲料，其中颗粒饲料分为大颗粒饲料和小颗粒饲料。所有的饲料在生产过程中首先要经过配料过程，该生产车间共有配料线5条。配料完成后颗粒饲料需要经过制粒机制成颗粒，而膨化饲料则需要用膨化机进行膨化。该车间共有制粒机5台，膨化机3台，其中有1台制粒机只用于制大颗粒，1台制粒机只用于制小颗粒，其余3台制粒机既可以制大颗粒也可以制小颗粒。但是为了保证产品质量，生产过大颗粒的制粒机不能改制小颗粒，同样生产过小颗粒以后也不能再用于生产大颗粒。

该车间的调度任务主要有三点：

（1）决定3台可以制大颗粒饲料也能制小颗粒饲料的制粒机具体用于哪种用途；

（2）制粒机的用途确定以后即要确定所有产品的加工顺序；

（3）决定每种产品在每道工序具体使用哪台机器。

该问题为具有机器灵活性的调度问题，相比基本的柔性流水车间调度来说多了一个选择机器用途的步骤，所以难度上有所增加。

2 粒子群算法介绍

粒子群优化算法自诞生以来，在无约束连续优化领域体现了其巨大的优化潜能，该算法结构简单，易于实现，算法收敛速度快，鲁棒性好。

因为粒子群算法的提出是为了解决连续优化问题，因此并不能直接用于组合优化问题的求解。对此，本文采用离散粒子群优化算法，根据粒子群算法的优化机理，离散粒子群算法中粒子采用整数编码，并利用下式来更新粒子：

其中vi（k）和xi（k）表示粒子在第k次迭代时的速度向量和位置向量；pbest和gbest分别是粒子的历史最优位置和种群的历史最优位置；

表示交叉操作，具体的交叉方式采用参考文献[5]中的方法，对交叉的两个个体pop1和pop2随机选择交叉区域，将pop2中的交叉区域加到pop1中对应的位置，删除pop1中已在pop2的交叉区域出现过的工件，并进行相应的映射替换。

3 问题求解

3.1 粒子的编码及解码

利用粒子群算法对调度问题求解首先要考虑的是粒子的编码及解码方式，本文采用基于工序的编码方式，即用整数序列来表示产品的加工顺序，如一个加工任务需要加工5个产品，则随机产生一个粒子：[2 3 1 4 5]，该编码表示先加工2号产品，再加工3号产品、1号产品、4号产品，最后是5号产品。

粒子的编码方式确定以后，就需要有解码方式，本文采用最先空闲机器规则，参考文献[7]中有定义：在确定的加工优先级的约束下，机器无闲置工件分配规则是一种最优分配模式。因此得到工件加工顺序（从第二个阶段开始工件的加工顺序由前一加工阶段的完成顺序决定）后，需要对工件在各道工序上的加工顺序和加工机器作出选择，最先空闲机器规则具体描述见参考文献[4]。

为了解决机器灵活性问题，本文在原有解码规则的基础上进行改进：在调度前，将多用途的机器放入一个集合中，例如common={2，3，4}，表示2、3、4号机器属于多用途机器，在最先空闲机器规则的第二步中，如果产品可用common集合中的机器加工，则分别计算产品在集合中各机器上加工的理论时间，若结果显示要选择common集合中的机器来加工，则将该机器从common集合中移除，并固定用于加工该类产品，依照此思想，当common集合为空时，所有机器的用途就确定了，接下来的产品生产安排可以按照最先空闲机器规则来分配加工机器。

3.2 局部搜索策略

单纯的粒子群算法容易陷入局部极值，为使算法能有效地摆脱局部极值的束缚，进行有效的局部搜索是很有必要的。定义粒子相似度：对两个D维的粒子，其相似度为D′/D，其中D′表示两个粒子有D′维相同。例如对粒子P1：[3 1 5 4 2]和粒子P2：[3 1 4 2 5]，其相似度为2/5。

有了粒子相似度的概念，规定粒子的邻域范围为与该粒子相似度高于某一阈值的所有粒子，在此本文采用一种基于最大完成时间排序的学习方式（Makespan Rank Based Learning，MRBL）进行局部搜索，局部搜索的时机为种群每更新一次之后，对每个粒子都进行一次局部搜索，具体的搜索方法如下：

（1）计算当前粒子与种群其他粒子的相似度，找出依据相似度阈值确定的邻域中适应值最优的粒子。

（2）计算邻域最优粒子对应的调度结果，找出完工时间较大的y个待加工的产品，例如完工时间如表1所示，若取y=2，则将产品2和产品7从加工序列中移除，然后依次将产品2和产品7试探性地插入到剩余加工序列的所有可能位置，最后将产品2和产品7放到能最小化最大完工时间的位置，得到一个新的加工序列。

（3）将新得到的序列的适应值与原粒子的适应值比较，若优于原粒子，则用新位置更新原粒子位置，否则原粒子不变。

（4）若所有粒子都已进行局部搜索，则局部搜索结束，否则继续对下一粒子进行局部搜索。

步骤（2）中的y值实际上表示了局部搜索的深度，当y值过大时，局部搜索的时间将会过长，甚至让人无法接受，而y值过小，会导致局部搜索深度不够，找到局部更优的几率减小，因此y的取值在一定程度上会影响算法效率。参考文献[8]中采用实验的方法确定在粒子为50维时y取6能得到较好的效果，然而现实问题的维数是不确定的，对每种情况都采用实验的方法去寻找恰当的y值显然很不实际，参考文献[9]中提到，考虑到欧式空间多点极限布局，哈密尔顿回路排列外形近似正方形，因此为平衡局部搜索深度和搜索效率，本文对y值进行随机选取，其范围为2~D/4之间，D为问题的维数。

3.3 算法流程

利用本文算法求解带机器灵活性的柔性流水车间调度问题的步骤如下：

（1）初始化：设定粒子群的种群大小和最大迭代次数，随机产生粒子的初始位置、初始速度和多用途机器集合common，以及粒子相似度阈值；

（2）求出每个粒子的适应值，并初始化所有粒子的个体极值和全局极值；

（3）根据式（1）和式（2）更新粒子位置和粒子速度；

（4）求出每个粒子的适应值并更新所有粒子的个体极值和全局极值；

（5）对每个粒子找出其邻域最优粒子，执行一次局部搜索，并更新粒子个体极值及全局极值。如果达到最大迭代次数，则转步骤（6），否则转步骤（3）；

（6）结束算法寻优过程，输出最好解。

3.4 实例求解与分析

现假设要同时生产10种饲料，其中3种为大颗粒饲料，2种为小颗粒饲料，其余5种为膨化饲料，各饲料在各工序（机台）上的加工时间如表2所示。

其中饲料1~饲料3为大颗粒饲料，饲料4~饲料5为小颗粒饲料，饲料6~饲料10为膨化饲料，加工时间为“-”表示该机台不可用。

为了验证算法的性能，分别利用带局部搜索的粒子群算法和不带局部搜索的粒子群算法对问题求解，种群大小均为40，迭代次数均为100次，局部搜索中的相似度阈值取0.85，两种算法的迭代曲线图如图1所示。

从输出的调度结果得到，common集合为空，且2台通用制粒机用于制大颗粒饲料，1台通用制粒机用于制小颗粒饲料，最终的完工时间为144个时间单位。图1的迭代曲线显示，带局部搜索的粒子群算法在大约第4次迭代以后就找到了最优值，而不带局部搜索的粒子群算法在大约13次迭代以后才达到最优值，说明本文的算法收敛速度快，寻优精度高。本例中本文算法和不带局部搜索的粒子群算法在最后的求解精度上没有区别，原因是本例规模较小，复杂度较低，最优值很容易找到。但是相对于饲料行业如今普遍使用的手工调度而言，本文提出的调度方法无论在求解速度上还是求解精度上都有十分出色的表现。

4 结论

本文针对某饲料厂生产过程的特点建立了带机器灵活性的柔性流水车间调度模型，模型中存在加工机器灵活性也可称为不确定性，在传统的柔性流水车间调度基础上要考虑某些机器的具体用途，机器用途的选择不同，调度模型也不同，因此相比基本的柔性流水车间调度问题更有难度。本文利用有效的编码及解码方式，通过带局部搜索的粒子群算法对模型进行了有效求解，求解结果较好，对饲料生产调度有一定指导意义。然而本文所做的研究有限，今后还可从编码及解码方式以及算法上做更多研究。

参考文献

[1] 王圣尧，王凌，许烨，等.求解混合流水车间调度问题的分布估计算法[J].自动化学报，2012，38（3）：437-443.

[2] 黎展滔.具有成组约束的柔性流水车间作业计划制定的启发式算法[D].广州：广东工业大学，2012.

[3] 周辉仁，唐万生，魏颖辉.柔性Flow-shop调度的遗传算法优化[J].计算机工程与应用，2009，45（30）：224-226.

[4] 王凌，周刚，许烨，等.求解不相关并行机混合流水线调度问题的人工蜂群算法[J].控制理论与应用，2012，29（12）：1551-1557.

[5] 张其亮，陈永生.基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论与实践，2014，34（3）：802-809.

[6] 张其亮，陈永生.解决具有混合约束柔性流水车间调度问题的粒子群优化算法[J].计算机应用研究，2013，30（11）：3253-3256.

[7] 唐立新，吴亚萍.混合流水车间调度的遗传下降算法[J].自动化学报，2002，28（4）：637-641.

[8] 王大志，刘士新，郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J].自动化学报，2014，40（3）：548-555.

[9] 熊伟，张江维，张火林.求解TSP问题的增强型自探索粒子群算法[J].华北电力大学学报，2009，36（6）：69-85.