串联生产系统维护在线决策与缓冲分配联合优化

摘要

针对生产系统的退化状态不能在线获取的问题，提出了设备维护在线决策与缓冲分配的联合优化模型。以隐马尔科夫退化系统的工件质量指标为决策依据，提出了设备维护的在线决策策略；推导了串联生产系统工件加工时间与完成时间的递推式，建立了在有限缓冲容量下的缓冲分配模型。以最小化总成本为优化目标，建立了以执行设备维护的质量阈值与缓冲分配为联合决策变量的数学模型。以基于设备跃迁过程的蒙特卡洛仿真算法估计系统期望成本，采用禁忌搜索算法对模型求解，并提出元胞自动机制邻域规则优化搜索过程。数值实验表明提出的联合优化模型及算法的有效性。

关键词

串联生产系统; 维护; 质量; 在线决策; 缓冲分配

质量控制和设备维护是生产系统的关键环节，为了提高生产系统的加工质量，保证其具有一定的生产加工能力，科学地制定维护策略和质量控制策略至关重要。视情维护是一种基于设备状态的维护策略，其已被证明在节约成本和提高生产系统可用性方面具有优势^［1-2］。但考虑技术限制，视情维护的状态检查工作和设备维护活动均需停机完成^［3］，而在串联生产线中停机会造成上游设备的堵塞和下游设备的饥饿，导致生产损失。为解决这个问题，一方面，开发设备维护的在线决策策略可以避免设备的停机检查，减少设备停机次数；另一方面，科学合理的配置串联生产系统的缓冲容量可以减少由于上下游设备停机导致的饥饿和堵塞，从而降低生产损失。设备维护、加工质量与缓冲容量总是交互地影响加工过程，研究其联合优化策略具有重要价值。

在制造系统中，利用缓冲区库存可以有效减少由设备维护造成的生产损失，保证设备维护时其上下游设备仍能正常生产，因而带有缓冲库存的设备维护问题成为国内外学者的研究焦点。对双机系统，郭闻雨等^［4］以带缓冲的双机系统为研究对象，结合随机波动的加工能力指标与可靠度，动态地描述设备的综合性能退化程度，并研究了维护计划与缓存配置的联合优化方法。Dimitrakos等^［5］假设系统中的上游设备会发生故障、下游设备为完美，以Markov过程对上游设备的维护阈值进行优化，并证明了设立缓冲区对于生产系统的成本优势。GAN等^［6］研究维护、缓冲库存和备件库存之间的相互作用，建立联合优化模型实现生产系统长期成本的最小化。Ribeiro等^［7］针对带瓶颈的两机系统，利用混合整数线性规划模型优化瓶颈设备及其上游设备的维护策略与中间缓冲区容量。对于多机串联生产系统，刘勤明等^［8］和Nahas^［9］分别以设备缓冲量和预防性维护周期为联合决策变量，优化生产系统的成本。王林等^［10］以预防性维护阈值和缓冲区容量为决策变量，提出预防性维护与缓冲容量分配的联合优化模型。成国庆等^［11］假设上游设备不能修复如新，以缓冲区库存控制和设备更换前故障次数为决策变量，运用几何过程建立了退化系统维修更换模型。

上述研究大多针对设备停机故障因素，维护策略均采用等周期或基于役龄的计划维护策略，在生产加工开始之前即确定了维护计划，这会导致进行维护时没有利用设备加工过程的实时信息，增加设备提前或延后维护的风险，造成维护资源和生产资源的浪费。本文针对现有研究的不足，以加工质量发生退化的串联生产系统为研究对象，提出一种基于工件质量指标的在线维护策略，根据加工质量判断设备退化状态从而作出实时决策，并通过与缓冲分配策略的联合优化进一步减少停机损失，通过与计划维护的比较验证了模型的有效性。

1 问题描述

以串联生产系统为研究对象，生产系统在计划期$L$内生产单一产品，产品需求量为$D$，未满足的需求会产生缺货成本。系统共包含$M(M\ge \mathrm{2})$台加工设备，工件从第一台设备进入系统，顺次经过各设备和缓冲区后加工成合格产品，从最后一台设备离开系统。设备$i$加工一个工件的时间为$p_i$。系统中缓冲区的总容量限制为$B$，设备$i$与设备$i+\mathrm{1}$之间的缓冲区容量为$X_i$。对系统假设及符号定义如下：

（1）产品的流动时间忽略不计，第一台设备不会饥饿、最后一台设备不会堵塞；

（2）设备在加工过程中不断发生退化，每台设备均有$S$个等级的退化状态；设备在状态间的跃迁服从马尔科夫过程，不考虑设备的故障停机，设备的初始状态为全新；

