一种G/G/1排队系统的等待响应时间置信区间预测方法和装置

摘要

本发明公开了一种G/G/1排队系统顾客等待时间和响应时间置信区间预测方法，包括：为ID号i的顾客采样m个服从经验分布函数的服务时间的随机样本；计算ID号i的顾客的m个等待时间和响应时间的样本及其均值；计算ID号i的顾客的等待时间均值的B个Bootstrap样本、及其均值和标准差；以及计算ID号i的顾客的响应时间均值的B个Bootstrap样本(B为大于等于100的整数)、及其均值和标准差；从而确定ID号i的顾客置信水平为1‑α的等待时间和响应时间的标准Bootstrap置信区间、分位数置信区间、偏差校正分位数置信区间、及枢轴置信区间。本发明为基于G/G/1排队系统的n个顾客中每个顾客等待时间和响应时间的置信区间的方法，预测顾客等待时间和响应时间的置信区间更具有实用价值。

说明书

技术领域

本发明涉及计算机科学、统计学、排队论技术领域，更具体的涉及一种基于服务时间经验分布函数和Bootstrap方法的G/G/1排队系统顾客等待时间和响应时间的置信区间预测。

背景技术

目前各类医院、银行、政务服务大厅等处现存的排队机，顾客取号后，仅仅知道自己处于队列中的位置，无法知道要等待多长时间才能获得服务，也无法知道获得服务后需要多长时间才能结束服务。尽管已有一些专利如专利号为200710027670.2的专利《一种智能排队叫号系统》，专利号为201210242019.8的专利《一种预估业务处理时间的排队处理系统及排队机调度方法》，专利号为201410231288.3的专利《一种用于排队机的等待时间预测方法》等公开了不同的预测顾客等待时间的方法，但存在如下不足：(1)现有专利预测的是顾客等待时间的点估计；但由于各种随机因素的影响，顾客的等待时间通常在一定的范围内变化，因此通过预测顾客等待时间的置信区间更符合客观实际，也便于顾客合理安排其它事务；(2)专利号为2007100 27670.2的专利虽然预测了顾客二次排队返回时间段的时间区间，但所述区间不是统计学意义上的置信区间，且采用的是M/M/n排队模型,而不是更具一般性的G/G/1排队模型。

此外，现有文献也讨论了顾客平均等待时间和响应时间的置信区间估计方法，例如有文献讨论了G/G/1排队系统n个顾客平均等待时间和响应时间的置信区间估计，有文献讨论了M/G/1排队系统n个顾客平均等待时间和响应时间的置信区间估计，有文献讨论了M/G/c排队系统n个顾客平均队列长度的置信区间估计，有文献讨论了求解G/G/1排队系统等待时间分布的一种方法。然而，这些文献均讨论的是n个顾客的平均性能指标或分布计算方法，而没有涉及预测排队系统中n个顾客中每个顾客等待时间和响应时间的置信区间。

发明内容

本发明实施例提供一种G/G/1排队系统的等待响应时间置信区间预测方法和装置，用以解决上述背景技术中提出的问题。

本发明实施例提供一种G/G/1排队系统的等待响应时间置信区间预测方法，包括：

获取历史上多个服务周期内为顾客提供服务的实际服务时间的样本数据，并确定实际服务时间的经验分布函数；

根据实际服务时间的经验分布函数，为ID号i的顾客采样m个服从经验分布函数的服务时间的随机样本；

根据服务时间的随机样本，确定ID号i的顾客的m个等待时间的样本及其均值，并确定ID号i的顾客的m个响应时间的样本及其均值；

根据ID号i的顾客的m个等待时间的样本，计算ID号i的顾客的等待时间均值的B个Bootstrap样本、及其均值和标准差；根据ID号i的顾客的m个响应时间的样本，计算ID号i的顾客的响应时间均值的B个Bootstrap样本、及其均值和标准差；

