关于时间非均匀性不可靠服务系统的最优策略 颜苏、 刘家文、 钟然

《Mathematics》：On the Optimal Policies of Time-Inhomogeneous Unreliable Service Systems Yan Su, Jiawen Liu and Ran Zhong

　　摘要 本文研究了具有多个客户来源和不同维护速度的时间非均匀不可靠多服务器排队系统的最优动态策略。在全球收入最优性的标准下，我们首先阐明了偏差最优策略的存在性，并严格证明了最优时间非均匀多阈值策略的存在性。进一步推导了两个充分条件来解决最优时间非均匀多阈值策略的单调性问题。最后，为了降低在全球优化目标下推导最优策略的计算复杂性，我们提出了一个基于上述理论结果的启发式算法。数值示例不仅证明了所提算法的强大性能，还表明当预设阈值根据客户类型区分时，生产损失成本相对于服务状态的单调性假设不再成立。

1. 引言
随机服务系统的动态优化一直是排队理论的核心研究分支。与静态优化相比，随机服务系统的动态优化提供了更高的灵活性。然而，其参数设置的复杂性意味着许多优化问题未能达到理想的研究结果，这也使得这一方向更具挑战性。在实际应用中，异质客户群体变得越来越突出，特别是在资源有限的收入管理问题中。例如，在时间受限的定制生产场景中，客户对企业有不同的要求，这对应于运营商不同的利润水平。服务设施的不可靠性是随机服务系统研究中经常考虑的另一个因素，以适应现实世界的需求。例如，在定制生产中，企业经常面临由于设备维护导致的生产中断，从而失去大量潜在客户并减少企业利润。在定制生产的背景下，本文结合了异质客户来源和多设备不可靠性来研究时间非均匀随机服务系统的动态优化问题。为此，下一部分首先简要回顾了现有的相关研究进展。

已经对各种类型的排队系统的高知名度优化问题进行了大量研究，例如[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]，其中[1,4,5,6,8,9,13,19,20]专门研究了这些系统的动态优化。一些研究[6,8,9,11,13,19,20]探讨了异质客户群体，[6,8,13]通过定价机制区分了不同类型的客户。参考文献[5]以预期折现奖励作为优化目标进行分析，而[1,4,6,8,9,19]则关注长期预期平均标准。算法设计和性能改进也是与这一研究方向相关的研究重点。参考文献[4,8,19]分别提出了针对所研究随机服务系统的相应高性能算法，而[10,12]提出了近似算法，以确保在有限时间内可计算性或提高算法效率。

在基于排队的生产过程中，由于生产设备的不可靠性，实践中经常发生部分或全部生产中断。在生产过程中，生产设备通常会经历周期性的故障和维护。由具有上述特征的服务器组成的排队系统通常被称为可维修排队系统。可维修排队系统引起了学者的广泛关注，并有大量文献从不同角度分析了这些系统，例如[4,9,10,12,16,17]。然而，整合了异质客户群体和多设备不可靠性的时间非均匀随机服务系统的动态优化问题在现有研究中尚未得到解决。本研究主要将先前研究[9]中提出的单服务器模型扩展到多服务器场景，并将原来的单一维护模式进一步推广到满足预设条件的各种合格维护模式。本文的具体贡献总结如下：
我们在时间非均匀模型下构建了最优性方程，从中推导出了偏差最优策略的几个性质，并证明了最优时间非均匀多阈值策略的存在性。
对于最优时间非均匀多阈值策略的单调性问题，我们提出了两个充分条件并完成了相应的证明。
当设备维护有多种选择时，为了降低算法的计算复杂性，我们基于上述结论提出了一个启发式算法。数值示例不仅证明了所提算法的强大性能，还表明当预设阈值根据客户类型区分时，生产损失成本相对于服务状态的单调性假设（见Crabill [4]）不再成立。

