带休假延迟和启动时间的N策略多重休假排队系统

申请号：	申请日期：0001/1/1	公开日期：0001/1/1	公开号：
行业类别:	发明人：	专利类型：	申请人：
主分类号：	优先权日：0001/1/1	优先权号：

带休假延迟和启动时间的N策略多重休假排队系统 技术领域 本发明涉及计算机、通讯网络、生产自动化及交通领域，尤其涉及带休假延迟和启动时间的N策略多重休假排队系统。 背景技术 排队系统，也称为随机服务系统，是研究服务过程和拥挤现象的随机模型。顾客随机地到达一个服务系统，要求进行某种服务。服务可能立即开始，也可能需要排队等待一段时间后才开始，服务开始并完成后，顾客离开系统。到达间隔和服务时间是非负离散随机变量的排队系统，称为离散时间排队。 离散时间排队自Meisling(1958)的论文提出以来，得到了较为深入的研究，Yadin、Kella较早在休假排队系统中引入N控制策略，带N策略的Geom/Geom/1休假排队近年来取得了一定的进展。 计算机和通讯网络中排队模型的优化常需要一个随机的延迟休假时间，基于这样的背景，Leung等在排队中引入休假延迟策略并得以进一步研究，本文针对Geom/Geom/1离散时间排队，提出一类模型，即具有N策略并带休假延迟和启动时间的多重休假排队，运用拟生灭过程分析方法，综合考虑系统主要性能指标。 发明内容 本发明的目的在于提供带休假延迟和启动时间的N策略多重休假排队系统，以解决上述技术问题。 本发明为解决上述技术问题，采用以下技术方案来实现： 带休假延迟和启动时间的N策略多重休假排队系统，文中定义x＝1-x，对任意的x∈[0,1]， (1)、系统为晚到达有延迟入口的排队，顾客的到达间隔时间T独立同几何分布到达发生在时隙末端(n-,n)，n＝0,1,2,L； (2)、服务遵照FIFO顺序，开始及结束设为只能发生在时隙t＝n，服务时间S服从参数为μ的几何分布即 (3)、系统采取带休假延迟和启动时间的多重休假N策略控制机制，即当一个忙期结束时，服务台先开始一个随机长度为D的休假延迟期，这段时间内若有顾客到达，服务台立即进入忙期，否则，系统开始多重休假，休假期长度的分布是等到一次休假结束时，系统中的顾客数若不小于N，则服务台先启动然后忙期开始，启动时间A独立同参数α的几何分布； (4)、休假的开始与结束均发生在(n-,n)上，记Ln+为时隙分点n+处的顾客数，在(n,n+)时刻被服务后离开的顾客不再计入Ln+，达到间隔时间T、服务时间S、启动时间A与休假长度V和休假延迟时间D均相互独立； 系统步骤(1)-(4)的状态： 易知{(Ln+,Jn),n≥0}是一个Markov链，其状态空间为 Ω＝{(0,0),(0,1)}U{(k,j):k≥1,j＝0,1,2}， 系统有四种状态：(k,1)(k≥N)表示n+时刻系统有小于N个顾客，记为k个；同时服务台在启动期,(k,2)(k≥1)表示服务台处于工作状态且有k个顾客；(0,1)表示n+时刻系统处于休假延迟状态；(k,0)(k≥0)表服务台处于休假期但系统有k个顾客。 优选的，系统步骤(1)-(4)的四种状态按照字典序排列，{(Ln+,Jn),n≥0}的转移概率矩阵可表为如下分块形式 其中： 由矩阵的结构知，{(Ln+,Jn),n≥0}是一个拟生灭链；为分析此二维随机模型{(Ln+,Jn),n≥0}，率阵R，即矩阵二次方程 R＝R2B+RA+C(1) 的最小非负解R起重要作用； 引理1当p＜μ时，矩阵方程R＝R2B+RA+C存在最小非负解 引理2Markov链{(Ln+,Jn),n≥0}是正常返的当且仅当p＜μ。 优选的，所述带休假延迟和启动时间的N策略多重休假排队系统的稳态队长分布，当p＜μ时，设{(L+,J)}表示Markov链{(Ln+,Jn),n≥0}的稳态极限，记平稳分布 π0＝(π00,π01)，πk＝(πk0,πk2),1≤k≤N-1,πk＝(πk0,πk1,πk2),k≥N, 定理1若p＜μ，则{(L+,J)}的稳态概率分布由(2)式给出 其中 由定理1，可知平稳状态下服务台处于相应状态的概率分布： 优选的，所述带休假延迟和启动时间的N策略多重休假排队系统的条件等待队长和条件等待时间的随机分解，引入条件随机变量： L(N)＝{L+-N|L+≥N,J＝2}，W(N)＝{W|L+≥N,J＝2} 其中L(N)表示顾客数大于或等于N时且服务台在忙期的条件等待队长，W(N)表示顾客到达遇系统有不少于N个顾客且服务台在工作的条件等待时间； 定理2当p＜μ时，系统条件等待队长L(N)可分解为独立的两个随机变量之和： 其中是标准Geom/Geom/1排队系统的稳态队长，服从参数为1-ρ的几何分布，另一部分Ld是附加队长，有分布函数 其中： 推论1稳态时系统的平均顾客数为其中平均附加队长 定理3当p＜μ时，条件等待时间可分解为独立的三个随机变量之和： W(N)＝W0++WN+Wd 其中W0是标准Geom/Geom/1排队中的逗留时间，WN和Wd分别有 推论2W(N)的期望 本发明的有益效果是： 本文分析了带休假延迟和启动时间的N策略多重休假排队系统模型，得到系统顾客数分布的稳态表达式，并证明了系统主要排队指标的条件随机分解结构。这种与排队过程密切相关的控制休假机制对于计算机和通讯领域诸多问题的随机建模而言是可供选择的好方案，并可研究在此基础上，进一步将模型推广使其更具实用性。 具体实施方式 为了使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结合具体实施例，进一步阐述本发明，但下述实施例仅仅为本发明的优选实施例，并非全部。基于实施方式中的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得其它实施例，都属于本发明的保护范围。下述实施例中的实验方法，如无特殊说明，均为常规方法，下述实施例中所用的材料、试剂等，如无特殊说明，均可从商业途径得到。 实施例 带休假延迟和启动时间的N策略多重休假排队系统，文中定义对任意的x∈[0,1]， (1)、系统为晚到达有延迟入口的排队，顾客的到达间隔时间T独立同几何分布到达发生在时隙末端(n-,n)，n＝0,1,2,L； (2)、服务遵照FIFO顺序，开始及结束设为只能发生在时隙t＝n，服务时间S服从参数为μ的几何分布即 (3)、系统采取带休假延迟和启动时间的多重休假N策略控制机制，即当一个忙期结束时，服务台先开始一个随机长度为D的休假延迟期，这段时间内若有顾客到达，服务台立即进入忙期，否则，系统开始多重休假，休假期长度的分布是等到一次休假结束时，系统中的顾客数若不小于N，则服务台先启动然后忙期开始，启动时间A独立同参数α的几何分布； (4)、休假的开始与结束均发生在(n-,n)上，记Ln+为时隙分点n+处的顾客数，在(n,n+)时刻被服务后离开的顾客不再计入Ln+，达到间隔时间T、服务时间S、启动时间A与休假长度V和休假延迟时间D均相互独立； 系统步骤(1)-(4)的状态： 易知{(Ln+,Jn),n≥0}是一个Markov链，其状态空间为 Ω＝{(0,0),(0,1)}U{(k,j):k≥1,j＝0,1,2}， 系统有四种状态：(k,1)(k≥N)表示n+时刻系统有小于N个顾客，记为k个；同时服务台在启动期,(k,2)(k≥1)表示服务台处于工作状态且有k个顾客；(0,1)表示n+时刻系统处于休假延迟状态；(k,0)(k≥0)表服务台处于休假期但系统有k个顾客。 系统步骤(1)-(4)的四种状态按照字典序排列，{(Ln+,Jn),n≥0}的转移概率矩阵可表为如下分块形式 其中： 由矩阵的结构知，{(Ln+,Jn),n≥0}是一个拟生灭链；为分析此二维随机模型{(Ln+,Jn),n≥0}，率阵R，即矩阵二次方程 R＝R2B+RA+C (1) 的最小非负解R起重要作用； 引理1当p＜μ时，矩阵方程R＝R2B+RA+C存在最小非负解 证明由于矩阵A,B,C均为上三角阵，所以可设R的形式也为上三角阵，即代入(1)，可得 引理2Markov链{(Ln+,Jn),n≥0}是正常返的当且仅当p＜μ。 证明Markov链{(Ln+,Jn),n≥0}正常返的充要条件是R的谱半径SP(R)＜1，且(x0,x1,L,x2N+1,x2N+2)B[R]＝(x0,x1,L,x2N+1,x2N+2)有正解。由于 易知B[R]是一个正则随机阵，取(x0,x1,L,x2N+1,x2N+2)为B[R]的不变概率向量，就是以B[R]为系数的方程组的一个正解。因此，{(Ln+,Jn),n≥0}是正常返的当且仅当注意到可知，当且仅当时成立SP(R)＜1。易证，等价于p＜μ。 带休假延迟和启动时间的N策略多重休假排队系统的稳态队长分布，当p＜μ时，设{(L+,J)}表示Markov链{(Ln+,Jn),n≥0}的稳态极限，记平稳分布 π0＝(π00,π01)，πk＝(πk0,πk2),1≤k≤N-1,πk＝(πk0,πk1,πk2),k≥N, 定理1若p＜μ，则{(L+,J)}的稳态概率分布由(2)式给出 其中 证明由矩阵几何解方法，πk＝πNRk-N＝(πN0,πN1,πN2)Rk-N,k≥N，且有(π00,π01,π10,π12,L,πN-1,0,πN-1,2,πN0,πN1,πN2)满足方程 (π00,π01,L,πN0,πN1,πN2)B[R]＝(π00,π01,L,πN0,πN1,πN2)，将B[R]代入，得到方程组 取πN-1,0＝K，记 由定理1，可知平稳状态下服务台处于相应状态的概率分布： 带休假延迟和启动时间的N策略多重休假排队系统的条件等待队长和条件等待时间的随机分解，引入条件随机变量： L(N)＝{L+-N|L+≥N,J＝2}，W(N)＝{W|L+≥N,J＝2} 其中L(N)表示顾客数大于或等于N时且服务台在忙期的条件等待队长，W(N)表示顾客到达遇系统有不少于N个顾客且服务台在工作的条件等待时间； 定理2当p＜μ时，系统条件等待队长L(N)可分解为独立的两个随机变量之和： 其中是标准Geom/Geom/1排队系统的稳态队长，服从参数为1-ρ的几何分布，另一部分Ld是附加队长，有分布函数 其中： 证明系统处于正规忙期且顾客数不少于N的概率为 L(N)的母函数可写为 容易证明σ＝(δ0+δ1+δ2)-1，因此，Ld(z)确是一个PGF。 推论1稳态时系统的平均顾客数为其中平均附加队长 定理3当p＜μ时，条件等待时间可分解为独立的三个随机变量之和： W(N)＝W0++WN+Wd 其中W0是标准Geom/Geom/1排队中的逗留时间，WN和Wd分别有 证明顾客到达遇到状态(j,2)，条件等待时间Wj(N)是j个服务时间的独立和，有由全概率公式： 推论2W(N)的期望 以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的仅为本发明的优选例，并不用来限制本发明，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。