考虑设备预防性维护的开放车间调度问题

朱传军 冯诗健 张超勇 金亮亮 王林琳

1.湖北工业大学机械工程学院,武汉,4300682.华中科技大学数字制造装备与技术国家重点实验室,武汉,430074 3.绍兴文理学院机械与电气工程学院,绍兴,312000

0 引言

开放车间调度问题(open shop scheduling problem,OSSP)是最基本的调度问题之一[1]。相较于流水车间调度问题(flow-shop scheduling problem, FSP)和作业车间调度问题(jop-shop scheduling problem, JSP),开放车间调度问题具有更大的可行解空间、更高的复杂度。机器数量极大影响开放车间调度的计算复杂度,当有三台或更多的机器时,它就是一个NP-hard问题。

目前在开放车间调度领域研究最多的性能指标是最小化最大完工时间。高亮等[2]以最小化最大完工时间为性能指标,采用粒子群优化算法求解了传统开放车间的调度问题,并获得了满意的结果。王军强等[3]提出一种基于多样性增强的自适应遗传算法,设计了多种进化算子,提高了遗传算法的进化效率和进化质量,求得了Taillard算例库60个算例的最优解。

实际的开放车间调度中,每个设备都可能发生故障,因此需要对设备进行维护,防止设备失效导致的生产中断。目前主流的设备预防性维护的方式包括传统的周期性维护和非周期性维护。PASURA等[4]采用传统的周期性维护方式对给定仪器设备进行维护。宋文家等[5]研究柔性作业车间调度问题时,在模型中加入了对设备的非周期预防性维护。SHEIKHALISHAHI等[6]研究了带有非周期预防性维护及人工失误的开放车间调度问题。相较于周期性维护,非周期预防性维护更为灵活、更贴合实际,并能有效避免设备欠维护或过度维护。目前的研究考虑设备预防性维护的开放车间调度问题较少涉及,相关研究起步较晚,因此,如何将预防性维护集成到开放车间调度优化中是一个开放的问题。

采用非周期预防性维护时,不同的生产环境和设备的故障率分布函数通常不同。工业中,通常采用指数分布来描述故障发生的概率;制造车间中,机械设备和电子元件等的故障率一般服从威布尔分布。威布尔分布遵循统计学规律,可以有效反映调度问题中机器运行时间和状态对设备役龄的影响[7]。

开放车间调度问题和作业车间调度问题的求解具有很大的相似性。张超勇等[8]提出一种进化禁忌混合算法,并设计了IPOX交叉算子和禁忌搜索的新邻域结构,取得了车间调度问题的高质量解。CAMINO等[9]针对具有模糊作业时间和柔性交货期的作业车间调度问题,采用进化禁忌搜索算法取得了调度问题的满意解。具有良好全局搜索能力的遗传算法和具有优秀局部搜索能力的禁忌搜索算法相结合可产生更均衡的搜索算法,因此本文借鉴求解作业车间调度问题的优秀算法,选择混合遗传禁忌搜索算法来求解考虑设备预防性维护的开放车间调度问题。

1 设备预防性维护

1.1 服从威布尔分布的概率密度函数

采用二参数威布尔分布描述一般设备的故障规律,判断其是否达到给定的故障率阈值,进行预防性维护,二参威布尔分布的率密度函数为

(1)

式中,β、θ分别为形状参数和尺度参数,β>0,θ>0;t为机器役龄。

β决定曲线形状,θ决定曲线横轴和纵轴的尺度。服从二参威布尔分布的积故障函数为

(2)

可靠度函数为

(3)

则设备达到可靠度阈值时的役龄为

t=θ(-lnR(t))i/β

(4)

使用过程中,设备状态不断变化,役龄也会缩短,既使进行了维护,设备还是不能回到最初的状态,因此采用役龄退回因子pm来描述这一过程的变化,经过预防性维护后设备的实际役龄变为(1-pm)t。

1.2 极大似然估计法

采用极大似然估计法求解二参威布尔分布中的β和θ[10-11]。服从二参威布尔分布的似然函数为

(5)

通过两边取对数,可得对数似然函数:

(6)

继而分别对β和θ求偏导,得如下公式:

(7)

(8)

式中,n为历史故障数据的数量;ti为第i个历史故障的实际役龄。

将历史故障数据代入式(7)、式(8),利用牛顿迭代算法对其进行求解,即可求出参数β和θ。

1.3 设备的预防性维护

在生产调度和机器维护的集成问题上,设备维护与工件调度不能发生冲突,即设备维护只能安排在工件加工前后。为解决这一问题,本文采用动态安排设备维护的方法[5],具体过程如下:

(1)首先按照单纯的开放车间调度进行决策,决定每个工序的加工顺序以及每个机器上工件的加工顺序。

(2)安排每道工序前,先计算出每台加工机器的当前役龄。如果完成该道工序后的机器故障率超过所给故障率阈值(役龄退回因子)pm,则在该工序前安排一次预防性维护;否则,安排下一道工序。

(3)安排预防性维护后,重新计算机器完成当前工序后的运行时间。

(4)重复步骤(2)和(3),直到安排完所有的工序。

2 考虑预防性维护的开放车间调度数学模型

优化目标为

minCmax

(9)

约束条件如下:

Yii′k+Yi′ik=1 ∀i≠i′∈N,∀k∈M

(10)

Xijj′+Xij′j=1 ∀i∈N,∀j≠j′∈M

(11)

Si′j-Sij≥tij+dkZij-L(1-Yii′k)

(12)

∀k,j∈M,∀i≠i′∈N

Sij′-Sij>tij-L(1-Xijj′)

(13)

∀i∈N,∀j≠j′∈M

Cmax≥Sij+tij+Zijdk

(14)

∀i∈N,∀j,k∈M

其中,Cmax为最大完工时间;i、i′为工件编号;j、j′、k为机器编号;N为工件集合,N={1,2,…,n};n为工件总数;M为机器集合,M={1,2,…,m};m为机器总数;Yii′k表示机器k上的零件i′和零件i的加工顺序,零件i′在零件i之前加工时,Yii′k=0,否则Yii′k=1;Xijj′表示零件i上的第j道工序和第j′道工序的加工顺序,第j道工序在第j′道工序之前加工时,Xijj′=1,否则Xijj′=0;Sij为零件i的第j道工序的开始加工时间;tij为工件i的第j道工序的加工时间;dk为机器k一次预防性维护所需时间;Zij表示工件i的第j道工序后面是否安排预防性维护,如果安排,则Zij=1,否则Zij=0;L为一个很大的正整数。传统的开放车间调度问题中,一个工件的工序数量与设备数量一致,同一工件的各工序在不同的设备上完成。

3 遗传禁忌搜索算法

3.1 遗传算法

3.1.1编码

编码是设计遗传算法的关键。编码须考虑合法性、可行性、有效性,以及对问题解空间表征的完全性。本文采用基于工序的编码,以确保解码总能得到可行调度,并涵盖所有的问题解空间。表1所示为染色体(4, 8, 0, 5, 1, 3, 7, 2, 6)中的元素对应的工件编号和加工机器编号。

表1 染色体解析表

3.1.2解码

本文采用插入式贪婪解码算法[12]对染色体进行解码,该算法可以确保染色体解码后产生主动调度。插入式贪婪解码算法操作方法如下:遍历染色体上的基因,找到与该基因对应工序的加工机器,然后在该机器上搜索该工序最早的加工时间,并将该工序安排在此时间开始。

3.1.3交叉算子

自适应交叉算子是一种改进的交叉算子,它根据种群中个体的适应度动态调整交叉概率和交叉方式,以提高算法的性能和收敛速度。种群中的个体适应度较大时,交叉概率减小,避免该个体的优良基因被破坏,算法早熟收敛到局部最优;个体适应度较小时,交叉概率增大,以促进探索更大的搜索空间。交叉概率的计算公式为

Pc(i,j)=

(15)

式中,Pc(i,j)为个体i和个体j的交叉概率;hmax、havg分别为当前种群的最大适应度和平均适应度;h(i,j)为与最优个体相交叉的个体的适应度;K1、K2为交叉概率修正系数(常数),K1,K2∈(0,1)且K1≠K2。