根据ID号i的顾客的m个等待时间的样本均值、ID号i的顾客的m个响应时间的样本均值、ID号i的顾客的等待时间均值的B个Bootstrap样本均值和标准差、ID号i的顾客的响应时间均值的B个Bootstrap样本均值和标准差，确定ID号i的顾客置信水平为1-α的等待时间和响应时间的标准Bootstrap置信区间、分位数置信区间、偏差校正分位数置信区间、及枢轴置信区间。

进一步地，所述实际服务时间为：

Y

其中，Y

进一步地，所述ID号i的顾客的m个等待时间的样本、所述ID号i的顾客的m个响应时间的样本分别为：

如果i＝＝1，则：w

如果i≠1，则：w

其中，w

进一步地，所述ID号i的顾客的m个等待时间的样本均值：

所述ID号i的顾客的m个响应时间的样本均值：

进一步地，所述根据ID号i的顾客的m个等待时间的样本，计算ID号i的顾客的等待时间均值的B个Bootstrap样本、及其均值和标准差，具体包括：

从ID号i的顾客的m个等待时间的样本w

重复该有放回的抽取m个Bootstrap样本并计算其均值的过程B次，获得ID号i的顾客的等待时间均值的B个Bootstrap样本

其中，B为整数且B大于等于1000。

进一步地，所述ID号i的顾客置信水平为1-α的等待时间和响应时间的标准bootstrap置信区间为：

其中，z

进一步地，将

所述ID号i的顾客置信水平为1-α的等待时间和响应时间的分位数置信区间为：

进一步地，令

a

其中，φ

所述ID号i的顾客置信水平为1-α的等待时间和响应时间的偏差校正分位数置信区间为：

进一步地，所述ID号i的顾客置信水平为1-α的等待时间和响应时间的枢轴置信区间为：

本发明实施例还提供一种G/G/1排队系统的等待响应时间置信区间预测装置，包括：均与网络交换机连接的顾客取号装置、顾客服务装置、排队服务器、等待时间和响应时间显示屏、以及若干顾客本人的手机；

所述排队服务器：用于获取历史上多个服务周期内为顾客提供服务的实际服务时间的样本数据，并确定实际服务时间的经验分布函数；

用于根据实际服务时间的经验分布函数，为ID号i的顾客采样m个服从经验分布函数的服务时间的随机样本；

用于根据服务时间的随机样本，确定ID号i的顾客的m个等待时间的样本及其均值，并确定ID号i的顾客的m个响应时间的样本及其均值；

用于根据ID号i的顾客的m个等待时间的样本，计算ID号i的顾客的等待时间均值的B个Bootstrap样本、及其均值和标准差；根据ID号i的顾客的m个响应时间的样本，计算ID号i的顾客的响应时间均值的B个Bootstrap样本、及其均值和标准差；

用于根据ID号i的顾客的m个等待时间的样本均值、ID号i的顾客的m个响应时间的样本均值、ID号i的顾客的等待时间均值的B个Bootstrap样本均值和标准差、ID号i的顾客的响应时间均值的B个Bootstrap样本均值和标准差，确定ID号i的顾客置信水平为1-α的等待时间和响应时间的标准Bootstrap置信区间、分位数置信区间、偏差校正分位数置信区间、及枢轴置信区间。

本发明实施例提供一种G/G/1排队系统的等待响应时间置信区间预测方法和装置，与现有技术相比，其有益效果如下：

本发明公开的是一种G/G/1排队系统中n个顾客中每个顾客等待时间和响应时间的置信区间预测方法和装置。排队系统是一种随机服务系统，顾客的等待时间和响应时间由顾客的到达间隔时间分布和为顾客提供服务的时间分布所确定，一旦顾客取号并开始排队，顾客的到达间隔时间就确定了，因此顾客的等待时间和响应时间将由为顾客提供服务的时间分布所确定。通过获取历史上多个服务周期内为顾客提供服务的实际服务时间的样本数据，并据此拟合实际服务时间的经验分布函数(且随着收集的实际服务时间的样本数据的逐渐增多，实际服务时间的经验分布函数的精度也会进一步提高)；再通过生成m个服从经验分布函数的实际服务时间的样本数据和Bootstrap方法，预测顾客的等待时间和响应时间的置信区间；与现有专利对顾客等待时间和响应时间的点估计方法相比，对顾客等待时间和响应时间置信区间的预测更符合排队系统的客观规律、更有利于顾客合理安排个人事务、更有利于顾客获得满意的服务体验。

