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可修重试排队系统。顾客到达服从参数为
的泊松流。若服务台空闲,新到达的顾客立即接受服务。否则,进入重试轨道等待。排在重试轨道前面的顾客会重新尝试,直到获得服务为止。服务时间和重试时间分别服从参数为
和
的指数分布。当系统中最后一个服务完成时,服务台不会立即关闭,而是会预留一段时间。在此期间,如果有新的顾客到达,服务台将工作。否则,将被关闭。当系统中的顾客数达到N时,服务台将重新启动。预留时间和启动时间分别服从参数为
和
的指数分布。服务台工作时,可能会发生故障。损坏的服务台立即被送去修复。服务台故障时,新到达的顾客不会加入系统。服务台寿命和维修时间分别服从参数为
和
的指数分布。假设该模型所涉及的时间变量都是相互独立的,如到达时间、维修时间等。
定义
为时刻t系统的状态,其中
表示轨道中的顾客数,
表示服务台的状态(0:空闲;1:繁忙;2:休假;3:故障)。到达顾客对系统的状态一无所知,假设顾客都以概率q进入,那么实际到达率为
。
3. 稳态分析
服务台各状态下的稳态概率为
,
,
,
,
且
,
,
,
其中
。
一名顾客到达并选择进入系统的期望等待时间为
,
轨道中的平均顾客数为
。
4. 双目标优化
本节建立了一个双目标优化模型,旨在同时最小化成本和期望等待时间。期望等待时间是决定服务质量的重要因素,然而在排队系统中,服务成本与服务质量常常发生冲突,因此本文将二者结合起来,寻找到使得它们同时达到最小的解集,并考虑它们之间存在的回归关系。
本文所构建的模型中,阈值N和服务率
是重要参数,显著影响整个系统,因此本文构建了期望等待时间函数
和成本函数
。下面给出成本函数的具体表达式
其中
代表每名顾客在系统内的单位时间成本。
代表服务台提供服务的单位时间成本。
、
和
分别代表了系统处于忙期、休假期和故障期的单位时间成本。
该双目标优化问题陈述如下
。
借助NSGA-II算法来寻找Pareto最优解集
。首先,随机产生初始种群,对其进行非支配快速排序,通过选择、交叉和变异操作得到第一代子代种群。然后,合并父代种群和子代种群,进行快速非支配排序,计算个体拥挤度,选取合适的个体组成新的父代种群。最后,通过选择、交叉和变异操作产生新的子代种群。依此类推,直到满足最大迭代次数,结束运行。
表1给出了
取不同值时的Pareto最优解。实际上每个
对应的最优解集中都有50组数据,在这里只截取了部分数据做展示。
Table 1. Pareto optimal solutions when λ takes different values
表1.
取不同值时的Pareto最优解
图1展现了不同
取值下的
关于
的走势图。从中可以看出,
和
成正比关系。
和
之间成反比关系,近似于逆函数、负指数分布或对数函数。然而在回归过程中,发现建立对数函数拟合的效果是最优的。
观察图2,可发现残差均数接近于0,标准差接近于1,数据呈标准正态分布。从图3中可看出图上的点近似地在一条直线附近,这意味着残差正态性条件是达到的,可建立各个变量间的回归关系。因此,建立多元回归模型如下
Figure 1. The trend chart of Pareto optimal solutions
图1. Pareto最优解走势图
Figure 2. Histogram for the regression residuals
图2. 回归残差项直方图
Figure 3. K-S test for the regression residuals
图3. 回归残差项的K-S检验
基于表1中的数据,使用加权最小二乘估计法(WLS)得到参数的估计量,结果见表2。
注:***表示系数在1%的水平下显著,括号内为稳健的标准差。
从表2中可以看出,在1%的显著性水平下,各个自变量对因变量的影响和回归方程都有显著的统计学意义。调整后的拟合优度为
,本文所选取的自变量一共可以解释因变量94%的变化,这说明模型拟合效果良好。
因此得到回归方程
从回归方程中,可以看出:
每变动一个单位,
平均变动0.313个单位;
每变动一个单位,
平均变动3.498个单位;
每变动1%,
平均变动17.551个单位。其中,
对
的影响是正向的,这是因为当
变大时,轨道中的顾客数增加,显然会导致成本的增加。
的参数估计值虽然为正,但
的参数估计值为负,并且
对
的影响更大,这是因为顾客在系统中的期望逗留时间增加,导致系统变得拥堵,轨道中的顾客数增加,因此成本增加。
5. 结论
本文考虑了基于N策略下带有预留时间和启动时间的M/M/1可修重试排队系统。利用概率母函数的方法,得到了系统的稳态概率,并给出了系统的关键性能指标。制定了一个基于性能指标和成本要素的成本函数,考虑了双目标优化问题,借助NSGA-II算法最小化成本函数和期望等待时间,得到了多组Pareto最优解集。随后建立了一个回归模型,检验了从帕累托最优解集获得的最小成本和期望等待时间的关系。