本文对交叉策略进行适当改进,具体操作方法如下:首先规定2个交叉个体P1和P2,定义大小与P1和P2相同的空白个体S1和S2,将当前种群中的最优个体作为P1,在剩下的个体中选出一个作为P2。交叉操作时,如果交叉对象的交叉概率较大,则将P2染色体上少部分的基因映射至容器S2对应的基因序号上,并将P1中的基因(不包含S2上已有的)依次插入到S2的空白位置。种群中的最优个体P1则进行与P2相反的操作,即将P1染色体上大部分的基因映射到容器S1对应的基因位,将P2中的基因(不包含S1上已有的)依次插入到S1的空白位置。对S1和S2进行解码并比较S1和S2的适应度,将其中更优良的个体放入新的种群。经数据检验,该交叉方式提高了遗传算法的稳定性。

3.1.4变异操作

变异操作通过引入一些新的个体来增强种群的多样性。尽管变异操作在一定程度上具有局部搜索的作用,但作用有限。本文采用的变异策略是随机选择染色体中的2个基因并交换它们的位置。

3.1.5增强种群多样性算子

算法迭代进化的过程中,调度的解会逐渐向最优解或近似最优解靠拢,因此个体差异逐渐减小,种群多样性不断降低,可能导致算法陷入局部最优。增强种群的多样性可以增大算法的搜索空间,避免算法过早陷入局部最优。文献[3]基于随机二分法原理设计的主动式种群多样性判定算子降低了对邻域局部解集的搜索能力,但增强了种群的多样性。在增强种群多样性的同时,本文采用局部搜索能力更好的禁忌搜索算法。

实现种群多样性增强算子时,需要引入多样性判定阈值w,将初始种群、交叉种群和变异种群合并,并判断合并后的种群的多样性是否达到多样性指标判定阈值。如果种群的多样性达到多样性指标判定阈值,则不进行任何操作;否则,对种群中的冗杂个体进行随机二分洗牌操作,以增强种群的多样性。

3.1.6选择算子

本文采用轮盘赌的方式从多样性判定后的合并种群中选择出子代种群。假设初始种群数量为P,则合并种群数量W=3P。轮盘具体操作如下:

(1)计算合并种群Wp中个体i的适应度h(i),i=1,2,…,W。

(2)计算种群中个体i被选中进入下一代群体中的概率pi:

(16)

(3)计算个体i的累积概率qi。计算第i个个体的累积概率时,需要将第1个个体到第i个个体的所有概率累加:

(17)

(4)生成的随机数R在[0, 1]区间内服从均匀分布。

(5)若R

(6)判断下一代种群中的个体数量是否小于P,如果小于,则重复步骤(4)、步骤(5),反之,则结束轮盘赌操作。

3.2 禁忌搜索算法

3.2.1邻域结构设计

在解决开放车间调度问题时,禁忌搜索是一种非常有效的局部搜索算法。邻域结构的设计是禁忌搜索中非常关键的一个步骤,它决定了搜索空间的大小和搜索质量。本文采用的邻域结构的设计思路如下:

首先找出当前调度的关键路径,其次将关键路径划分为关键块,最后对关键块内的工序进行调整,产生邻域解,本文采用NOWICKI等[13]提出的N5邻域结构。以保证所有移动产生的解不会变差。该邻域结构的具体操作如下:

(1)如果第一个关键块包含2个以上的工序,则只交换块尾的2个工序;如果最后一个关键块包含2个以上的工序,则只交换块首相连的2个工序;如果该关键块只包含2个工序,则只交换这2个工序。

(2)首尾关键块以外的关键块如果有3个或3个以上的工序,则交换块首和块尾的2个工序。

(3)如果关键块只包含1个工序,则不进行任何操作。

开放车间调度问题中,对同一工件的不同工序或同一机器的不同工序均没有固定的先后要求,因此在调整关键块时,需要考虑的两种情况,如图1、图2所示,其中,PJ(n)、SJ(n)分别为某个工件的工序n(n=i,j)的紧前工序和紧后工序,PM(n)、SM(n)分别为某台机器完成的工序n的紧前工序和紧后工序。