附图说明

图1为本发明实施例提供的一种G/G/1排队系统的等待响应时间置信区间预测方法流程示意图。

图2为本发明实施例提供的一种G/G/1排队系统的等待响应时间置信区间预测装置连线示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例涉及的术语和符号：

等待时间：从顾客开始排队到顾客开始被服务所经历的时间长度；

服务时间：从顾客开始被服务到被服务完成所经历的时间长度；

响应时间：从顾客开始排队到顾客被服务完成所经历的时间长度，响应时间是等待时间与服务时间之和；

i：顾客的ID号；

T

x

C

S

E

W

R

Y

y

w

r

参见图1，本发明实施例提供一种G/G/1排队系统的等待响应时间置信区间预测方法，该方法包括：

步骤S1，获取历史上多个服务周期内为顾客提供服务的实际服务时间的样本数据，并确定实际服务时间的经验分布函数。

步骤S2，根据实际服务时间的经验分布函数，为ID号i的顾客采样m个服从经验分布函数的服务时间的随机样本。

步骤S3，根据服务时间的随机样本，确定ID号i的顾客的m个等待时间的样本及其均值，并确定ID号i的顾客的m个响应时间的样本及其均值。

步骤S4，根据ID号i的顾客的m个等待时间的样本，计算ID号i的顾客的等待时间均值的B个Bootstrap样本、及其均值和标准差；根据ID号i的顾客的m个响应时间的样本，计算ID号i的顾客的响应时间均值的B个Bootstrap样本、及其均值和标准差。

步骤S5，根据ID号i的顾客的m个等待时间的样本均值、ID号i的顾客的m个响应时间的样本均值、ID号i的顾客的等待时间均值的B个Bootstrap样本均值和标准差、ID号i的顾客的响应时间均值的B个Bootstrap样本均值和标准差，确定ID号i的顾客置信水平为1-α的等待时间和响应时间的标准bootstrap置信区间、分位数置信区间、偏差校正分位数置信区间、及枢轴置信区间。

需要说明的是，本发明实施例提供一种G/G/1排队系统的等待响应时间置信区间预测方法的具体实施方式参见下面的一种G/G/1排队系统的等待响应时间置信区间预测装置的具体实施方式。

基于同一发明构思，参见图2，本发明实施例提供一种G/G/1排队系统的等待响应时间置信区间预测装置，该装置包括：

一台顾客取号装置、一台顾客服务装置、一台排队服务器、一台等待时间和响应时间显示屏、以及若干顾客本人的手机构成，以上装置分别连接到网络交换机上。

顾客取号装置：顾客在此装置上点击“取号按钮”取号或“刷卡取号”后，顾客取号装置要完成如下功能：

(1)将顾客取号消息“Customer Arrival”发送给排队服务器，等待排队服务器返回该顾客的ID号i，为其指派的条码C

(2)打印分配给顾客i的条码、等待时间和响应时间的置信区间。

顾客服务装置：当服务人员开始对顾客i提供服务时，如果顾客没有在叫号时到达服务窗口，则将二元组(顾客的ID号i，“Balking”)发送给排队服务器；否则，服务人员首先扫描顾客提供的条码，同时顾客服务装置完成如下功能：

(1)将2元组(顾客的ID号i，“Start”)发送给排队服务器；

(2)为该顾客提供服务；

(3)当服务结束时，将2元组(顾客的ID号i，“Finish”)发送给排队服务器。

(4)呼叫排队服务器返回的下一个顾客的ID号i。

排队服务器：排队服务器根据收到的来自顾客取号装置或顾客服务装置的不同消息，分别完成如下功能：