（3）设备状态影响加工质量，设备$i$在退化状态$s$下以不合格品率$u_{i,s}$加工工件；

（4）每台设备后均设有检查工位，假设检查是瞬时完成的，能够甄别出合格品与不合格品，不合格工件立即在该设备上进行返工，如图1所示；

图1 带有质量检查工位与缓冲区的生产线示意图

Fig. 1 Serial production system with quality inspection stations and intermediate buffers

（5）在工件加工的间隙可以进行设备维护，维护可以将设备恢复到全新状态。

为减少不合格品带来的生产损失，需要合理地制定维护策略和质量控制策略、安排维护活动，同时决策各缓冲区的容量配置，优化产线平衡、提高生产率，减少缺货成本、在制品库存成本、设备维护成本以及工件返工造成的额外成本，使系统总成本最小化。

2 问题建模

2.1　设备退化及维护建模

假设设备的多状态退化模型服从离散时间马尔科夫过程，该过程有如下属性：

$$\begin{array}{l}\mathrm{P}\mathrm{r}\{s_i(t_n)=s_n|s_i(t_{\mathrm{0}})=s_{\mathrm{0}},s_i(t_{\mathrm{1}})=s_{\mathrm{1}},...,s_i(t_{n-\mathrm{1}})=s_{n-\mathrm{1}}\}\\ =\mathrm{P}\mathrm{r}\{s_i(t_n)=s_n|s_i(t_{n-\mathrm{1}})=s_{n-\mathrm{1}}\}\end{array}$$

（1）

式中：$\mathrm{P}\mathrm{r}(\cdot )$表示取概率函数；$s_i(t_n)$表示设备$i$在第$n$次跃迁后的状态；$t_n$表示第$n$次跃迁的时刻。式（1）表明设备在$n$步跃迁的马尔科夫过程中，第$n$步跃迁的概率只与第$n-\mathrm{1}$步跃迁后的状态有关，而与$n-\mathrm{2}$、$n-\mathrm{3}$、…、1、0步跃迁后的状态无关。马尔科夫过程的状态跃迁概率为

$$q_{i,g,k}=\mathrm{P}\mathrm{r}\{s_i(t+\mathrm{\Delta }t)=k|s_i(t)=g\},\forall i,\forall g,\forall k$$

（2）

式中：$q_{i,g,k}$表示在一次跃迁中设备$i$从状态$g$跃迁至状态$k$的概率；$\mathrm{\Delta }t$表示每一次跃迁经过的设备累积加工时间。由全概率公式有：

$${\displaystyle \sum _{k=\mathrm{1}}^S}{q}_{i,g,k}=\mathrm{1},\forall i,\forall g$$

（3）

设备在初始状态下为全新，有：

$$s_i(\mathrm{0})=\mathrm{1},\forall i$$

（4）

假设设备的退化是一个单调不可逆的过程，则有：

$$q_{i,g,k}=\mathrm{0},\forall i,\forall g,\forall k<g$$

（5）

设备在状态间的转移为隐马尔科夫过程，设备的状态序列为隐含状态链，而不同状态下设备以不同的合格品率加工工件，通过工件质量检查，工件质量序列则构成可见状态链。设备维护可以改善设备状态，从而提高加工质量、减少不合格品及返工。通过对工件加工质量的监测和决策可以实现对设备状态的预测及维护的在线决策。因而，以累计不合格品数作为维护的决策依据，维护子模型的决策变量为：$\mathit{Q}=\{Q_{\mathrm{1}},Q_{\mathrm{2}},...,Q_M\}$，是由$M$个阈值决策变量构成的矢量，分别表示每台设备进行维护时的累计不合格品数。记$O_{i,j}$表示设备$i$加工工件$j$的工序，记0/1变量$t_{i,j}$表示设备$i$在工序$O_{i,j}$完成时是否发生跃迁，若是则为1，否则为0，变量$a_{i,j}$表示设备$i$在上一次维护或跃迁直至工序$O_{i,j}$完成时的累积加工时间。则：

