应用萤火虫算法求解基于学习效应的PFSP 问题

2015-04-17叶春明凌远雄

计算机工程与应用 2015年16期

关键词：萤火虫亮度工件

杜贞，叶春明，凌远雄

DU Zhen,YE Chunming,LING Yuanxiong

上海理工大学管理学院，上海200093

Department of Management,University of Shanghai for Science and Technology,Shanghai 200093,China

1 引言

置换流水车间调度问题（Permutation Flow-shop Scheduling Problem，PFSP）是实际生产车间中一类重要的流水车间调度问题，尤其适用于单件大批量生产背景的制造型企业。该问题可以被描述为：n个工件在m台不同的机器上加工，每个工件有m道不同的工序，每道工序要在不同的机器上加工完成；n个工件通过m台机器的顺序相同，它们在每台机器上的加工顺序也相同；每台机器每次只能加工一个工件，每个工件每次只能由一台机器加工；已知每个工件在每台机器上的加工时间；求解的目标是确定最优加工顺序，使得按照该顺序加工工件时总完工时间最小。

对PFSP 的求解方法，可以分为三种类型：精确方法、启发式算法以及智能优化算法。研究表明，精确算法只适用于小规模问题的求解，启发式算法求解质量较差[1]，而当m>2 时，PFSP 问题已是NP 难题[2]，因此随着问题规模的增加，调度问题的解空间容量巨大，其求解过程更加复杂。由于精确方法和启发式算法的局限性，目前对该问题的求解方法趋向于使用更高效的智能优化算法，包括遗传算法、禁忌搜索算法、模拟退火法、蚁群优化算法以及粒子群算法等[3]。本文采用的萤火虫算法[4-5]是一种比较新颖的算法，在生产调度方面的研究刚刚起步，但也取得了一些成果：文献[6-8]分别应用该算法求解PFSP 和Job-shop 调度问题，通过对PFSP 中的典型Car 类测试问题和Job-shop 调度问题的FT、LA 两类测试问题进行仿真测试，并将结果与粒子群等算法的结果进行对比，验证了算法的可行性和有效性。

在经典的排序理论中，工件的加工时间都没有考虑与工件的加工位置的关系。然而，在一些实际排序问题中，由于工人或机器在长时间加工相同或类似的工件时，加工效率可能会逐渐提高，从而使后加工的工件的加工时间变小，这种现象被称为具有学习效应[9]。学习效应在生产中的影响最早是由Wright[10]提出的，之后国内外很多学者对其进行了研究，研究发现绝大多数行业存在学习效应，且由于环境、工艺、工序、生产设备等因素的差异，不同的行业学习率有所不同。相关学者对将学习效应应用到工件排序问题中进行了研究，其中孙林辉等[9]对工件具有学习效应的2 台机器流水作业排序问题进行了研究，给出了问题的数学规划模型，同时对大规模问题给出3 个启发式算法并验证了这3 个算法解决所研究问题具有有效性；张新功[11]对具有学习效应的最小化总完工时间的重新排序问题进行了研究，对于最大序列错位、总序列错位和最大时间错位下的最小化总完工时间问题给出了多项式时间算法，对于总时间错位下的最小化总完工时间问题提出了动态规划算法，并证明这个算法是拟多项式时间的。

本文结合生产实际情况，将学习效应模型加入到PFSP 中，建立基于学习效应的PFSP 模型，应用萤火虫算法进行模型的求解，并将不同学习率下对应的结果进行对比，找出差距，为制造企业提供理论依据。

2 数学模型的构建

2.1 学习效应模型

本文采用Biskup[12]提出的一种与工件的加工位置有关的学习效应模型：Pjr=Pj·ra，j，r=1,2,…,n，其中，a≤0 是学习效应因子，a=lgl/lg 2，l为学习率；Pj和Pjr分别为工件的基本加工时间和实际加工时间；r为工件的加工位置。

2.2 基于学习效应的PFSP 模型

假设有n个工件在m台机器上加工；工件的待加工序列为π(r1，r2，…，rn)，其中ri表示排序中第i个位置上待加工工件对应的工件编号；编号为ri的工件在机器j上的正常加工时间为P(ri，j)(i=1，2，…，n；j=1，2，…，m)，若每个机器有相同的学习率，则其实际加工时间为P(ri，j)·ia，其中a为学习效应因子；C(ri，j)是编号为ri的工件在机器j上的完工时间；目标函数是最小化最大完工时间（Makespan）。则基于学习效应的置换流水车间调度问题的模型为：

目标函数：

3 萤火虫算法

3.1 算法原理