图1 同一机器上交换弧

图2 同一工件上的交换弧

如图1所示,对于由同一个机器完成的工序i和j,邻域结构的交换方式可分为4种:①交换弧(i,j);②同时交换弧(i,j)和(PJ(i),j);③同时交换弧(i,j)和(i,SJ(i));④同时交换弧(i,j)、(i,SJ(i))、(PJ(i),j)。

如图2所示,对于属于同一个工件的工序i和j,邻域交换方式可分为4种:①交换弧(i,j);②同时交换弧(i,j)和(PM(j),j);③同时交换弧(i,j)和(i,SM(i));④同时交换弧(i,j)、(i,SM(i))、(PM(j),j)。

3.2.2禁忌表和禁忌长度

禁忌表用于记录邻域解产生过程中已交换过的弧,避免禁忌搜索的重复搜索。实际运用中,禁忌表的长度可以不固定,但禁忌表太短可能导致可行解得不到充分搜索,陷入局部解,太长则会影响到算法的效率。因此,本文采用在给定区间内随机取值的方法确定禁忌表的长度。

3.2.3精华解机制

本文采用的精华解机制[8]操作如下:在禁忌搜索的过程中,如果发现比当前解更好的解,则将其加入精华解集。算法运行给定的最大未改进代数后,若未出现更优解,则从精华解集中取出解,将其作为当前解,并清空禁忌表,重新进行禁忌搜索。

3.2.4移动选择

如果某次移动产生的解优于当前解,但该次移动处于禁忌状态时,则对其进行豁免并解禁。如果所有的移动都处于禁忌状态,则从所有被禁忌的移动中随机选择一个,并将其解禁。

3.2.5终止准则

算法运行给定代数或找到最优解时终止。

3.3 混合遗传算法和禁忌搜索算法

遗传算法和禁忌搜索算法融合的关键在于编码的相互转化。本文中的遗传算法采用基于工序的编码方式,该种编码方式可以保证父辈优良的基因在遗传进化的过程中被子代继承,禁忌搜索则采用的是基于析取图的编码方式。目前,基于析取图的编码与基于工序的编码的相互转换已在作业车间调度中得到应用[8]。在开放车间调度中,基于工序的编码和主动调度的析取图编码之间也可以进行相护转换。为了更清晰地表述遗传算法和禁忌搜索算法的混合,给出了遗传禁忌搜索算法的简化框架,如图3所示。

图3 遗传禁忌算法框架图

4 算法的时间复杂度分析

遗传禁忌搜索算法由遗传算法和禁忌搜索算法组合而成,每个算法部分又由多种算子组成。因此整体的时间复杂度分析依靠对各个算子的分析,并将这些组成部分中的时间复杂度最大值作为算法的时间复杂度。

遗传算法的复杂度与初始种群数量P、工件数量N、机器数量M相关。在遗传算法中,初始种群生成算子的时间复杂度为O(NPM),主动调度解码的时间复杂度为O(N2PM),自适应交叉的时间复杂度为O(NPM),变异算子的时间复杂度为O(P)。

种群多样性增强的算子中,多样性判断算子的时间复杂度为O(W2NM)。选择算子与工件数量和机器数量无关,其时间复杂度为O(WP)。

禁忌搜索算法的时间复杂度是不断变化的,它与关键路径长度Kp、关键模块个数Kn、关键模块长度Kl、禁忌表长度Tl、禁忌搜索代数Gt、初始种群数量P、工件数量N以及机器数量M有关,因此需要根据实际问题的特性来确定。本文中,禁忌搜索算法的时间复杂度取其在变化过程的最大值O(NPMGt)。

从整体算法的角度来看,需要综合考虑各个参数对遗传禁忌搜索算法时间复杂度的影响。但从实际问题的特性来看,本文所提遗传禁忌搜索算法的时间复杂度主要由遗传算法的解码复杂度、多样性增强复杂度和禁忌搜索算法的复杂度决定。

5 计算结果与分析