$$t_{i,j}=\left\{\begin{array}{l}\mathrm{1},a_{i,j}\ge \mathrm{\Delta }t\\ \mathrm{0},a_{i,j}<\mathrm{\Delta }t\end{array}\right.$$

记0/1变量$r_{i,j}$表示工件加工质量，工序$O_{i,j}$的加工质量不合格而需要返工则为1，否则为0，$N_{i,j}$表示设备$i$自上一次维护至工序$O_{i,j}$完成时加工的累计不合格品数，$v_{i,j}$表示设备$i$在工序$O_{i,j}$完成时是否进行预防性维护，则：

$$v_{i,j}=\left\{\begin{array}{l}\mathrm{1},N_{i,j}\ge Q_i\\ \mathrm{0},N_{i,j}<Q_i\end{array}\right.$$

变量$s_{i,j}$表示设备$i$在工序$O_{i,j}$完成时的状态，则：

$$s_{i,j}=v_{i,j}+(\mathrm{1}-v_{i,j})[t_{i,j}\cdot \prod _{q_{i,s_{i,j-\mathrm{1}},k}}k+(\mathrm{1}-t_{i,j})\cdot s_{i,j-\mathrm{1}}]$$

该式表示设备进行维护后恢复到全新状态，状态跃迁后到达新状态，新状态为由跃迁概率矩阵决定的随机量， $\prod _{q(k)}k$表示依概率$q(k)$在不同情况下取值$k$，而既不维护也不跃迁时维持原状态。

图2表示在维护在线决策策略下，设备加工过程中设备状态与累计不合格品数随时间的变化，其中时间单位为工序的平均加工时间。显然：较大的阈值会增加设备在高退化状态下运行的风险，降低生产率，而较小的阈值会增加设备在较小退化状态下进行维护的趋势，造成维护资源和生产资源的浪费，因而合理的选择维护阈值是重要的。

图2 设备维护在线决策机制

Fig. 2 Online decision-making strategy of maintenance

2.2　缓冲分配建模

由于加工质量的不确定性，在设备之间设置缓冲区以吸收不确定性。由于缓冲区容量限制，设备在加工过程中会发生饥饿及堵塞。记变量$p_{i,j}$表示工序$O_{i,j}$的加工持续时间，$b_{i,j}$表示工序$O_{i,j}$的加工开始时间，$d_{i,j}$表示工件$j$离开设备$i$的时间。工件在设备上的加工流程如下：

假设设备$i$进行一次维护的时间$T_i^{\mathrm{P}}$，则工序$O_{i,j}$的加工开始时间$b_{i,j}$取决于该工件在上游设备上的离开时间$d_{i-\mathrm{1},j}$和上一个工件在设备$i$上的离开时间$d_{i,j-\mathrm{1}}$：

$$b_{i,j}=\mathrm{m}\mathrm{a}\mathrm{x}\{d_{i-\mathrm{1},j},d_{i,j-\mathrm{1}}+v_{i,j-\mathrm{1}}\cdot T_i^{\mathrm{P}}\}$$

若$d_{i-\mathrm{1},j}>d_{i,j-\mathrm{1}}+v_{i,j-\mathrm{1}}\cdot T_i^{\mathrm{P}}$，则设备$i$需等待上游设备供应工件而闲置，即设备$i$饥饿；若$b_{i-\mathrm{1},j}+p_{i-\mathrm{1},j}<d_{i,j-\mathrm{1}}+v_{i,j-\mathrm{1}}\cdot T_i^{\mathrm{P}}$，则工件$j$将进入缓冲区等待，若无缓冲空间则发生堵塞。若设备$i$的下游未堵塞，则工件$j$加工完成后立即进入缓冲区，否则工件需等待下游设备开始工件$j-X_i$的加工而释放缓冲空间，则工件$j$离开设备$i$的时间$d_{i,j}$为

$$d_{i,j}=\mathrm{m}\mathrm{a}\mathrm{x}\{b_{i,j}+p_{i,j},b_{i+\mathrm{1},j-X_i}\}$$

假设工件在设备$i$上进行返工的时间为$T_i^{\mathrm{R}}$，则工序$O_{i,j}$的加工持续时间取决于工件是否进行返工：

$$p_{i,j}=p_i+r_{i,j}\times T_i^{\mathrm{R}}$$

基于以上产品加工流程，设备的缓冲区库存与其上下游设备的关系如图3所示，图中以每道工序的平均时间为单位时间1，中间区域表示某设备$i$在加工过程中的缓存区库存数量变化，两侧区域表示该设备及其上游设备$i-\mathrm{1}$和下游设备$i+\mathrm{1}$的工作状态，即正常运行（图中空白区域）、维护、饥饿或堵塞。显然在缓冲区有容量限制条件下，上游设备的维护和饥饿会导致下游设备饥饿，而下游设备的维护会导致上游设备堵塞。因而合理地分配缓冲区容量和制定维护策略对于控制在制品以及减少设备的饥饿和堵塞非常重要。

图3 设备停机及缓冲区库存与其上下游设备关系

Fig. 3 Relationship between buffer stock and breakdowns of upstream and downstream machines

因此建立缓冲分配子模型的决策量为$\mathit{X}=\{X_{\mathrm{1}},X_{\mathrm{2}},...,X_M\}$，为由$M-\mathrm{1}$个缓冲分配决策变量构成的矢量，分别表示每台设备后设置的缓冲区大小，由于缓冲区总容量为$B$，则：

$${\displaystyle \sum _{i=\mathrm{1}}^{M-\mathrm{1}}}{X}_i=B$$

2.3　成本建模

本文的目标为最小化生产过程的总成本。总成本包括设备维护成本、在制品库存成本、产品缺货成本以及返工造成的成本。假设$c_i^{\mathrm{P}}$为设备$i$进行一次维护的成本，则加工过程中的维护总成本为

$$C^{\mathrm{P}}={\displaystyle \sum _{i=\mathrm{1}}^M}{\displaystyle \sum _{j=\mathrm{1}}^D}{v}_{i,j}{c}_i^{\mathrm{P}}$$

（6）

假设$c^{\mathrm{S}}$为单位时间内储存一件在制品的成本，则总的加工时间内的库存水平在数值上等于所有工件在所有缓冲区内的停留时间，因而加工过程中的库存总成本为

$$C^{\mathrm{S}}={\displaystyle \sum _{j=\mathrm{1}}^D}{\displaystyle \sum _{i=\mathrm{1}}^{M-\mathrm{1}}}(a_{i+\mathrm{1},j}-d_{i,j})\cdot c^{\mathrm{S}}$$

（7）

假设$c_i^{\mathrm{R}}$为单位工件在设备$i$上进行一次返工的成本，则加工过程中的总返工成本为

$$C^{\mathrm{R}}={\displaystyle \sum _{i=\mathrm{1}}^M}{\displaystyle \sum _{j=\mathrm{1}}^D}{r}_{i,j}{c}_i^{\mathrm{R}}$$

（8）

假设$c^{\mathrm{O}}$为单位产品的缺货成本，则总的缺货成本为

$$C^{\mathrm{O}}=(D-\underset{d_{M,j}\le L}{\mathrm{m}\mathrm{a}\mathrm{x}}j)\cdot c^{\mathrm{O}}$$

（9）

2.4　联合模型

因此建立的随机规划数学模型为

$$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}E(C)=E(C^{\mathrm{P}})+E(C^{\mathrm{S}})+\\ E(C^{\mathrm{R}})+E(C^{\mathrm{O}})\end{array}$$

（10）

$${\displaystyle \sum _{j=\mathrm{1}}^{M-\mathrm{1}}}{X}_j=B$$

（11）

$$s_{i,\mathrm{0}}=\mathrm{1}$$

（12）

$$N_{i,\mathrm{0}}=\mathrm{0}$$

（13）

$$a_{i,\mathrm{0}}=\mathrm{0}$$

（14）

$$r_{i,j}~B(\mathrm{1},u_{i,s_{i,j}})$$

（15）

$$N_{i,j}=N_{i,j-\mathrm{1}}\cdot (\mathrm{1}-v_{i,j-\mathrm{1}})+r_{i,j}$$

（16）

$$v_{i,j}=\left\{\begin{array}{l}\mathrm{1},N_{i,j}\ge Q_i\\ \mathrm{0},N_{i,j}<Q_i\end{array}\right.$$

（17）

$$a_{i,j}=a_{i,j-\mathrm{1}}\cdot (\mathrm{1}-t_{i,j-\mathrm{1}})\cdot (\mathrm{1}-v_{i,j-\mathrm{1}})+p_{i,j}$$

（18）

$$t_{i,j}=\left\{\begin{array}{l}\mathrm{1},a_{i,j}⩾\mathrm{\Delta }t\\ \mathrm{0},a_{i,j}<\mathrm{\Delta }t\end{array}\right.$$

（19）

$$s_{i,j}=v_{i,j}+(\mathrm{1}-v_{i,j})[t_{i,j}\cdot \prod _{q_{i,s_{i,j},k}}k+(\mathrm{1}-t_{i,j})\cdot s_{i,j-\mathrm{1}}]$$

（20）

$$b_{i,j}=\mathrm{m}\mathrm{a}\mathrm{x}\{d_{i-\mathrm{1},j},d_{i,j-\mathrm{1}}+v_{i,j-\mathrm{1}}\cdot T_i^{\mathrm{P}}\}$$

（21）

$$d_{i,j}=\mathrm{m}\mathrm{a}\mathrm{x}\{b_{i,j}+p_{i,j},b_{i+\mathrm{1},j-X_i}\}$$

（22）

$$p_{i,j}=p_i+r_{i,j}\cdot T_i^{\mathrm{R}}$$

（23）

$$Q_i\in N^{+}$$

（24）

$$X_i\in N,\forall i\ne M$$

（25）

式（10）为目标函数，表示包括维护成本、在制品库存成本、返工成本以及缺货成本在内的总成本最小化；式（11）表示缓冲分配约束；式（12）~（14）表示设备状态、累积加工时间以及累计不合格品数的初始化；式（15）定义了工件质量即工件是否进行返工，为由设备状态和工序不合格品率决定的随机量；式（16）定义了累计不合格品数的递推式；式（17）定义了设备在任意工件加工完成时是否进行维护；式（18）为设备上一次维护或跃迁后的累积加工时间的计算式；式（19）表示设备发生状态跃迁的时刻；式（20）为设备状态的计算式；式（21）~（23）表示工件加工流程，即在有限缓冲容量约束下，工件加工开始时间、加工持续时间及离开设备的时间的计算式；式（24）和式（25）定义了决策变量的取值范围。

3 算法设计

由于设备状态跃迁和工件加工质量的随机性，本文目标中的期望总成本无法通过精确表达式推算。另一方面，由于模型的规模以及加工质量的随机性使得模型求解变得复杂，无法使用CPLEX等商业软件进行直接求解。因此，本文首先根据数学模型提出蒙特卡洛仿真的具体算法，通过仿真获得期望总成本的近似值，以替代目标函数中的期望值。鉴于禁忌搜索算法对大规模问题的求解能力以及搜索时间的可行性，采用禁忌搜索算法框架对决策量$\mathit{Q}$和$\mathit{X}$的可行解进行迭代搜索，考虑串联生产线上下游设备的结构关联性，提出带有元胞自动机制的邻域结构优化算法搜索过程。

3.1　基于状态跃迁抽样仿真的成本估计

本文的目标函数为随机量的期望值，无法通过约束及可行解准确计算其目标值，因而通过蒙特卡洛仿真方法获得目标函数的近似值。根据第2节的数学模型，在确定的系统参数、缓冲分配及预防性维护阈值情况下，通过蒙特卡洛仿真方法得到系统的总成本$C$。

为保证结果的有效性，需要确定抽样仿真的次数。对抽样仿真的次数进行置信度分析，记生产总成本的置信区间为：$I=\overline{X}\pm t_{n-\mathrm{1},\alpha /\mathrm{2}}\cdot \frac{S}{\sqrt[]{n}}$，其中，$\overline{X}$表示样本均值，$S$为样本标准差，$n$为抽样仿真次数，$t_{n-\mathrm{1},\alpha /\mathrm{2}}$表示自由度为$n-\mathrm{1}$，显著水平为$\alpha /\mathrm{2}$的$t$分布值。取$\alpha =\mathrm{0.02}$，即置信水平为98 %。图4表示总成本的累积均值以及其上下偏差随抽样仿真次数变化的图，在抽样仿真次数为80次时偏差已控制在2 %以内，因而取抽样仿真次数为80次。

图4 累积均值及上下偏差随仿真重复次数变化

Fig. 4 Cumulative mean, and upper and lower deviation with replications of simulation

3.2　禁忌搜索算法

禁忌搜索算法对大规模问题的求解能力及搜索时间的可行性适合本文模型的求解，采用维护阈值列表和缓冲分配列表的双列表编码方案（图5），设计初始化程序以调高初始解质量且保证充分的搜索空间，同时设计适合本问题的邻域搜索算子即元胞自动机制邻域结构以提高算法的速度和精度。

图5 禁忌搜索编码方案示意图

Fig. 5 Coding example of tabu search algorithm

3.2.1　编码方案

维护阈值列表$\mathrm{Q}\mathrm{L}=\{Q_{\mathrm{1}},Q_{\mathrm{2}},...,Q_M\}$，采用与阈值决策矢量相应的长度为$M$（设备台数）的实值编码，第$i$个位置的值$Q_i$表示设备$i$在累计不合格品数为$Q_i$时进行预防性维护。缓冲分配列表$\mathrm{B}\mathrm{L}=\{x_{\mathrm{1}},x_{\mathrm{2}},...,x_{M+X}\}$，采用0/1二进制编码，$x_l=\mathrm{1}$表示第${\displaystyle \sum _{k=\mathrm{1}}^l}{x}_k$台设备，任意两台设备间的0值个数表示设备间分配的缓冲容量。该编码方案有如下约束：$x_{\mathrm{1}}=x_{M+X}=\mathrm{1}$；${\displaystyle \sum _{l=\mathrm{1}}^{M+X}}{x}_l=M$。

3.2.2　初始解

对于缓冲分配列表$\mathrm{B}\mathrm{L}$，其初始解采用均匀分配策略生成。对于维护阈值列表$\mathrm{Q}\mathrm{L}$，由于邻域产生方式总体为增加式迭代，故将初始值设定为较小值，即： $Q_i~U(T_i^{\mathrm{P}}/(\mathrm{2}{T}_i^{\mathrm{R}}),T_i^{\mathrm{P}}/T_i^{\mathrm{R}})$。

3.2.3　邻域结构

对于缓冲分配列表$\mathrm{B}\mathrm{L}$采用随机交叉的方式产生其邻域，随机选择交叉位置$k\in [\mathrm{2},M+X-\mathrm{2}]$且$x_k\ne x_{k+\mathrm{1}}$，其邻域$\mathrm{B}{\mathrm{L}}^{\mathrm{N}\mathrm{E}\mathrm{W}}=\{x_{\mathrm{1}},x_{\mathrm{2}},...,x_{k+\mathrm{1}},x_k,...,x_{M+X}\}$，显然该种邻域产生方式不打破编码约束。

对于维护阈值列表$\mathrm{Q}\mathrm{L}$，考虑到串联生产系统上下游设备的结构关联性，借鉴元胞自动机（cellular automatan， CA）原理，引入元胞自动机制邻域结构。将$\mathrm{Q}\mathrm{L}$的每个元素$Q_i$视为一个元胞，定义其左侧和右侧的各$r$（称邻元半径）个元素集合为其邻元$Q_{ir}$，如图5元胞的更新依赖于该元胞及其邻元的值以及设定的更新规则，更新规则$Q_i^{\mathrm{*}}=f(Q_i,Q_{ir})$为

$$Q_i^{\mathrm{*}}=Q_i+\rho ·(\mathrm{m}\mathrm{a}\mathrm{x}{Q}_{ir}-\mathrm{m}\mathrm{i}\mathrm{n}{Q}_{ir})+(\mathrm{1}-\rho )z$$

（26）

式中：$\rho$和$z$为随机量，$\rho ~U(\mathrm{0},{\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}})$，$z~N(\mathrm{0},\sigma )$。第一项$\rho ·(\mathrm{m}\mathrm{a}\mathrm{x}{Q}_{ir}-\mathrm{m}\mathrm{i}\mathrm{n}{Q}_{ir})$保证邻域搜索的速度，第二项$(\mathrm{1}-\rho )z$保证邻域搜索的精度。为解决在算法迭代后期不易收敛的问题，令${\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{1}-{y/Y}_{\mathrm{1}}$，$y$表示算法当前迭代次数，$Y_{\mathrm{1}}$表示算法最大迭代次数。随机选择更新位置$k\in [\mathrm{1},M]$，其邻域$\mathrm{Q}{\mathrm{L}}^{\mathrm{N}\mathrm{E}\mathrm{W}}=\{Q_{\mathrm{1}},Q_{\mathrm{2}},...,Q_k^{\mathrm{*}},...,Q_M\}$。该种邻域生成方式有两个经验取值：邻元半径$r$及正态分布的标准差$\sigma$。因而，在一次更新中的邻域结构为$(\mathrm{Q}{\mathrm{L}}^{\mathrm{N}\mathrm{E}\mathrm{W}},\mathrm{B}\mathrm{L})$或$(\mathrm{Q}\mathrm{L},\mathrm{B}{\mathrm{L}}^{\mathrm{N}\mathrm{E}\mathrm{W}})$。

3.2.4　禁忌及终止准则

为避免重复搜索，采用如下禁忌规则：对于$\mathrm{B}\mathrm{L}$，将搜索过的位置加入禁忌列表$\mathrm{T}{\mathrm{L}}^{\mathrm{B}\mathrm{L}}$，对于$\mathrm{Q}\mathrm{L}$，将搜索过且无改进的位置加入禁忌列表$\mathrm{T}{\mathrm{L}}^{\mathrm{Q}\mathrm{L}}$，当列表达超过列表长度上限后，采用先进先出的规则将最先加入列表的位置元素移除列表。当算法达到最大迭代次数$Y_{\mathrm{1}}$或最大连续无改进次数$Y_{\mathrm{2}}$时，结束迭代，算法流程图如图6所示。

图6 禁忌搜索算法流程图

Fig. 6 Flowchart of Tabu search algorithm

4 算例分析

现有研究大多单独研究维护优化问题、或是计划维护与缓冲分配优化问题，针对马尔科夫退化系统，还没有在线维护策略与缓冲分配联合优化的研究，下面通过与其他维护策略或是单独优化策略的对比验证本文模型的有效性。

记本文的联合优化模型为P0，与现有研究中广泛使用的三种不同策略对比：P1，采用等周期预防性维护策略，设备按照维护周期同时进行维护，Moghaddam等^［12］采用该种维护策略，缓冲采用均匀分配策略，这是因为对于均衡生产线，缓冲容量均匀分配为最佳策略^［13］，决策量即维护周期采用禁忌搜索算法求解；P2，基于役龄的预防性维护，陆志强等^［14］采用该种维护策略，缓冲均匀分配策略，决策量即执行预防性维护的役龄阈值采用禁忌搜索算法求解；P3，基于役龄的维护计划和缓冲联合优化策略，王林等^［10］采用该种策略，采用禁忌搜索算法求解。

4.1　基本算例分析

假设一串行系统由4台设备3个缓冲区组成，需完成数量为$D=\mathrm{2}\mathrm{000}$的加工任务，最大加工时间$L=\mathrm{3}\mathrm{000}$，缓冲区总容量为$\mathrm{10}\times \mathrm{3}$，产品在每台设备上的加工时间均为单位时间$p_i=\mathrm{1}$，所有设备上的单位返工时间均为$T_i^{\mathrm{R}}=\mathrm{1}$，所有设备的维护时间均为$T_i^{\mathrm{P}}=\mathrm{20}$元。单位存储成本$c^{\mathrm{S}}=\mathrm{0.015}$元，单位缺货成本$c^{\mathrm{O}}=\mathrm{4}$元，所有设备上的单位返工成本均为$c_i^{\mathrm{R}}=\mathrm{1}$元，所有设备的维护成本均为$c_i^{\mathrm{P}}=\mathrm{30}$元。

禁忌搜索算法最大允许迭代次数为100，最大允许连续无改进次数为8，现讨论经验取值$(r,\sigma )$对算法迭代过程的影响，$r$分别取0（对照组）、1、2，$\sigma$分别取5、10、20，最优目标值随迭代次数变化的曲线如图7所示（$r=\mathrm{0}$时取$\sigma$中最优曲线绘制）。曲线表明，元胞自动机制邻域结构明显优于一般搜索策略，$(r,\sigma )=(\mathrm{1,10})$时优化效果较好，这是因为$r=\mathrm{1}$充分利用上下游设备间的关联性，使得每台设备上下游间生产过程的局部平衡，而$\sigma$较小时算法搜索速度慢不易跳出局部最优解，$\sigma$较大时算法搜索速度快但容易在最优解附近产生震荡而不易收敛，$\sigma =\mathrm{10}$可以较好平衡算法收敛速度、提高收敛精度，搜索到更优目标值，因而参数取值$(\mathrm{1,10})$。

图7 不同$(r,\sigma )$下最优目标值随迭代次数变化图

Fig. 7 Diagram of optimum value and iteration at different values of $(r,\sigma )$

如图8所示，本文的维护在线决策与缓冲分配联合优化模型的总成本为2 034.4元，而等周期预防性维护与缓冲均匀分配策略的总成本为2 304.4元，基于役龄的预防性维护与缓冲均匀分配策略下的总成本为2 291.4元，基于役龄的预防性维护与缓冲优化策略下的总成本为 2 240.0元。可以看出，本文的维护在线决策与缓冲联合优化模型明显优于一般维护策略和单独优化模型，与单独优化策略（P1和P2）相比最低优化比例为11.2 %，与维护计划与缓冲分配联合优化策略（P3）相比优化比例达到9.18 %。

图8 不同策略下的总成本构成

Fig. 8 Component of total cost of different strategies

从不同策略下优化结果的总成本的构成来看，维护在线决策与缓冲联合优化模型主要通过降低返工成本实现降低总成本，对比模型中等周期预防性维护的返工成本最高、总成本也最高，基于役龄的维护计划次之。本文的联合优化模型有效地权衡了维护与质量，实现总成本的优化。

4.2　大规模算例分析

为验证不同参数下模型的性能，改变设备数量（$M$）、需求量（$D$）和缓冲区总容量（$B$）进行试验。数值实验的部分结果如表1所示，对比模型P的优化比例（$G_{\mathrm{a}\mathrm{p}}$）计算为

$$G_{\mathrm{a}\mathrm{p}}(\mathrm{P})=\frac{C_{\mathrm{P}}-C_{\mathrm{P}\mathrm{0}}}{C_{\mathrm{P}}}\times \mathrm{100}\mathrm{\%}$$

（27）

式中：$C_{\mathrm{P}}$为策略P下生产系统的总成本。从表中可以看出本文模型和算法即P0总是优于对比策略，与单独优化策略（P1和P2）相比最大优化比例为15.15 %，最小优化比例为5.53 %，平均节约成本10.09 %，与计划维护与缓冲联合优化策略（P3）相比，最大优化比例为11.32 %，最小优化比例为4.41 %，平均节约成本6.64 %。

表1 不同数据规模下本文模型与对比模型成本比较

Tab.1 Cost comparison of proposed method and compared ones at different data scales

$B$	策略	$M\times D,L=1.5D$
		$4\times 2000$		$8\times 2000$		$12\times 2000$
		$C_{\mathrm{P}}$/元	$G_{\mathrm{a}\mathrm{p}}(\mathrm{P})$/%	$C_{\mathrm{P}}$/元	$G_{\mathrm{a}\mathrm{p}}(\mathrm{P})$/%	$C_{\mathrm{P}}$/元	$G_{\mathrm{a}\mathrm{p}}(\mathrm{P})$/%
$5(M-1)$	P0	2 107.7		3 414.8		4 964.8
	P1	2 360.3	10.70	3 979.3	14.18	5 513.8	9.96
	P2	2 333.6	9.68	3 871.9	11.80	5 342.6	7.07
	P3	2 244.9	6.11	3 771.1	9.45	5 310.8	6.52
$10(M-1)$	P0	2 034.4		3 309.0		4 986.1
	P1	2 304.4	11.72	3 818.0	13.33	5 424.4	8.08
	P2	2 291.4	11.22	3 635.1	8.97	5 298.6	5.90
	P3	2 240.0	9.18	3 583.4	7.66	5 231.6	4.69
$15(M-1)$	P0	1 946.0		3 245.0		4 938.7
	P1	2 293.5	15.15	3 762.8	13.76	5 438.9	9.20
	P2	2 276.3	14.51	3 594.7	9.73	5 227.6	5.53
	P3	2 194.3	11.32	3 541.3	8.37	5 166.8	4.41
$20(M-1)$	P0	2 026.1		3 295.8		4 987.9
	P1	2 261.7	10.42	3 711.8	11.22	5 593.1	10.82
	P2	2 382.0	14.94	3 597.6	8.41	5 309.4	6.06
	P3	2 208.5	8.26	3 501.3	5.89	5 221.3	4.47

随机选取缓冲总容量为$\mathrm{10}(M-\mathrm{1})$时绘制不同策略下总成本随设备数变化如图9a所示，在设备数小于10时总成本近似呈线性增长，继续增加设备数总成本增长加快，这是由于设备数持续增多，产出率下降导致产品缺货而产生较大的缺货成本。随机选取设备数为8绘制不同策略下总成本随缓冲区总容量变化如图9b所示，适当增加缓冲可以有效减少设备因上下游设备停机而停机，增加生产率降低缺货成本，但缓冲区容量过大时总成本有上升趋势，这是因为缓冲区容量过大时产生较大的储存成本。总而言之，不同的设备数及缓冲容量下，维护在线决策与缓冲联合优化策略总是优于其他策略。

图9 不同策略下不同参数与总成本的关系图

Fig.9 Diagram of parameters and total cost of different strategies

5 结束语

本文研究了串联生产系统维护、质量控制与缓冲分配的联合优化问题：

（1）针对串联生产系统的设备退化引起的不合格品因素，联合设备维护与质量控制提出设备维护在线决策策略，充分利用设备加工过程中的实时信息，减少设备提前或延后维护的风险；分析了设备在有限缓冲容量和加工质量不确定下的加工过程，建立了设备维护、质量控制与缓冲分配的联合优化模型。

（2）针对联合优化模型提出基于蒙特卡洛仿真的成本估计算法，采用禁忌搜索算法对维护策略的不合格品阈值和缓冲配置进行迭代搜索，为充分利用上下游设备的结构关联性，提出元胞自动机制邻域结构优化搜索过程。

（3）数值实验结果表明，本文提出的模型及算法与单独优化策略相比平均节约10 %以上总成本，与现有的联合优化策略相比平均节省6 %以上总成本。从成本构成来看，在线维护策略极大地减少了质量损失成本，证明了在不同设备数和缓冲区总容量条件下，在线维护策略、质量控制与缓冲分配联合优化方法的有效性。

（4）本文的质量检查结果为工件是否合格，未来研究中可以考虑具体的质量特性指标及其在串行生产线上的传递性。

作者贡献声明

陆志强：提出研究选题，设计研究思路和论文框架；

张之磊：设计研究思路，实施研究过程，负责进行试验，起草论文及撰写。