分类筛选
分类筛选:

粒子群算法硕士论文范文 与基于改进粒子群算法的设备维修调度优化有关论文如何怎么撰写

版权:原创标记原创 主题:粒子群算法范文 类别:本科论文 2024-02-05

《基于改进粒子群算法的设备维修调度优化》

本文是粒子群算法类大学毕业论文范文与设备维修和粒子群算法和调度类硕士论文范文。

锋,董宝力

(浙江理工大学机械与自动控制学院,杭州 310018)

摘 要: 为保障离散制造企业生产系统的连续性并降低其维修成本,构建了以维修时间最短和维修成本最低为目标的设备维修调度优化模型,并采用改进粒子群算法对模型进行求解.针对标准粒子群算法后期易陷入局部最优的缺点,采用指数函数递减的惯性权重形式来平衡算法的全局搜寻能力和局部搜寻能力,在速度更新公式和位置更新公式中分别引入速度扰动项和飞行时间因子以提高算法的收敛能力.以某机械公司生产车间设备维修调度为例,验证了该方法的有效性和适应性.

关键词: 设备维修;调度;多目标;改进粒子群算法

中图分类号: TP311

文献标志码: A

文章编号: 1673\|3851 (2017) 06\|0859\|07

0引言

设备维修过程中,由于时间、人员、故障诊断工具等限制,存在维修资源短缺、维修资源分配不均等问题,难以确保在较短时间内完成维修任务,影响生产系统及时恢复正常运行状态.合理安排设备维修调度可以实现维修资源的最优化利用,及时修复失效的设备,同时降低维修成本.目前,制造企业通常根据设备维修主管的经验或先来先服务(first in first out,FIFO)的规则进行维修任务的调度,缺乏科学的计划,导致较长的维修等待时间和较高的维修保障成本.因此,探索科学合理的维修调度策略对制造企业提升设备维修管理水平具有重要意义.

目前,国内外学者对设备维修调度问题的研究已取得一定的成果.Yare等[1]以提高电网系统可靠性为目标,对维修资源、系统负荷等进行综合分析,建立了发电机维修调度模型,并运用变异动态粒子群优化(mutational dynamic particle swarm optimization,MDPSO)算法对模型求解.Aissani等[2]提出了一种用于石油工业生产系统的动态维修任务调度的多智能体系统(multiagent system,MAS)方法.厉红等[3]研究了半导体生产领域的设备维修调度问题,在维修人员不足的前提下,提出了以停机损失最小为目标的维修人员两步分派法.王正元等[4]把战时维修管理工作中的动态调度问题分解成静态子问题和动态子问题,以作战单元为研究单位,以修复时间最短为目标,分别构建相应的模型.杨琴等[5]对汽车维修车间调度问题的特征进行了分析,采用基于工作的分解法将问题分解成多个子问题,并应用启发式算法对子问题进行求解.杨少华等[6]采用柔性制造系统(flexible manufacture system,FMS)调度问题的形式化描述,构建了基于工艺约束的军用飞机维修作业调度模型.吕学志等[7]对维修人员的休息时间进行系统性分析,以维修任务完成时间最短为目标,构建了军用装备维修调度模型.

设备维修成本一般包括设备停机损失成本、人员维修工时成本和备件成本等.上述研究大都聚焦于停机损失成本,对其他维修成本缺乏整体考虑.还有一些研究仅从时间的角度优化维修调度目标,没有考虑维修成本目标.维修时间与维修成本是非线性的关系[8].在实际设备维修过程中,过分追求短的维修时间,虽然可以减少停机损失成本,但是可能需要安排维修专家或增加普通维修人员的投入,进而增加人工成本,同时可能增加备件贮存等管理成本.本文以离散制造企业的生产设备为研究对象,在同时考虑设备停机损失成本和人员维修工时成本的基础上,构建了以维修时间最短和维修成本最低为目标的设备维修调度优化模型,并设计了改进粒子群算法对模型进行求解.

1问题描述及模型建立

离散制造企业的生产设备是根据生产工艺布置的,其种类繁多,大小不一,结构繁简程度不同,精度高低不同,功能多样,可以实现相同功能的设备通常有多台,且具有相同功能的设备往往涉及多个OEM厂商,因此对设备维修人员的技能水平和维修资源调度的合理性要求都较高.

对本文研究的离散制造企业的生产设备维修调度问题,做以下的基本假设:

a) 有L种类型的生产设备,每一种类型有若干台,编号i等于1,2,…,I,不同类型的设备重要度不同,且单位时间的停机损失成本不同.这些设备可能发生的故障类型有M种,编号为m等于1,2,…,M.