本文的其余部分组织如下。第2节介绍了时间非均匀模型的所有参数以及相应的目标函数。第3节基于最优性方程推导了最优策略的几个性质，并解决了最优时间非均匀多阈值策略的存在性问题。第4节介绍了所提出的启发式算法，并通过数值示例评估了其有效性。我们核心结构结果的证明被推迟到第5节。

2. 建模
考虑一个时间非均匀排队系统，其在时间x的容量表示为。所有潜在到达的客户被分为j类，类别j的客户对系统的贡献值表示为，其中我们不失一般性地假设。类别j的客户在时间x的到达遵循参数为的泊松过程。系统完成一个客户服务的预期成本为。为了保证正利润，我们假设成立。
我们假设所有设备的故障和维护过程与到达和服务过程独立，并遵循有限状态马尔可夫过程。其生成矩阵的非零元素由给出，其中对于，所有状态都是不可约的。这里表示异常运行的设备单元数量。因此，表示所有设备都正常运行。让表示当 units 的设备同时进行维护时的维护成本率。
我们在一般服务率框架下考虑这个问题。设系统在时间x时有i个客户的 ???率为。我们假设：，，，，和。上述假设显然适用于多个相同设备单元共同提供服务的场景。此外，我们假设上述所有时变参数都是有界且可测量的，并且存在，使得所有参数在时保持不变。为了符号简便，我们定义：，，，和。
当类别j的客户到达系统请求服务时，如果客户被接受，系统将获得净奖励；如果服务被拒绝，客户将永久离开系统。我们研究的主要目标是推导出使系统总收入最大化的最优策略。
我们使用定义的参数系统地将上述过程描述为一个马尔可夫决策过程（MDP）。设，然后可以将其视为泊松过程的事件发生率。设表示第m次事件的发生时间。由于过程是时间非均匀的，系统状态可以用一个四维向量来表示，该向量包含时间维度，我们可以使用来表示集合，其中：
-i 表示系统中的客户数量；
-j 表示客户行为：表示类别j的客户到达，表示客户已完成服务，表示没有客户行为发生；
表示事件发生后的故障设备单元数量；
在状态下的动作空间由给出，其中1表示接受客户服务，0表示拒绝客户，表示客户已完成服务。
因此，从状态到任何可测量集合的转移核（转移概率）在采取动作s后为（1），其中，，均匀和非均匀转移概率分别为
设表示第k个决策时期，在状态下采取的动作，其中f是从系统状态到动作空间的映射。在初始状态和策略f下，长期平均净奖励定义为，并且其最优值由给出，其中D表示所有可接受策略f的集合。如果，f被定义为一个最优策略，并表示所有最优策略的集合。
策略f的偏差定义为（2），最优偏差值为。如果策略f满足上述方程，则它是偏差最优的。