自然界的萤火虫具有发光的特性。它们在晚上群聚时，通过散发荧光素来实现求偶、照明、警戒等信息交流活动。萤火虫算法就是模拟萤火虫的这一特性产生的。在萤火虫算法中，每只萤火虫被看做解空间的一个解，萤火虫种群作为初始解随机分布在目标函数的定义空间内。通过该算法中包含的亮度这一要素，将萤火虫在解空间中的位置与目标函数值对应起来：萤火虫越亮表示它所在的位置越好，即它所对应的目标函数值越优，从而能够吸引亮度低的萤火虫向自己所在的方向移动。萤火虫算法的另一要素——吸引度，与萤火虫自身的亮度成正比关系，亮度越大，吸引度越高，它决定萤火虫移动的距离。算法的优化过程为：亮度高的萤火虫吸引亮度低的萤火虫朝自己方向移动，萤火虫的亮度和吸引度就会不断变化，萤火虫的位置也相应地不断得到更新，最终使大部分萤火虫聚集在位置较优处，从而实现目标优化[8，13]。

3.2 数学描述

对萤火虫算法的优化机理从数学角度有以下定义[8，13]：

定义1萤火虫亮度的计算公式为：

其中I0为最大荧光亮度，即亮度较大的萤火虫j自身发出的亮度，与目标函数值呈正比；γ为光强吸收系数，由于距离的增加和传播媒介的吸收，荧光亮度会逐渐减弱，这里设置光强吸收系数来体现此特性，可以设为常数；rij表示萤火虫i与j之间的空间距离。

定义2萤火虫吸引度的计算公式为：

其中β0为最大吸引度，即亮度较大的萤火虫j所在位置的吸引度；γ、rij意义同上。

定义3萤火虫i被萤火虫j吸引向其所在方向移动的位置更新公式为：

其中，χi、χj分别为萤火虫i和j所处的空间位置；α为步长因子，在[0，1]范围内取值；rand为随机因子，在[0，1]上服从均匀分布。式中α·(rand－1/2)的作用是对萤火虫进行随机扰动，避免过早陷入局部最优。

3.3 算法设计

在搜索空间中，萤火虫的位置用n维向量χi=(xi，1，xi，2，…，xi，n)表示，n个分量均由随机方式产生。针对PFSP 问题，采用基于ROV 规则的随机键编码方式，既萤火虫位置向量的每一个分量代表一个工件，对向量中的分量进行升序排序，通过对每个分量的位置与下标进行映射将萤火虫的位置向量和机器上各工件的加工序列π(r1，r2，…，rn)联系起来。

在萤火虫位置更新过程中，考虑外界因素的影响，萤火虫的位置向量会发生一定的交叉和变异。为了增加算法的搜索精度，在算法设计过程中增加交叉和变异操作。

3.4 算法流程

步骤1进行基本参数初始化设置，依次设置萤火虫数目k、最大吸引度β0、光强吸收强度γ、步长因子α的取值，算法最大迭代次数maxGen，以及独立运行次数。

步骤2初始化萤火虫位置，计算每只萤火虫对应的目标函数值，并将其作为萤火虫各自的最大荧光亮度。

步骤3根据式（6）和式（7）分别计算萤火虫的亮度和吸引度，由荧光亮度决定萤火虫的移动方向，并更新萤火虫位置。

步骤4对更新后的萤火虫位置进行交叉和变异操作，并重新计算萤火虫的相对亮度，更新最优解。

步骤5当达到最大搜索次数时转步骤6，否则，将搜索次数增加1，转步骤3 进行下一轮搜索。

步骤6输出全局最优解，并将每次迭代后的最优解绘制成图。

算法流程图如图1 所示。

图1 萤火虫算法流程图

4 仿真测试

本文选取Car 类基准测试问题[14]来验证萤火虫算法的有效性，并对建立的含学习效应的PFSP 模型进行测试求解。

算法在处理器主频2.10 GHz，物理内存2 GB，Windows 7操作系统的PC机下进行，应用MATLAB R2012a编译软件编码。算法参数设置为：萤火虫数目k=40，最大吸引度β0=1，光强吸收强度γ=1，步长因子α=0.3，最大迭代次数maxGen=300，算法独立运行20 次。

4.1 对不含学习效应的PFSP 问题进行测试

应用萤火虫算法对测试问题进行仿真测试，并与粒子群算法（PSO）和遗传算法（GA）的测试结果进行对比。其中粒子群算法的粒子数为40，学习因子C1=C2=1.5，采用Wstart=0.9、Wend=0.4 的线性递减惯性权重，最大迭代次数也为300，独立运行20 次。遗传算法结果取自文献[15]。结果如表1 所示。

表1 car类问题优化结果

表1中，C*是理论最优解，SR表示寻优成功率，BRE表示最优相对误差，ARE表示平均相对误差。其中，BRE=(min(Cmax)-C*)/C*×100%,ARE=(avg(Cmax)-C*)/C*×100%。从测试数据可以看出，萤火虫算法不论在寻优成功率还是在相对误差方面性能都明显优于粒子群算法和遗传算法，验证了萤火虫算法求解PFSP问题的可行性和有效性。

