燕山大学理学院，河北 秦皇岛

收稿日期：2023年3月14日；录用日期：2023年4月4日；发布日期：2023年4月19日

摘要

本文考虑了一个基于N策略下带有预留时间和启动时间的M/M/1可修重试排队系统。通过概率母函数法求得系统的稳态概率，并给出了一些性能指标。考虑了双目标优化问题，旨在同时最小化成本和期望等待时间，借助NSGA-II算法来寻找Pareto最优解集。建立二者之间的回归模型，检验从帕累托最优解集获得的最小成本和期望等待时间的关系。

关键词

重试排队，N策略，预留时间，双目标优化，回归分析

Bi-Objective Optimization of the Repairable Retrial Queue with N-Policy

Liuqing He

School of Science, Yanshan University, Qinhuangdao Hebei

Received: Mar. 14^th, 2023; accepted: Apr. 4^th, 2023; published: Apr. 19^th, 2023

ABSTRACT

In this paper, we consider the M/M/1 retrial queue with a repairable server as well as reserved time and setup times under the N-policy. The stationary probabilities of the system are obtained by the generating function method, and some performance measures are given. Bi-objective optimization problem is considered to minimize the cost and expected waiting time at the same time, and NSGA-II algorithm is used to find the Pareto optimal solution set. The regression model between them is then constructed and the relationship between the minimum cost and the expected waiting time obtained from the Pareto optimal solution set is tested.

Keywords:Retrial Queue, N-Policy, Reserved Time, Bi-Objective Optimization, Regression Analysis

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

若顾客到达时，服务台处于忙期，那么他将加入重试轨道等待再次请求服务，这样的行为被称为重试。20世纪50年代Cohen [1] 首次发表了关于重试排队的文章，自此以后，关于重试的研究不断涌现，有关重试排队的分析可参阅Falin [2] 和Artalejo [3] 等人的著作。

实际生活中，经常会发生服务台无法工作的情况，需要维修后才能继续服务顾客，研究可修排队有着重要的现实意义。Shogan [4] 和Neuts [5] 等人分别研究了单服务台和多服务台的可修排队系统。Wang [6] 等人将其引入到重试排队系统中，考虑了M/M/1可修重试排队。

在经典的排队系统中，服务台总是能够提供服务，而休假排队允许服务台在某些时刻去休假。N策略就是众多休假策略的一种情况。当系统为空时，服务台将处于休假状态。只有当队列长度达到N时，服务台才再次开启工作。关于N策略休假的研究最早可以追溯到Kulkarni [7] 的文章。有关休假排队的分析还可以参阅田乃硕 [8] 的著作。

大多数关于排队模型优化的研究都集中在单目标问题上，然而现实世界中有许多优化问题需要同时考虑多个目标函数。关于在排队中考虑多目标优化的问题，可以参阅Wu [9] ，Khodemani-Yazdi [10] 和Hajipour [11] 等人的文献。

本文考虑了一个基于N策略下带有预留时间和启动时间的M/M/1可修重试排队系统，并且考虑了双目标优化的问题，其实用性能在诸多领域为系统管理者提供指导。

2. 模型描述

考虑一个基于N策略下带有预留时间和启动时间的M/M/1可修重试排队系统。顾客到达服从参数为 $\lambda$ 的泊松流。若服务台空闲，新到达的顾客立即接受服务。否则，进入重试轨道等待。排在重试轨道前面的顾客会重新尝试，直到获得服务为止。服务时间和重试时间分别服从参数为 $\mu$ 和 $\delta$ 的指数分布。当系统中最后一个服务完成时，服务台不会立即关闭，而是会预留一段时间。在此期间，如果有新的顾客到达，服务台将工作。否则，将被关闭。当系统中的顾客数达到N时，服务台将重新启动。预留时间和启动时间分别服从参数为 $\sigma$ 和 $\theta$ 的指数分布。服务台工作时，可能会发生故障。损坏的服务台立即被送去修复。服务台故障时，新到达的顾客不会加入系统。服务台寿命和维修时间分别服从参数为 $\beta$ 和 $\alpha$ 的指数分布。假设该模型所涉及的时间变量都是相互独立的，如到达时间、维修时间等。

定义 $\left(N\left(t\right),I\left(t\right)\right)$ 为时刻t系统的状态，其中 $N\left(t\right)$ 表示轨道中的顾客数， $I\left(t\right)$ 表示服务台的状态(0：空闲；1：繁忙；2：休假；3：故障)。到达顾客对系统的状态一无所知，假设顾客都以概率q进入，那么实际到达率为 $\Lambda =\lambda q$ 。