3. 主要结果
3.1. 最优策略的性质
将转移核（1）代入动态规划最优性方程，我们得到以下公式：
（3）
其中，非均匀和均匀段的转移公式分别由（4）和（5）给出。
基于上述定义的最优性方程，我们构建了价值迭代序列如下：
当：（6）
当：（7）
其中对于（8）
对于（9）
设和。在此基础上，我们推导出以下引理。详细证明见第5节。
引理1. （a）和；（b）对于，和相对于i是递减的；（c）如果对于固定的x，是一个随机单调矩阵，和相对于ν是递减的。
根据价值迭代算法的收敛性质，我们有随着。因此，当没有歧义时，我们可以省略和中的上标f，可以直接得出以下结论。
引理2. （a）和；（b）对于，和相对于i是递减的；（c）如果对于固定的x，是一个随机单调矩阵，和相对于ν是递减的。
注释1. 随机单调性具有重要的实际意义。尽管在不同维护策略下设备的转移结构不同，它们都满足随机单调性属性，这赋予了本研究结论的普遍适用性。典型的例子包括生死过程、随机游走和其他相关随机过程。我们在下面给出几个例子来证明常用的维护策略满足随机单调性属性。
（a）考虑在状态空间上定义的维护过程，其生成器为无穷小：
这个生成器对应于一个有限状态的生死过程，已知是随机单调的。特别是当，简单的可维修排队在运行和故障周期之间交替也满足随机单调性。
（b）考虑在状态空间上定义的批量可维修过程，其生成器为无穷小：
经过均匀化后，这个生成器与具有递减故障率的年龄更新过程的结构相匹配，因此是随机单调的。
（c）考虑在状态空间上定义的单次向下转移（分支型过程）的维护过程，其生成器为无穷小：
经过均匀化后，这个过程满足随机单调性。
接下来我们建立两个引理：一个为提供了上限，另一个分析了在均匀情况下从最优性方程导出的结构性质。这两个引理为后续部分中提出的关键结论奠定了重要基础。所有详细证明见第5节。
引理3. 对于任何满足前述动态最优性方程和任意i、ν、x的策略f，我们有。
引理4. 设表示在f下的所有复发状态的集合；那么以下陈述成立：
（a）对于任何，。
（b）的一个必要条件是方程（3）成立。
（c）存在i和ν，使得。
现在我们提出一个关键结论，这涉及时间非均匀阈值的定义，所以我们首先描述时间非均匀阈值。详细证明见第5节。
定义1. 如果对于f，存在一个函数，使得对于任何ν和x，只有当队列长度小于时才会接受相应类型的客户的服务，那么f被定义为一个时间非均匀多阈值策略。
定理1. 在当前的随机服务系统中，如果在固定时间内服务过程的变化是随机单调的，则存在满足最优性方程的f，并且同时满足以下陈述：
（a）对于任何，
（b），
（c）；
（d）如果对于任何j和ν，成立，则f是一个偏差最优策略。