b) 有数量为N的设备维修工,编号j等于1,2,…,J.由于维修工技能水平、设备类型和故障类型的差异,每一名维修工对同一台故障设备进行修复作业所需的时间不同,同一名维修工对不同台故障设备进行修复作业所需的时间也不同.

c) 一个维修任务对应一台故障设备,并且由一名维修工执行.

d) 一台设备同一时间只发生一种故障类型.

e) 同一时间有多台设备发生故障,按照设备重要度等级安排维修顺序.

f) 任意一个维修任务分配后,维修期间不再更换维修工,直到该维修任务完成.

g) 维修准备时间与维修顺序无关,并计入维修时间.

h) 相邻维修任务之间的走动时间忽略不计.

调度流程为:生产人员提交维修任务,维修中心接收维修任务后,维修主管对维修人员进行任务分配,维修人员完成一项任务后接受新任务的分配,若没有被安排新任务则从生产车间返回维修中心.设备维修调度流程如图1所示.

图1设备维修调度的流程

调度目标是为每台故障设备选择最合适的维修人员,确定每台故障设备的维修顺序,使维修时间最短,同时考虑维修人员工时成本和停机损失成本,使维修成本最低.建立设备维修调度多目标优化模型如下:

minf等于(f1,f2)(1)

f1等于∑Ww(cwi-rwi)i等于1,2,…,I(2)

f2等于∑Jj等于1∑kjsumk等于1∑WwXwikj·pij·qj+

∑Ww(cwi-rwi)tii等于1,2,…,I(3)

s.t.

cwi等于Xwikj·pij+swi,当Xwikj等于1w,i,j,k(4)

swi≥rwiw,i(5)

sw′i′<swi,当rw′i′等于rwi且hi′>hiw,w′,i,i′(6)

∑Jj等于1∑kjsumk等于1Xwikj等于1w,i(7)

Xwikj∈0,1(8)

式中:wi表示修复故障设备i的维修任务;rwi表示维修任务wi的提交时间;swi表示执行维修任务wi的开始时间;cwi表示维修任务wi的完成时间;kjsum表示维修工j一个维修调度时间段内执行的作业任务数量;pij表示维修工j维修设备i所需要的时间;qj表示维修工j的单位时间薪酬;ti表示设备i发生故障时的单位时间损失成本;hi表示设备i的重要度等级.

目标函数(1)表示设备维修调度总目标是实现维修时间和维修成本综合最优;式(2)表示所有维修任务从提交到完成的总时间;式(3)表示总维修成本等于所有参与维修作业的维修工修复全部故障设备的工时成本与全部故障设备的停机损失成本之和;式(4)表示维修任务w的完成时间等于维修工j执行维修任务w的起始时间与这名维修工完成维修任务w所需要的时间之和;式(5)表示限制执行维修任务w的起始时间,显然不能早于维修任务w的提交时间;式(6)表示同一时间有多台设备发生故障时,优先对重要度等级高的设备进行维修;式(7)表示维修任务w只由维修工j执行一次;式(8)表示控制变量的取值范围为{0,1},当维修任务w被分配给维修工j第k个执行时,Xwikj取为1,否则为0.

2基于改进粒子群算法的模型求解

粒子群算法(particle swarm optimization,PSO)是求解设备维修调度问题的有效方法,相对于其他算法具有结构简单、参数较少、搜索速度快、易于工程实现等优点[9].因此,本文提出一种基于粒子群算法的方法来求解上述模型.

2.1粒子群算法的改进

标准粒子群算法存在迭代后期搜索速度不足,容易陷入局部最优等缺点[10],为了避免在实际使用过程中出现早熟现象,本文从惯性权重、速度更新策略和位置更新策略三方面对标准粒子群算法进行改进来提高算法的分布性与收敛性,具体的改进策略如下.

2.1.1惯性权重的调整策略

惯性权重w的值影响粒子群算法的全局搜寻能力和局部搜寻能力,当w值较大时,粒子的迭代步长较大,能够扩大种群的搜寻区域,而当w值较小时,粒子的迭代步长较小,能够提升种群的局部搜寻能力[11].文献[12]表明,当w在[0.4,0.9]区间线性递减时,算法能够快速收敛.但是线性变化的惯性权重在算法迭代过程化速率保持不变,无法实现粒子前期快速寻优、后期精确寻优的目的.而非线性变化的惯性权重在算法初期,w值递减速率较大,w从一个较大值骤减为一个较小值,使粒子能够在较大范围内快速寻找到优质解的大概位置;在算法后期,w值递减速率下降,粒子能够在较优区域保持低速搜索状态,相对于线性变化的惯性权重能够更加有效地提高算法局部挖掘能力.因此,本文采用非线性变化的惯性权重调整策略,根据指数函数的特点,设计了指数函数递减的惯性权重计算方法,如式(9)所示.线性递减的惯性权重策略与指数函数递减的惯性权重策略对比图像如图2所示.

