考虑设备可用性约束的单机调度问题

王金凤，陈 璐，杨雯慧

(上海交通大学 工业工程与管理系，上海 200240)

传统调度方法假设设备总是可用的，但在实际生产过程中，许多因素会导致设备不可用，如更换刀具、设备检修、设备突然故障等情况.当这些情况发生时，设备的不可用约束较容易量化，可以通过定义周期性不可用时段[1-2]，或通过定义设备失效函数定义不可用约束[3].而当设备中的关键部件发生可靠性退化而影响工件的加工质量、加工速度或加工能耗时，设备同样具有不可用性[4-5].因此，考虑设备状态对可用性约束的影响对于生产调度具有重要的现实意义.然而，如何量化此类设备的可用性约束是一个很大的挑战.在现有文献中，没有统一的方法来量化设备状态对可用性的影响，应用最广泛的是利用可靠性来衡量设备状态，进而对设备的可用性进行量化[6-7].

在现有文献中，设备不可用性通常分为单周期不可用、多周期不可用、柔性不可用3类，多数是以维护为代表的操作造成的设备不可用.Lee[8]作为开创者，首次在生产调度问题中考虑设备不可用，考虑单次已知开始时间和持续时间的不可用间隔.Kubzin等[9]在考虑设备单周期不可用时，假设其持续时间依赖于启动时间，具有可控长度.但实际上，单周期不可用是对实际生产情况过分简化的结果，与现实情况存在较大差异.Yu等[1]在此类问题中引入开始时间和持续时间都已知的多周期不可用间隔.蒋凯丽等[2]在模型中考虑具有时间窗的多周期不可用间隔.但由于影响间隔周期长短的因素较多，难以准确计算.当周期过短时会造成资源浪费，而周期过长又会导致设备失效率增加[10].Ahmadi等[11]引入基于状态的不可用间隔，并通过对比实验得出采用基于状态的不可用间隔更具有现实应用意义的结论.Yildirim等[12]在研究中提出，当可靠性低于临界阈值时，需引入单一级别的不可用间隔.Chen等[13]在此基础上引入柔性不可用间隔，按照其效果分为3个级别：① 将设备恢复如新；② 改善部分设备状态；③ 仅将设备恢复到失效前的工作状态.但在上述研究中，设备失效并没有被考虑在模型中.丁珮雯等[14]和Salmasnia等[3]在考虑设备状态的单机调度问题研究中，也引入了柔性不可用.但以上研究均未考虑由可靠性过低而引发的设备不可用问题[15].

本文对单机调度问题进行了研究，同时考虑设备失效和设备可靠性对可用性的影响，选用不同类型的维护作业对设备状态进行恢复，建立以最小化总拖期时间为优化目标的数学规划模型，并设计开发了遗传算法(GA)对问题进行求解，最后利用算例分析对算法的有效性及效率进行验证.

1 设备可用性的定义

在可靠性、维修性术语中，将可用性定义为在要求的外部资源得到保证的前提下，设备在规定的条件下和规定的时间区间内处于可执行规定功能状态的能力.利用设备可靠性对“可执行规定功能状态的能力”进行量化.假设设备故障函数服从Weibull分布，可以表示为[16]

ρ(u)=λβuβ-1

(1)

式中：λ和β分别为Weibull分布的比例参数和形状参数；u为设备役龄.当β>1时，该过程为非齐次泊松分布过程(NHPP)，设备故障率随时间的增长而逐渐增大.在此过程中，设备可靠性R可表示为

(2)

本文提出两种等级的预防性维护策略：不完全维护 (IPM) 和完全维护 (PPM).IPM仅改善部分设备状态，而PPM将设备状态恢复如新.设备可靠性随加工时间的演化过程如图1所示.可靠性阈值δ作为衡量设备是否可用的标准，假设当设备可靠性介于[δ,1]时，设备可用；而介于[0,δ)时，设备不可用.由图1可知，工件4和工件7的加工将导致设备可靠性超过临界阈值，因此，必须在这两个工件开始加工之前进行维护.此时，需要在维护时间和维护效果两者之间进行权衡，确定维护级别(IPM或PPM)，即选择IPM所需维护时间较短，但可靠性改善程度有限，而选择PPM可以使设备修复如新，但是所需维护时间较长.

图1 设备可靠性和可用性的关系Fig.1 Machine reliability versus availability

2 模型的建立

在考虑设备状态的单机调度问题中，需要对工件集合N中的工件进行排序，目标是最小化总拖期时间.两个相邻工件中可以插入一次IPM或PPM以改善设备状态.模型假设包括：① 在0时刻，所有工件均可加工；② 在加工前，设备役龄为0；③ 设备在同一位置只能加工一个工件，且一个工件只需加工一次；④ 忽略设备在加工不同工件之间的准备时间；⑤ 在加工过程中，设备发生故障修复后，被中断的工件可以继续加工，不需要额外的加工时间.