3. 稳态分析

服务台各状态下的稳态概率为

$P_0\left(1\right)=\left[\frac{\delta }{\lambda +\delta }-\frac{\mu }{\lambda +\delta }\frac{\lambda \delta +\left(\lambda +\delta \right)\sigma N}{\left(\lambda +\delta \right)\text{Λ}-\delta \mu }\right]P_{0,0}$ ，

$P_1\left(1\right)=\frac{\lambda \delta +\left(\lambda +\delta \right)\sigma N}{\delta \mu -\left(\lambda +\delta \right)\text{Λ}}{P}_{0,0}$ ，

$P_2\left(1\right)=\sigma \left(\frac{N}{\text{Λ}}+\frac{1}{\theta }\right)P_{0,0}$ ，

$P_3\left(1\right)=\frac{\beta }{\alpha }\frac{\lambda \delta +\left(\lambda +\delta \right)\sigma N}{\delta \mu -\left(\lambda +\delta \right)\text{Λ}}{P}_{0,0}$ ，

且

${P^{\prime }}_0\left(1\right)=\frac{1}{\lambda +\delta }\{\frac{2\mu \sigma N\lambda +\mu N\left(N-1\right)\sigma \left(\lambda +\delta \right)}{2\left[\delta \mu -\left(\lambda +\delta \right)\Lambda \right]}+\frac{\mu \Lambda \left(\lambda +\delta \right)\left[\lambda \delta +\sigma N\left(\lambda +\delta \right)\right]}{{\left[\delta \mu -\left(\lambda +\delta \right)\Lambda \right]}^2}+\sigma N\}{P}_{0,0}$

${P^{\prime }}_1\left(1\right)=\left\{\frac{2\sigma N\lambda +N\left(N-1\right)\sigma \left(\lambda +\delta \right)}{2\left[\delta \mu -\left(\lambda +\delta \right)\Lambda \right]}+\frac{\Lambda \left(\lambda +\delta \right)\left[\lambda \delta +\sigma N\left(\lambda +\delta \right)\right]}{{\left[\delta \mu -\left(\lambda +\delta \right)\Lambda \right]}^2}\right\}{P}_{0,0}$ ，

${P^{\prime }}_2\left(1\right)=\sigma \left[\frac{N\left(N-1\right)}{2}\frac{1}{\Lambda }+\frac{N}{\theta }\right]P_{0,0}$ ，

${P^{\prime }}_3\left(1\right)=\frac{\beta }{\alpha }\left\{\frac{2\sigma N\lambda +N\left(N-1\right)\sigma \left(\lambda +\delta \right)}{2\left[\delta \mu -\left(\lambda +\delta \right)\Lambda \right]}+\frac{\Lambda \left(\lambda +\delta \right)\left[\lambda \delta +\sigma N\left(\lambda +\delta \right)\right]}{{\left[\delta \mu -\left(\lambda +\delta \right)\Lambda \right]}^2}\right\}{P}_{0,0}$ ，

其中

$P_{0,0}={\left[\left(\frac{\mu }{\lambda +\delta }+1+\frac{\beta }{\alpha }\right)\frac{\lambda \delta +\left(\lambda +\delta \right)\sigma N}{\delta \mu -\left(\lambda +\delta \right)\Lambda }+\frac{\delta }{\lambda +\delta }+\frac{\sigma N}{\Lambda }+\frac{\sigma }{\theta }\right]}^{-1}$ 。

一名顾客到达并选择进入系统的期望等待时间为

$W=\frac{{P^{\prime }}_0\left(1\right)+{P^{\prime }}_1\left(1\right)+{P^{\prime }}_2\left(1\right)+{P^{\prime }}_3\left(1\right)}{\Lambda \left[P_1\left(1\right)+P_2\left(1\right)\right]}$ ，

轨道中的平均顾客数为

$E\left(N\right)={P^{\prime }}_0\left(1\right)+{P^{\prime }}_1\left(1\right)+{P^{\prime }}_2\left(1\right)+{P^{\prime }}_3\left(1\right)$ 。

4. 双目标优化

本节建立了一个双目标优化模型，旨在同时最小化成本和期望等待时间。期望等待时间是决定服务质量的重要因素，然而在排队系统中，服务成本与服务质量常常发生冲突，因此本文将二者结合起来，寻找到使得它们同时达到最小的解集，并考虑它们之间存在的回归关系。