w(t)等于2-ttmax-0.1(9)

式中:t表示算法当前的迭代次数,tmax表示算法最大的迭代次数.

图2指数函数递减的惯性权重与线性递减的

惯性权重趋势变化的对比

2.1.2速度更新公式的改进策略

针对粒子群算法在迭代后期搜索速度不足,容易陷入局部最优的缺陷[10],通过添加速度扰动项对速度更新公式进行改进.改进后的速度更新公式如下:

vi(t+1)等于w·vi(t)+c1·r1·(pi-xi)+

c2·r2·(gb-xi)+a·ttmax-r3·b(10)

式中:a和b均是(0,1)的常数,根据实验情况设定;r3是(0,1)的随机数.

在速度更新公式中添加速度扰动项后,在算法前期,粒子具有较大的速度,速度扰动项的数值远小于公式的前三项,对粒子探索能力的影响微乎其微;随着迭代次数的增加,粒子的速度越来越小,逐渐趋向于零,速度扰动项使粒子在算法后期依然保有一个较小的速度进行持续探索,避免算法过早收敛.

为了验证改进速度更新公式的有效性,选取Ackley函数进行仿真检验,追踪改进前后粒子的速度变化,为了方便观察,将种群规模设置为1.在相同的迭代条件下,改进前后粒子的速度变化如图3、图4所示.从以下两图中可以看到,改进前粒子的飞行在40代时开始趋向于停滞状态,到50代时粒子的速度衰弱至零,粒子停止搜索;而改进后由于速度扰动项的作用,在40代时粒子依然保有一个有效的速度进行细致的局部搜寻,直到70代粒子的速度才衰弱至零,搜寻的精度更高,具有更好的局部搜寻性能.

图3改进前粒子速度变化的趋势

图4改进后粒子速度变化的趋势

2.1.3位置更新公式的改进策略

考虑到粒子运动时间随着迭代的进行而不断变化,为了保持粒子种群的多样性,通过引入飞行时间因子对位置更新公式进行改进.改进后的位置更新公式如下:

xi(t+1)等于xi(t)+K·1-ttmax·vi(t+1)(11)

式中:K是初始飞行时间因子.

2.2粒子的编码

编码方式采用顺序编码,即维修任务的序列编号作为粒子的编码规划,维修任务的数量决定编码长度,粒子位置的每维取整数,分别表示执行对应维修任务的维修工,如某一维值为1表示执行该维修任务的是1号维修工,每一个维度的取值范围为可以执行对应维修任务的维修工,如可以执行维修任务1的人员有1号、2号和3号维修工,则该维的取值范围为{1,2,3}.粒子运动后,对粒子位置的每维修正取整,根据取整后得到的值确定执行对应维修任务的维修工.假设维修任务数量为12,维修工数量是5,且每名维修工可以执行所有的维修任务,粒子(2 3 1 4 4 3 2 5 1 2 5 4)为一个可行的维修调度方案.

2.3适应度函数

本文考虑了维修时间最短和维修成本最低两个目标,采用线性加权法将多目标转变为单目标,运用改进粒子群算法求解设备维修调度问题,设计适应度函数F表达式如下所示:

F等于α·f1+β·f2u(12)

式中:α、β分别表示各个目标的权重,u是适应度函数调整参数.

2.4改进粒子群算法流程

运用改进粒子群算法求解本文研究的设备维修调度问题,主要分为以下五个步骤,基本流程如图5所示.

1) 种群初始化:设置种群规模H、最大迭代次数T、学习因子c1和c2,根据维修任务数量和维修人员技能确定种群的维数和每维的取值范围,并随机产生粒子的初始速度和位置.

2) 求解适应度值:根据式(12)求解每个粒子的适应度值,将结果作为各自的个体极值fgbest(i),并比较所有粒子的个体极值,将它们中的最小值作为全局极值fzbest.

3) 惯性权重、速度和位置更新:分别根据式(9)、式(10)和式(11)更新惯性权重、粒子的速度和位置,对更新后的速度和位置分别根据式(13)、式(14)进行调整.

vi(t)等于Vmin,当vi(t)<Vmin

vi(t),当Vmin<vi(t)<Vmax,

Vmax,当vi(t)>Vmaxi等于1,2,…,H;t等于1,2,…,T(13)