3.2. 单调性
在本小节中，我们研究了时间非均匀阈值相对于x的单调性。这项工作有助于分析时变参数如何影响最优调节的方向，这在实际中具有重要意义。
定理2. 在当前的随机服务系统中，假设f是一个时间非均匀多阈值偏差最优策略，那么以下结论成立：如果满足以下条件，则对于所有的x，函数f是非递减的：g是关于x非递增的；h和i也都是关于x非递减的；当满足某个条件时，j关于x是非递增的；当满足另一个条件时，j关于x也是非递减的。2. 如果满足以下条件，则对于所有的x，函数f是非递增的：g是关于x非递减的；h和i也都是关于x非递增的；k是一个常数；当满足某个条件时，j关于x是非递增的；当满足另一个条件时，j关于x也是非递减的。证明见第5节。□ 4. 算法与数值实验 4.1. 离散化近似 当系统参数需要很长时间才能达到稳态时，即当X的值足够大时，系统的时间非均匀部分在全球分析中起着关键作用。从第2节的系统状态表达式中可以看出，由于时间变量x是不可数的，因此不可能直接推导出在所有状态下的策略。我们采用了一种广泛使用的离散化方法来进行近似：将整个区间均匀划分为多个子区间。在实际应用中，对于参数波动较大的区域进行更细的离散化可以获得更高的精度，但也会相应增加计算成本。随着参数值的增加，误差会单调减小并逐渐收敛。设x1 < x2 < ... < xn，其中xi < xn。对于每个子区间内的系统参数，我们将参数值设为常数，并取该区间左边界处的值；即xi = ci，其中c是一个常数。因此，方程(4)可以重新表述为...（此处省略了具体的数学表达式）。通过应用类似于方程(6)、(7)和(9)的方法来处理上述方程，我们可以定义值迭代序列...（此处省略了具体的计算过程）。因此，根据引理1和定理1的结论，我们可以有效地计算出时间非均匀的多阈值最优策略。4.2. 启发式值迭代算法 在设备维护领域，动态选择多个维护效率水平中的最优策略是一个有意义的研究问题。当系统面临多个维护效率水平的选择时，穷举搜索方法将导致计算复杂度的指数级增长。在本小节中，我们提出了一种基于经典文献研究结论的分析的高效近似解决算法。首先，我们调整第2节中描述的模型参数，以便更好地描述本小节的问题。设b表示维护效率水平的类型：b的值越大，维护速率越快，成本率也越高。相应地，我们将固定的维护成本率和转换率修改为更快的服务率...（此处省略了具体的数值）。由于维护策略仅依赖于设备的当前状态，因此修改后的模型对应于部分可观测的马尔可夫决策过程。当行动空间较大时，解决客户分配和设备维护的联合优化问题在计算上非常昂贵。因此，我们采用经典的单调维护策略来降低计算复杂度。改进后的算法1如下：算法1：改进算法 1. 设置一个初始值x0。2. 选择一个新的单调维护策略并设置新的参数值。如果没有更多的单调维护策略可用，则跳转到步骤6。3. 根据方程(6)、(7)、(9)以及引理1和定理1的结论，计算...（此处省略了具体的计算过程）。4. 如果满足某个条件，则继续执行步骤5；否则，返回步骤3。5. 按照以下方法计算近似最优的多阈值策略：...（此处省略了具体的计算过程）。6. 比较每次迭代获得的所有最优净收入的值，并输出最优策略。4.3. 数值实验 在本小节中，我们测试了所提出算法在备注1中描述的三种不同维护模式下的性能。我们固定了几个基本参数...（此处省略了具体的参数值）。对应于上述三种结构的参数描述如下：（生死结构）退化转移率为λ，维护转移率为μ1、μ2和μ3。（批量维护结构）退化转移率为λ，维护转移率为μ4、μ5、μ6和μ7，其中...（此处省略了具体的参数值）。（分支结构）退化转移率对于所有状态都满足某个条件，维护转移率为μ8、μ9和μ10。我们在表1中列出了全局最优策略和单调维护策略下的均匀最优净收入。结果表明，单调启发式算法在所有结构中的表现都接近最优：平均最优性差距小于1%，并且在70%的测试案例中恢复了全局最优策略。对于分支结构，单调启发式算法始终是最优的。然而，实证性能结果表明，启发式算法在计算效率上有了显著的改进。一个合理的解释是：在维护速率选择问题上，从算法流程可以看出，搜索步骤从原来的指数阶变成了阶乘阶。为了增强我们结论的稳健性，并考虑时间非均匀情况，我们进一步分析了到达率和服务率变化对目标策略的影响，以及它们对计算效率的影响（使用表1中的第一组成本数据）。结果表明，启发式算法仍然能够提供令人满意的结果，其输出与最优解非常接近；此外，图1和图2的结果也证实了启发式算法的高效性（A1、A2和A3表示迭代算法，H1、H2和H3表示启发式算法）。图1：最优策略的运行时间与...的关系。图2：最优策略的运行时间与...的关系。使用第一组数据集，我们还在图3和图4中分别指定了其他参数，并使用算法1研究了最优阈值随x的变化情况。从图3可以看出，随着x的增长，阈值减小，这是由于μ与x的单调递增性质。相比之下，在图4中，随着x的增长，阈值增大，因为μ也随x单调递增。上述数值示例的所有结果都与定理2中得出的理论结论一致。图3：μ和μ与x的关系。图4：μ'和μ''与x的关系。我们注意到，虽然最优准入阈值μ在x上非递增，但在给定服务状态的条件下，条件期望的平均奖励并不总是非递增的。这表明Crabill [4]的经典结果中关于损失生产成本的单调性假设在有多个客户类别的系统中可能不成立，解释了为什么单调维护策略并不总是全局最优的。确定单调维护策略在何种条件下全局最优仍然是未来研究的一个有趣方向。5. 主要结果的证明 本节提供了引理1-4和定理1、2的证明。引理1的证明。我们通过归纳法证明部分(a)和(b)，然后再证明部分(c)。(a)和(b)。基本情况显然成立（根据定义6）。假设对于每次迭代，(a)和(b)都成立。对于某个状态i，定义A为在队列长度i时准入最优的客户类别集合，即A_i；定义B为在队列长度i时拒绝最优的客户类别集合，即B_i。定义C为在i和j时都可接受的类别集合（对于所有的j）。集合A、B及其高阶交集的定义类似。根据归纳假设，C在i上是非递减的，所以A?B（即一个类别在i时不可接受但在j时可接受）。对于任意的i和j，将其代入(7)得到...（此处省略了具体的数学表达式），从而推出对于所有的i，C?B。取队列长度之间的差值，得到...（此处省略了具体的数学表达式）。对于某些j，...（此处省略了具体的数学表达式）。根据归纳假设，右侧的所有项都是非负的，所以C在i上是非递减的。对于某个j，这一结果直接来自(7)。将边际差值代入(8)和(9)，对于...我们得到...（此处省略了具体的数学表达式），对于...我们得到...（此处省略了具体的数学表达式）。根据归纳假设，右侧的所有项都是非负的，所以对于所有的j，C在i上是非递减的。由此得到对于某个j的结果。将边际差值代入(8)和(9)，对于...我们得到...（此处省略了具体的数学表达式）。根据凹服务率的假设，...。根据归纳假设，所有项都是非负的，所以C在i上是非递减的，从而完成了归纳步骤。(c)基本情况显然成立。假设对于每次迭代，(c)都成立。根据归纳假设，...（此处省略了具体的数学表达式），所以对于某个j，A?B。将其代入(11)得到...（此处省略了具体的数学表达式）。对于第三种情况，注意到...由于...意味着...，并且...意味着...。根据归纳假设，所有其他项都是非负的，所以...。由于对于固定的x，f是随机单调的，因此均匀化的转移矩阵保持了单调性。将(13)中的差值在不同服务状态之间取差并重新排列项，得到...（此处省略了具体的数学表达式）。在凹服务率的假设下，...。根据归纳假设，所有项都是非负的，所以对于某个j，C在i上是非递减的，从而完成了归纳步骤。□引理3的证明。我们首先证明对于某个特定情况的结果，然后通过归纳法扩展到时间非均匀的情况。设f满足动态最优性方程(3)，即只有当...时才允许客户进入。假设相反情况成立，即存在某个状态j使得f不是最优的。根据引理2，f在i和j上是非递减的，所以对于所有的i和j，所有客户都被拒绝，即使系统没有达到满载。我们使用样本路径耦合论证来证明这种策略不可能是最优的。定义一个修改后的策略g，它在状态j时允许类型1的客户进入，其他情况下与f相同。设过程1（P1）遵循策略f，过程2（P2）遵循策略g，它们在相同的概率空间上定义，具有相同的到达、服务和服务容量转移过程。当状态为j时，这两个过程是耦合的：在第一次访问这个状态时，P2接受客户并获得奖励，而P1拒绝客户并获得0。由于准入阈值的单调性，P1接受的任何客户也被P2接受，因此P2的队列长度总是至少与P1的队列长度相同，最大差异为1个客户。如果P2完成一次服务，P1也在同一时间完成服务，因此队列长度差异得以保持。如果服务容量发生变化，两个过程产生的维护成本也相同。当过程第一次返回状态j时，P2的累积奖励严格高于P1。由于f是正循环的，因此f的长期平均奖励严格高于f，这与f的最优性相矛盾。因此，对于所有的i和j，g都不可能是最优的。我们通过对值迭代计数器k进行归纳来继续证明。基本情况显然成立（根据(6)。假设对于所有的i和j，...（此处省略了具体的数学表达式）。根据(11)，对于所有的i和j，...（此处省略了具体的数学表达式）。从这个等式减去(13)，得到...（此处省略了具体的数学表达式）。根据归纳假设，右侧的所有项都是非负的，所以对于所有的i和j，...（此处省略了具体的数学表达式）。随着...的取极限，我们得到...□引理4的证明。(a) 对于任何i和j，如果...，则存在某些k和l使得对于所有的j，...（此处省略了具体的数学表达式）。但是在循环类别下，存在一个满足(3)的策略，其平均奖励相同，这与引理3矛盾（类型1的客户必须在系统未满载时被接受）。因此，...。(b) 假设存在某个状态j使得最优性方程(3)不成立。那么存在一个满足(3)的策略f，使得...（此处省略了具体的数学表达式）。由于对于所有最优策略，...（根据Puterman [21]中的命题8.6.1），f不可能是最优的，这是一个矛盾。因此，对于所有的i和j，(3)成立。(c) 从(3)可以看出，对于某些i和j，如果...，那么...；否则...。结合这个等式得到...（此处省略了具体的数学表达式）。根据惯例，我们设……将（5）中的替换为……得到（19）。再假设对于所有的……都有（20）。如果相反地假设对于所有的……都有……，那么（19）和（20）将导致矛盾，这与正 arrival 奖励的假设相矛盾。因此，对于至少存在一个……，必须有……。□