根据学习因子的计算公式a=lgl/lg 2 可知，不含有学习效应的PFSP问题既是学习率为100%的PFSP问题。

4.2 对含有学习效应的PFSP 问题进行求解

行业不同，流水车间存在的学习率也不同，因此对学习效应在PFSP问题中的应用要考虑不同的学习率。当学习率l分别是90%、80%、70%、60%、50%时学习效应因子a分别是-0.152、-0.322、-0.515、-0.737、-1。在独立运行萤火虫算法20 次后得到的优化结果如表2 所示。

表2 含学习效应的Car类问题优化结果

图2 优化结果的线性拟合情况

4.3 结果分析

（1）拟合分析

对Car 类问题在不同学习率下的优化结果进行线性拟合（图2），从图2 中可以看出，随着学习率的降低，各测试问题目标函数值的减小趋势均十分明显。因此在PFSP 问题中加入学习效应后，工件的最小化最大完工时间缩短，并随着学习效果的增强，最小化最大完工时间呈明显的减小趋势。

（2）敏感性分析

敏感性分析是一种定量描述模型输入变量对输出变量的重要性程度的方法。敏感度系数是敏感性分析的评价指标，它是目标值变化的百分率与敏感因素变化的百分率之比，计算公式为：

式中，SAF为评价指标A对于不确定因素F的敏感度系数；ΔF/F为不确定因素F 的变化率；ΔA/A为不确定因素F发生ΔF变化时，评价指标A的相对变化率。SAF＞0 表示评价指标与不确定因素同方向变化；SAF＜0表示评价指标与不确定因素反方向变化。|SAF|越大表明评价指标A对于不确定性因素F越敏感；反之则不敏感[16]。

本文采用敏感性分析来定量地研究学习效应对目标函数值的影响程度。根据公式（9）计算学习率的敏感度系数，汇总于表3 中。由表3 可以看出，除了在敏感因素变化率为-50% 时，Car7 对应的敏感度系数0.94 小于1 外，其余所有Car 问题在不同学习率下的敏感性系数均大于1，其中部分敏感度系数大于2，这说明：学习率与目标函数值同方向变化，学习率越低，学习效果越明显；学习率每变化1%，目标函数值将变化1%以上，从而得出结论——学习率属较敏感的因素。

综上可知，学习效应对PFSP的目标函数值有很大影响，企业在实际生产中考虑学习效应的存在是十分必要的。

表3 学习率敏感度系数表

5 结束语

本文通过测试和分析，在验证了萤火虫算法求解PFSP 问题具有可行性和有效性的基础上，得出结论：学习率是影响工件加工完成时间的一个较敏感因素；由于学习效应的存在，批量生产的工件的最小化最大完工时间会比理论值小，且学习效果越好，实际值与理论值差距越明显。因此企业在安排生产计划时考虑学习效应这一影响总完工时间的因素，可以使预测的结果更接近实际情况，制定出更加合理准确的生产计划，从而促进生产力的提升。本文只针对学习效应在PFSP 中的应用问题进行了研究，鉴于生产调度的多样性，基于学习效应的生产调度问题还有待作进一步研究。

[1] 刘延风，刘三阳.基于混合电磁算法求解置换流水车间调度问题[J].系统仿真学报，2012，24（3）：603-607.

[2] Garey M R，Johnson D S，Sethi R.The complexity of flow-shop and job-shop scheduling[J].Mathematics of Operations Research，1976，1（2）：117-129.

[3] 张其亮，陈永生，韩斌.改进的粒子群算法求解置换流水车间调度问题[J].计算机应用，2012，32（4）：1022-1024.

[4] Yang X S.Nature-inspired metaheuristic algothms[M].UK，Beckington：Luniver Press，2008：83-96.

[5] Yang X S.Firefly algorithms for multimodal optimization[J].Lecture Notes in Computer Sciences，2009，5792：169-178.

[6] 刘长平，叶春明.置换流水车间调度问题的萤火虫算法求解[J].工业工程与管理，2012，17（3）：56-59.

[7] 杨娇，叶春明.应用新型萤火虫算法求解Job-shop 调度问题[J/OL].计算机工程与应用，http：//www.cnki.net/kcms/detail/11.2127.TP.20120907.1626.017.html.

[8] 周季华，叶春明.应用萤火虫算法求解置换流水线问题[J].计算机应用研究，2013，30（1）：152-154.

[9] 孙林辉，王丹，王吉波.具有学习效应的总完工时间流水作业问题[J].系统管理学报，2011，20（1）：114-118.

[10] Wright T P.Factors affecting the cost of airplanes[J].Journal of Aeronautical Sciences，1936（3）：122-128.

[11] 张新功.具有学习效应的重新排序问题[J].重庆师范大学学报，2012，29（1）：1-6.

[12] Biskup D.Single-machine scheduling with learning considerations[J].European Journal of Operational Research，1999，115（1）：173-178.