xi(t)等于Xmin,当xi(t)<Xmin

xi(t),当Xmin<xi(t)<Xmax,

Xmax,当xi(t)>Xmaxi等于1,2,…,H;t等于1,2,…,T(14)

式(13)中:vi(t)表示迭代次数为t时粒子i的速度,Vmin、Vmax分别表示粒子的速度下限、速度上限,目的是控制粒子搜寻的精确程度,避免粒子速度过小导致算法陷入局部最优,同时避免粒子速度过大导致位移过大,飞出群体区域;式(14)中,xi(t)表示迭代次数为t时粒子i的位置,Xmin、Xmax分别表示粒子位置的最小界限、最大界限,目的是确保粒子在可行解域内进行搜寻,保证搜寻的有效性.

4) 个体极值、全局极值更新:根据式(12)计算每个粒子的适应度值,将结果依次与各自的个体极值fgbest(i)、全局极值fzbest进行比较,根据比较结果,更新个体极值fgbest(i)、全局极值fzbest.

5)如果达到最大迭代次数T,则输出最优粒子的位置zbest,算法结束,将zbest解码得到最佳的设备维修调度方案,否则,转向步骤3).

图5改进粒子群算法的流程

3实例验证

3.1设备维修调度实例描述

以某机械公司生产车间某一时间段的维修记录数据进行仿真实验.实验中有电脉冲机床、数控镗铣床、粗加工车轴机床、精加工车轴机床、成型磨床、数控外圆磨床6种(M1—M6)共12台设备发生6种类型故障(C1—C6).负责该车间的维修工共有5名(P1—P5),每名维修工的工时成本为25元/h.每台故障设备的故障类型和维修任务的提交时间如表1所示,故障类型及各维修人员进行相应维修所需的时间如表2所示,每种设备的单位时间停机损失成本如表3所示,各类型设备的重要度等级如表4所示,重要度从A至F依次降低.

表1故障设备的故障类型和维修任务的提交时间

维修任务序号设备类型故障类型任务提交时间

1M2C28:00

2M3C38:05

3M1C18:08

4M48:13

5M48:14

6M6C68:25

7M5C58:34

8M6C68:34

9M5C58:38

10M6C68:45

11M1C18:53

12M3C38:57

表2各类型故障由相应的维修人员维修所需的时间min

故障类型维修人员P1P2P4P5

C12436303648

C24836364242

C3168192138180192

9012010860132

C512090120150150

C6180210192228210

表3各类型设备单位时间的停机损失成本元/h

设备类型M1M2M3M4M5M6

单位时间损失费用960900720780720660

表4各类型设备的重要度等级

设备类型M1M2M3M4M5M6

重要度等级CABDEF

3.2仿真结果及分析

为了使两个目标尽可能达到同时最优,参考维修记录数据,对权重的选取进行不同取值的模拟,模拟结果如表5所示.由表5可知,当α取0.5,β取0.5时,权重能够对两个目标的寻优起到较好的协调作用.采用Matlab R2014a软件分别对标准PSO算法和改进PSO算法进行仿真实验,参数设置为:种群规模H等于50,最大迭代次数T等于200,学习因子c1等于c2等于2,仿真结果如图6所示.图6表示标准PSO求解方法和改进PSO求解方法随着迭代次数的增加适应度值的收敛情况,从图中可以看到,标准PSO求解方法很快陷入了局部最优,粒子搜索停滞,进入收敛状态,在36代收敛至最优解,出现了早熟现象,而改进PSO求解方法在迭代前期能够更快速地寻优,并且进入局部搜索后由于速度扰动项的作用保持持续搜索状态,直到59代收敛至最优解,具有较好的局部挖掘能力,相对于标准PSO求解方法收敛效果更好.图7表示以维修任务1的开始维修时间作为时间起点改进PSO算法求解结果的甘特图,图中包含数字的矩形表示维修任务,数字表示维修任务的序号.

表5两个目标的权重分配的模拟

αβu·α·f1β·f2/%

0.30.741

0.40.664

0.50.596

0.60.4144

0.70.3223

图6适应度值的收敛过程

图7设备维修调度的甘特图

将FIFO方法、标准PSO求解方法和改进PSO求解方法进行比较,三种方法的设备维修调度结果和计算结果如表6所示.

表6先来先服务、标准PSO、改进PSO方法调度结果的比较

方法维修任务序号

123456789101112维修时间

/min维修成本

/元

FIFO方法P2P1P4P5P1P2P4P2P5P5193424230

标准PSO方法P5P1P4P4P4P2P5P2P1P3175721963

改进PSO方法P2P1P4P4P5P2P2P4P1P1168620587