本文算法使用C++语言编程,计算机为Intel I5-6300HQ多核的个人计算机,算法参数设置如下:初始种群规模P= 30;交叉概率修正系数K1=0.75,K2=0.99;变异概率Pr=0.05;多样性判定阈值w=0.95;禁忌表长Tl在区间[8,12]之间随机取值;禁忌代数Gt=200;最大未改进代数Tn=10。

为验证本文所提算法有效性,实验案列采用Taillard[14]系列OSP标准测试实例的40个实例(4×4、5×5、7×7、10×10的实例各10个),将本文提出的遗传禁忌搜索(GATS)算法、猫群优化[15](CSO)算法、蝙蝠群优化(BA_OS)算法[16]相比较,运算结果见表2,其中,t为GATS算法求得最优解的运行时间。

表2 算例结果

由表2可以看出GATS算法和BA_OS算法在求解单纯的调度问题时均能求得所有算例的最优解,CSO算法能求出大部分算例的最优解,这验证了所提算法的有效性和稳定性,能用来求解该类复杂的调度问题。图4是实例10×10的算例1的最优调度甘特图。

图4 实例10×10 的算例1的最优调度甘特图

本文选取实例7×7的算例1,并在该算例中加入了预防性维护这一过程。将每台设备的历史故障数据代入最大似然估计法的函数,在MATLAB上利用牛顿迭代算法仿真获得威布尔分布函数的形状参数θ和尺度参数β。如图5所示,历史故障数据沿一条直线均匀分布,表明收集的故障数据符合威布尔分布,因此可以使用服从威布尔分布的故障率函数模型对设备的故障时间进行预测。表3所示为OSP模型7×7的算例1求解得到的设备维护相关数据,设备的可靠度阈值为0.85。

图5 威布尔分布拟合图

表3 实例7×7的算例1的设备维护相关参数

利用遗传禁忌搜索算法对该带预防性维护的调度模型进行求解,非周期预防性维护的结果如下:机器M1、M2、M5、M6的维护次数为2,机器M3的维护次数为3,机器M4、M7的维护次数为1;总维护次数ψ为13;每台机器的平均维护次数ν为1.85;加工某个工序时,机器超过可靠度阈值进行加工的次数即维护不及时次数δ为0;最大完工时间T为468 s。

非周期预防性维护与周期性维护的最大区别是:非周期性维护通过拟合分析机器故障历史数据来判断下次维护的时间,保证机器一直在可靠度范围内正常运转;周期性维护按照固定周期进行维护,由于没有故障历史数据的支持,因此容易出现机器的过度维护或欠维护。过度维护会导致资源的浪费,而欠维护会导致机器可能发生故障停工,引起不必要的损失。

表4所示为不同周期维护下的结果,为保证结果的一般性,分别选取阈值附近、阈值以下和阈值以上的5组数据进行对比分析。由表4可以看出,周期性维护的周期过短时,设备的维护次数显著增大,调度时间延长。周期性维护的周期过长时,虽然工件完工时间变短,但设备处于欠维护状态的次数明显增多。图6所示为在设备预防性维护下,该算例所得到的满意调度方案。

图6 实例7×7的算例1 的维护调度甘特图

表4 周期性维护结果

6 结论

本文根据实际生产车间的运行场景,介绍了一种考虑设备预防性维护的开放车间调度模型,并提出一种混合遗传禁忌搜索算法求解该问题。对所提遗传禁忌搜索算法的遗传编码和解码、改进交叉和变异操作,以及禁忌搜索算法的邻域结构进行了设计,得到了一种搜索能力更均衡的混合算法。以最小化最大完工时间为目标,将所提算法用于求解开放车间调度问题的基准问题和带设备预防性维护的开放车间调度问题,获得了开放车间调度问题基准实例问题的最优解和带设备预防性维护开放车间调度问题的满意解。预防性维护下,调度车间的维护更加灵活有效且符合实际。实际生产车间中存在许多不确定的问题,并且可能涉及多个性能指标的求解,未来工作将开展考虑设备预防性维护的不确定性和多目标开放车间调度问题。