本文所构建的模型中，阈值N和服务率 $\mu$ 是重要参数，显著影响整个系统，因此本文构建了期望等待时间函数 $W\left(N,\mu \right)$ 和成本函数 $F\left(N,\mu \right)$ 。下面给出成本函数的具体表达式

$F\left(N,\mu \right)=C_{n}E\left(N\right)+C_s\mu +C_1{P}_1\left(1\right)+C_2{P}_2\left(1\right)+C_3{P}_3(\; 1\; )$

其中

$C_n$ 代表每名顾客在系统内的单位时间成本。

$C_s$ 代表服务台提供服务的单位时间成本。

$C_1$ 、 $C_2$ 和 $C_3$ 分别代表了系统处于忙期、休假期和故障期的单位时间成本。

该双目标优化问题陈述如下

$\underset{\alpha >0,\mu >0}{\min }\left[F\left(N,\mu \right),W\left(N,\mu \right)\right]$ 。

借助NSGA-II算法来寻找Pareto最优解集 $\left(F_P,W_P\right)$ 。首先，随机产生初始种群，对其进行非支配快速排序，通过选择、交叉和变异操作得到第一代子代种群。然后，合并父代种群和子代种群，进行快速非支配排序，计算个体拥挤度，选取合适的个体组成新的父代种群。最后，通过选择、交叉和变异操作产生新的子代种群。依此类推，直到满足最大迭代次数，结束运行。

表1给出了 $\lambda$ 取不同值时的Pareto最优解。实际上每个 $\lambda$ 对应的最优解集中都有50组数据，在这里只截取了部分数据做展示。

表1. $\lambda$ 取不同值时的Pareto最优解

图1展现了不同 $\lambda$ 取值下的 $F_P$ 关于 $W_P$ 的走势图。从中可以看出， $F_P$ 和 $\lambda$ 成正比关系。 $F_P$ 和 $W_P$ 之间成反比关系，近似于逆函数、负指数分布或对数函数。然而在回归过程中，发现建立对数函数拟合的效果是最优的。

观察图2，可发现残差均数接近于0，标准差接近于1，数据呈标准正态分布。从图3中可看出图上的点近似地在一条直线附近，这意味着残差正态性条件是达到的，可建立各个变量间的回归关系。因此，建立多元回归模型如下

$F_P={\beta }_0+{\beta }_1\lambda +{\beta }_2{W}_P+{\beta }_3\ln W_P$

图1. Pareto最优解走势图

图2. 回归残差项直方图

图3. 回归残差项的K-S检验

基于表1中的数据，使用加权最小二乘估计法(WLS)得到参数的估计量，结果见表2。

表2. 回归结果

注：^***表示系数在1%的水平下显著，括号内为稳健的标准差。

从表2中可以看出，在1%的显著性水平下，各个自变量对因变量的影响和回归方程都有显著的统计学意义。调整后的拟合优度为 $R^2=94\%$ ，本文所选取的自变量一共可以解释因变量94%的变化，这说明模型拟合效果良好。

因此得到回归方程

$F_P=12.086+0.313\lambda +3.498W_P-17.551\ln W_P$

从回归方程中，可以看出： $\lambda$ 每变动一个单位， $F_P$ 平均变动0.313个单位； $W_P$ 每变动一个单位， $F_P$ 平均变动3.498个单位； $\ln W_P$ 每变动1%， $F_P$ 平均变动17.551个单位。其中， $\lambda$ 对 $F_P$ 的影响是正向的，这是因为当 $\lambda$ 变大时，轨道中的顾客数增加，显然会导致成本的增加。 $W_P$ 的参数估计值虽然为正，但 $\ln W_P$ 的参数估计值为负，并且 $\ln W_P$ 对 $F_P$ 的影响更大，这是因为顾客在系统中的期望逗留时间增加，导致系统变得拥堵，轨道中的顾客数增加，因此成本增加。

5. 结论

本文考虑了基于N策略下带有预留时间和启动时间的M/M/1可修重试排队系统。利用概率母函数的方法，得到了系统的稳态概率，并给出了系统的关键性能指标。制定了一个基于性能指标和成本要素的成本函数，考虑了双目标优化问题，借助NSGA-II算法最小化成本函数和期望等待时间，得到了多组Pareto最优解集。随后建立了一个回归模型，检验了从帕累托最优解集获得的最小成本和期望等待时间的关系。

文章引用

何柳青. 带有N策略的可修重试排队系统的双目标优化
Bi-Objective Optimization of the Repairable Retrial Queue with N-Policy[J]. 统计学与应用, 2023, 12(02): 339-345. https://doi.org/10.12677/SA.2023.122036

参考文献