实验结果表明,改进PSO方法优于FIFO方法和标准PSO方法,维修时间比FIFO方法和标准PSO方法分别减少了13%和4%,维修成本比FIFO方法和标准PSO方法分别节约了15%和6%.因此,从实验可以得出,采用改进PSO算法进行设备维修调度能够实现维修人员的优化调度,更加有效地提升设备维修的效率,降低设备维修的成本.

4结论

本文针对离散制造企业的生产设备维修调度问题,以维修时间最短和维修成本最低为目标,构建多目标优化模型.针对标准粒子群算法后期易陷入局部最优的缺陷,从惯性权重调整方式、速度更新公式和位置更新公式三方面对标准粒子群算法进行改进.采取顺序编码方式,采用线性加权法将多目标转变为单目标,运用改进粒子群算法对模型进行实例求解.实例结果表明,改进粒子群算法明显优于传统的FIFO调度方法;在相同的迭代条件下,相对于标准粒子群算法能够找到更优的全局极值,验证了改进粒子群算法的有效性.

参考文献:

[1] YARE Y, VENAYAGAMOORTHY G K. Optimal maintenance scheduling of generators using multiple swarmsMDPSO framework[J]. Engineering Applications of Artificial Intelligence,2010,23(6):895910.

[2] AISSANI N, BELDJILALI B, TRENTESAUX D. Dynamic scheduling of maintenance tasks in the petroleum industry: A reinforcement approach[J]. Engineering Applications of Artificial Intelligence,2009,22(7):10891103.

[3] 厉红,钱省三.半导体制造设备的维修调度研究[J].中国机械工程,2006,17(16):16931697.

[4] 王正元,朱昱,宋建社,等.动态维修任务调度的优化方法[J].机械工程学报,2008,44(1):9297.

[5] 杨琴,周国华,李艳茹,等.汽车维修车间作业排序的优化模型及调度算法[J].计算机应用研究,2010,27(5):16861689.

[6] 杨少华,王瑛,刘刚.多目标军用飞机维修作业调度优化研究[J].计算机工程与应用,2016,52(14):1926.

[7] 吕学志,陈乐,尹健,等.考虑休息的维修任务调度模型及其求解算法[J].兵工学报,2014,35(12):21162123.

[8] 李葆文,徐保强.规范化的设备维修管理:SOON[M].北京:机械工业出版社,2006:4950.

[9] 纪震,廖惠连,吴青华.粒子群算法及应用[M].北京:科学出版社,2009:1617.

[10] HUREL J, MANDOW A, GARCíACEREZO A. Tuning a fuzzy controller by particle swarm optimization for an active suspension system[C]//Proceedings of the 38th Annual Conference of the IEEE Industrial Electronics Society. IEEE,2012:25242529.

[11] CHALERMCHAIARBHA S, ONGSAKUL W. Stochastic weight tradeoff particle swarm optimization for nonconvex economic dispatch[J]. Energy Conversion and Management,2013,70:6675.

[12] ELGALLAD A, ELHAWARY M, SALLAM A. Enhancing the particle swarm optimizer via proper parameters selection[C]//Proceedings of the 2002 IEEE Canadian Conference on Electrical & Computer Engineering. IEEE,2002:792797.

Study on Optimization of Equipment Maintenance Scheduling

Based on Modified Particle Swarm Optimization Algorithm

HONG Zhifeng, DONG Baoli

(Faculty of Mechanical Engineering & Automation, Zhejiang SciTech University, Hangzhou 310018, China)

Abstract: To ensure the continuity and reduce the maintenance cost of production system of discrete manufacturing enterprises, an equipment maintenance scheduling optimization model was built for minimizing maintenance time and maintenance cost, and the model was solved with modified particle swarm optimization algorithm. Considering the defect that it is liable to fall into local optimum with the particle swarm optimization algorithm in the later iteration, the discending inertia weight of exponential function was adopted for balancing the global search capability and local search capability of the algorithm, and velocity perturbation and flying time factor were introduced into the velocity updating formula and the location updating formula respectively to improve the convergence ability of the algorithm. The effectiveness and adaptability of the method he been proved via case study of equipment maintenance scheduling of production workshop of a machinery company.

Key words: equipment maintenance; scheduling; multiobjective; modified particle swarm optimization algorithm

(责任编辑: 康锋)

粒子群算法论文参考资料:

简而言之:上述文章是一篇关于设备维修和粒子群算法和调度方面的相关大学硕士和粒子群算法本科毕业论文以及相关粒子群算法论文开题报告范文和职称论文写作参考文献资料。

和你相关的