基于可靠性理论中的最优维护间隔(T*)，设备可靠性的临界阈值可表示为

(3)

基于NHPP假设，工位j上的累积故障次数可表示为

λ[(ufj)β-(ub1)β]

(4)

式中：ub1=0.

模型的决策变量为

由此建立数学模型如下：

(5)

s.t.

(6)

(7)

(8)

tPPMzj+tF(Mj-Mj-1)

(9)

∀i∈N,∀j∈N

ubj=uf(j-1)(1-θyj-zj),∀j∈N

(10)

ufj≥ubj+xijpi,∀j∈N

(11)

e-λ[(ufj)β-(ubj)β]≥δ,j∈N

(12)

yj+zj≤1,∀j∈N

(13)

(14)

∀i∈N,∀j∈N

3 算法设计

考虑设备状态的单机调度问题已被学者证明是NP难问题[17]，引入计算可靠性的非线性约束(约束12)，增加了求解难度.Lingo等商业求解器只能对有限规模的问题进行计算.因此，研究采用更为高效的遗传算法进行求解，并通过C++语言实现.

3.1 编码与解码

染色体对工件加工序列进行编码，图1中算例的编码染色体如图2所示.

图2 染色体编码方式Fig.2 Chromosome coding

通过对染色体进行解码，确定维护位置和维护方式，获得一个完整的调度策略，其解码算法如算法1所示.

算法1解码

1.已知各工位j上的待加工工件的序号、加工时间以及δ.

2.根据式(2)，计算工位j在完成工件加工后的设备可靠性R.

3.若R≥δ，则yj=zj=0，即表示不需要任何类型的维护.

4.否则，令yj=1,即假设在工位j上进行IPM，并计算该工位在完成工件加工后的设备可靠性R′.

5.若R′≥δ，则yj=1,zj=0，即在工位j上进行IPM.

6.否则，yj=0,zj=1，即在工位j上进行PPM.

7.j++，若j≤|N|，则返回步骤2；否则，继续步骤8.

8.将各工位上的维护操作和工件序列结合，获得完整的调度方案.

利用上述算法对图2中的染色体编码进行解码，获得一个完整调度方案，如图3所示.

图3 完整调度方案Fig.3 A complete schedule for sample problem

3.2 种群初始化

种群规模的大小会影响算法的性能及效率，所提算法中，种群规模Npop=50.首先，采用完全随机的方式生成45个不同的个体作为初始解，继而利用最早交货期启发式(EDD)规则生成5个较好的初始解，这样既保证了初始种群的多样性，同时能提高算法的收敛速度.

3.3 评价与选择

3.4 交叉与变异

考虑到染色体代表个体的可行性，故对实数编码的工序染色体采用两点式交叉方法.交叉概率范围一般为0.4～0.9.同样，为保证染色体的可行性，对工序染色体采用换位变异方式.在变异过程中，引入Emmons规则[18]确定工件的优先关系，缩小搜索空间[19].

设Bi和Ai分别为在工件i加工前和加工后的工件集合，记为Bi→i和i→Ai.j

变异的发生需满足上述优先规则，定义pm为变异概率.算法2详细描述了变异过程.

算法2变异

1.已知各工位j上待加工工件的序号i、加工时间pi和交货期di；

2.对于任意染色体，随机生成(0，1)之间的数a；

3.若a>pm，则该染色体不进行变异，i++,返回2；

4.否则，随机生成两个满足条件j

3.5 算法流程

完整算法流程可见算法3.

算法3遗传算法

1.已知算法参数Npop，Gmax，pc和pm.

2.初始化第1代种群，解码后计算适应度值，得到最优个体π*和最差个体ω，并将π*的染色体序列复制给ω.

3.基于轮盘赌选择法在种群中选取两条染色体作为父代.

4.对父代进行交叉操作，得到子代.

5.对子代进行突变操作，得到新的子代.

6.对新的子代染色体解码后，计算其适应度值，得到当前代最优个体π，最差个体ω，将 π的染色体序列复制给ω，并更新全局最优个体π*.

7.g++，若g≤Gmax，则返回3；否则，继续8.

8.返回最优个体π*.

其中：g为当前代数；Gmax为最大迭代次数；pc为交叉概率；π*为最优个体；π为当前代最优个体；ω为当前代最差个体.

4 算例验证与分析

4.1 小规模算例验证

为证明遗传算法的有效性，将遗传算法所求的解与商业求解器Lingo所求的最优解进行比较.考虑8种不同规模的问题，分别在每种规模下生成10个算例.设置Lingo求解时限为 5 400 s.两种解的比较如表1所示.其中，OLin和OGA分别为Lingo求解器和GA所求解的目标值；tCPU为运算时间.