定理1的证明：为了证明定理1，我们首先为满足条件（3）的策略建立辅助结果。对于任何……，用……表示具有组成部分……的决策后状态的稳态分布，用……表示具有组成部分……的决策前状态的稳态分布，用……表示决策前偏差向量，用……表示决策后价值函数向量。根据稳态流量平衡，结合……和……的定义，我们得到……。注意……。将……代入平衡恒等式中，可以得到……（21）直接由引理2和3得出（a）–（d），因此我们省略了细节。我们关注偏差最优性结果。注意到对于所有满足条件（3）的……，都有……。对于任何一对满足条件（3）的策略……，我们可以构造第三种策略……，除了在单个状态……之外，它在其他地方都与……相匹配。因此，最优的非均匀多阈值策略集合满足条件（3），其中上确界策略……对于所有的……都由……定义。

现在我们证明这个上确界策略d是偏差最优的。对于任何具有……的……，决策后的价值函数满足对于某个常数C……。由于维护转换与接纳决策无关，服务状态的稳态分布在所有策略中是相同的：对于所有的……。将……代入（21）得到……（22）结合（21）得到……（23）我们使用样本路径耦合论证来比较d和f的稳态分布。让过程1（P1）遵循策略d，过程2（P2）遵循策略f，在具有相同到达、服务和维护过程的同一概率空间上。由于d的接纳阈值高于f，P1的队列长度始终至少等于P2的队列长度。因此，P1的稳态分布随机地大于P2的稳态分布：对于所有的……。部分和……关于z是非递减的（根据引理2），并且根据引理4(c)至少对一个z是严格递增的。根据随机排序的定义，在随机更大的分布下，非递减函数的期望值更高，所以将……代入（23）得到……，因此对于所有的……都有……。因此，d是唯一的偏差最优策略，它对应于阈值规则。□

定理2的证明：我们证明（a）；（b）通过对称性论证得出。根据定理1，如果……关于x是非递增的，那么接纳阈值对于……关于x是非递减的。因此只需证明对于所有的k，……关于x是非递增的。基础情况显然成立，因为对于……都有……。对（13）关于x求导得到……（24）利用稳态流程平衡恒等式，我们可以重新排列（24）得到……（25）其中……（26）在（a）的条件下：……关于x是非递增的，……关于x是非递减的，并且对于……是非递增的，对于……是递减的。因此，……中的所有项对于……都是非正的。根据归纳假设，……。使用与引理1(c)相同的论证，我们可以证明对于所有的……都有……。因此，（25）右侧的所有项都是非正的，所以……。当……趋于……时，证明完成。□