1.冷启动：为了预测顾客等待时间和响应时间的置信区间，需要收集历史上一个或多个服务周期内为顾客提供服务的实际服务时间的样本数据：

(1)如果已收集到这类样本数据，则将这些样本数据输入到排队服务器；

(2)如果没有这种数据，则首先收集这类样本数据(参见5)；在收集样本数据期间，不提供对顾客等待时间和响应时间的置信区间的预测，但提供顾客在当前排队中的位置信息；

(3)根据所收集的实际服务时间的样本数据以及统计学的理论，获得实际服务时间的经验分布函数。

2.初始化：当一个服务周期开始时，做如下初始化工作：

(1)设置用户ID为0，即i＝0；

(2)设置用户ID为0的等待时间为0，即W

3.当排队服务器收到顾客取号装置的“Customer Arrival”消息时，要完成如下功能：

(1)i＝i+1，然后将顾客ID号i和条码C

(2)记录ID号i的顾客的到达时间T

(3)计算顾客的到达间隔时间x

(4)为顾客i预测等待时间和响应时间的置信区间(参见6)；

(5)将顾客ID号i，条码C

4.当排队服务器收到顾客服务装置的(顾客的ID号i，“Start”)消息时，要完成如下功能：

(1)记录为顾客i提供服务的开始时间S

(2)计算顾客i的实际等待时间W

5.当排队服务器收到顾客服务装置的(顾客的ID号i，“Finish”)或(顾客的ID号i，“Balking”)消息时，要完成如下功能：

(1)记录给顾客i提供服务的结束时间E

(2)计算顾客i的实际响应时间R

(3)计算顾客i的实际服务时间Y

(4)用顾客i的实际等待时间和响应时间替换顾客i的预测等待时间和响应时间，然后重新计算仍在排队等待的顾客的预测等待时间和响应时间，并刷新“顾客等待时间和响应时间显示屏”和“顾客本人的手机”的预测等待时间和响应时间；

(5)如果顾客ID号i+1在等待服务，则将将顾客ID号i+1发送到顾客服务装置。

6.为ID号i的顾客预测等待时间和响应时间的置信区间要完成如下功能(如果要重新计算仍在排队等待的顾客的预测等待时间和响应时间，则从步骤(3)开始执行)：

(1)根据1所生成的实际服务时间的经验分布函数，为ID号i的顾客采样m个服从经验分布函数的服务时间的随机样本：y

(2)如果i＝＝1，则令：w

(3)如果i≠1，则令：w

(4)对ID号i的顾客的m个等待时间的样本w

(5)对ID号i的顾客的m个响应时间的样本r

(6)利用ID号i的顾客的m个等待时间的样本w

步骤①：从样本w

步骤②：重复步骤①B次，获得ID号i的顾客的等待时间均值的B个Bootstrap样本

(7)利用ID号i的顾客的响应时间的样本r

(8)计算ID号i的顾客置信水平为1-α的等待时间和响应时间的标准bootstrap置信区间(Standard bootstrap confidence interval)，计算公式分别为：

其中z

(9)假设

(10)令：

计算ID号i的顾客置信水平为1-α的等待时间和响应时间的偏差校正分位数置信区间(Bias-corrected percentile bootstrap confidence interval)，计算公式分别为：

(11)计算ID号i的顾客置信水平为1-α的等待时间和响应时间的枢轴置信区间(Pivotal bootstrap confidence intervals)，计算公式分别为：

等待时间和响应时间显示屏：接受并显示来自排队服务器的正在排队的顾客等待时间和响应时间的置信区间等数据。

顾客本人的手机：接受并显示来自排队服务器的该手机顾客的等待时间和响应时间的置信区间等数据。

需要说明的是，本发明实施例涉及的方法和装置的适用场景举例：医院单台设备的检查排队、医院指定专家门诊的排队等。

以上公开的仅为本发明的几个具体实施例，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围，但是，本发明实施例并非局限于此，任何本领域的技术人员能思之的变化都应落入本发明的保护范围内。