由表1可知，在小于8个工件的算例中，GA不仅得到了最优解，而且在求解时间上明显优于Lingo.当工件数量增加时，Lingo求解器无法在限定的时间内得到最优解，此时GA得到的最优解优于Lingo在规定时间内得到的最优解.因此，遗传算法的有效性得以验证.

表1 小规模算例实验结果Tab.1 Results of small-scale instants

4.2 中、大规模算例验证

为了评估不同类型的维护作业对调度策略的影响，首先对GA进行修改，得到以下两种算法：

(1) GA-IPM：对任意一个工位j，令zj=0，此时算法只考虑IPM.

(2) GA-PPM：对任意一个工位j，令yj=0，此时算法只考虑PPM.

将第3节中提出的GA所求的解作为基准解，分别计算GA-IPM和GA-PPM所求解的偏差：

(15)

(16)

式中：OTPM，OIPM和OPPM分别为GA、GA-IPM和GA-PPM所求解的目标值，其结果如表2所示.

表2 不同GA在中、大规模算例中的表现Tab.2 Performance of different GAs on medium and large scales

由表2可知，同时考虑两种维护作业对减少总拖期时间具有一定的优越性，这种优越性随问题规模的增大而减小，最终趋于稳定，相比于GA-IPM和GA-PPM的改善分别维持在25%和5%左右.另外，与GA-IPM相比，GA-PPM表现更优.由此可见，虽然PPM耗时长，但能更显著降低设备的失效风险，从而达到缩短总拖期时间的效果.

4.3 敏感性分析

下文将分别针对可靠性阈值和设备状态改善因子进行敏感性分析.

4.3.1可靠性阈值对调度决策的影响 考虑3个级别的可靠性阈值，分别为δ=0.5，δ=0.6，δ=0.78.其中，δ=0.78是通过式(3)计算出来的临界阈值.在其他参数设置保持不变的情况下，对比不同可靠性阈值对调度决策的影响，如图4和5所示.其中：tW为总拖期时间；L为维护次数.

由图4可知，随着可靠性阈值的增加，总拖期时间增大.问题规模越大，这种变化趋势变得更加明显.造成这种现象的原因为，随着可靠性阈值的增加，设备需要更频繁的维护作业，使得设备可靠性能够保持在阈值之上.而当维护作业时间增加时，总拖期时间也增加.然而，当设备可靠性阈值降低时，设备在加工时的状态较差，将会导致加工工件的质量降低.

图4 不同可靠性阈值下的总拖期时间Fig.4 Total tardiness at different reliability thresholds

由图5可知，当可靠性阈值增加时，采用IPM的次数增加，采用PPM的次数减少.原因是IPM能够以较短的耗时将设备可靠性恢复到阈值之上，而PPM则在恢复效率(改善效果与维护时长的比值)上稍显劣势.由此可见，在可靠性阈值增加时，调度决策更加侧重维护的效率.

图5 不同可靠性阈值下的维护次数Fig.5 Times of maintenance at different reliability thresholds

4.3.2状态改善因子对调度决策的影响 考虑3种不同程度的状态改善因子，分别是θ=0.3，θ=0.4，和θ=0.5.在其他参数设置保持不变的情况下，对比不同状态改善因子对调度决策的影响，如图6和7所示.

由图6可知，当改善因子增加时，总拖期时间相应降低，这种变化趋势随着问题规模的增大而变得更加明显.这是由于在IPM耗时不变的前提下，随着改善因子的增加，IPM的效率提高，节省了维护时间，从而减少了总拖期时间.

图6 不同改善因子下总拖期时间的变化曲线Fig.6 Total tardiness with different improvement factors

由图7可知，当改善因子增加时，采用IPM的次数增加，PPM的次数减少至0.

图7 不同改善因子下的维护次数Fig.7 Times of maintenance with different improvement factors

以上结果表明，在实际生产调度决策时，可以通过提高维护效率，提高可靠性改善效果来降低生产交付的压力.

5 结语

本文研究了某转子车间内单台设备的生产调度问题，考虑设备可用性约束，以及不同级别的维护作业，优化目标为最小化总拖期时间.优化模型中通过可靠性来表征设备的可用性约束，减少当设备可靠性下降时对加工质量的影响.设计开发了遗传算法对模型进行优化求解.实验结果表明，所提方法能够有效量化设备可用性对生产调度的影响，并能够合理地选择不同类型的维护作业，以减少总拖期时间.灵敏度分析为车间内实际生产调度提供决策支持，具有实际应用价值.后续研究将把该方法应用于更复杂的生产环境中，如并行机、流水线生产等.