（运筹学与控制论专业论文）部分服务台休假的多服务台排队系统.pdf

摘要 本文在多服务台休假排队系统研究的基础上，利用拟生灭过程( 有限状态拟 生灭过程) 和矩阵几何解的方法进一步研究了部分服务台休假的排队系统( 有限 排队系统) ，推广了原有的多服务台休假排队系统的研究，弥补了容量有限的多服 务台休假排队系统研究的不足。文章主要做了以下工作： 首先，简要的介绍了排队论的基本知识，对多服务台休假排队的研究现状进行 了总结，并且介绍了研究的基础理论和方法。 其次，对部分服务台异步单重休假m m c 排队系统进行了研究。在建立排队 系统满足的转移概率矩阵的基础上，利用拟生灭过程和矩阵几何解方法，给出了 系统的稳态指标的计算方法，并且证明了这些稳态指标的条件随机分解结果。进 而揭示了异步单重休假m m , c 排队是本模型的一个特例。 最后，研究了部分服务台同步多重休假的m m c k 排队系统及其优化问题。 以前研究的休假排队系统都假设系统的容量是无限的，但在实际问题中系统的容 量通常是有限的，而且对容量有限的排队系统研究理论难度较大。本文在系统容 量有限的经典m m c k ( c 皇蛐排队中首次引入部分服务台同步多重休假策略，利用 有限状态拟生灭过程和全概率分解的方法，得到了系统的稳态队长分布和稳态等 待时间分布。因为系统容量有限，如果去休假( 从事辅助工作) 的服务台较多的 话，势必造成到达不能进入系统的顾客相对就多，这样虽然提高了系统辅助工作 的收入，却减少了系统的主收入，这里自然就存在当系统空闲时让多少个服务台去 休假( 从事辅助工作) 才使得整个系统的总收益最大的优化问题。因此本文进一 步讨论了系统空闲时允许同时休假的服务台的最佳个数问题，给出了计算的方法 与数值例子。 关键词：休假排队；部分服务台休假；拟生灭过程；矩阵几何解；条件随机分解； 有限状态 a b s n a d a b s t r a c t b a s e do nt h er e s e a r c ho fv a c a t i o nq u e u ew i t hm u l t i s e r v e r , t h e ( f i n i t e ) q u e u e sw i t h v a c a t i o no fp a r t i a ls e r v e r sa r ec o n s i d e r e db yu s i n gq u 勰ib i r t ha n dd e a t hp r o c e s sa n d m a t r i x g e o m e t r i cs o l u t i o n s t h e s ea r ee x t e n s i o nt ot h ep r e v i o u sr e s e a r c ho fv a c a t i o n q u e u ew i t hm u l t i s e r v e r , a n dc o m p e n s a t et h ed e f e c to ft h er e s e a r c ho ff i n i t ev a c a t i o n q u e u e w i t hm u l t i s e r v e r w ed ot h ef o l l o w i n gw o r k ： f i r s t l y , t h eq u e u e i n gt h e o r ya r ei n t r o d u c e db r i e f l y t h er e s e a r c hs t a t u so fv a c a t i o n q u e u ew i t hm u l t i s e r v e ri ss u m m a r i z e d t h et h e o r ya n dm e t h o do fr e s e a r c ha r ea l s o i n t r o d u c e d s e c o n d l y , t h em m cq u e u e w i t hs i n g l ea s y n c h r o n o u sv a c a t i o no fp a r t i a ls e r v e r si s c o n s i d e r e d b a s e do nt h et r a n s i t i o np r o b a b i l i t ym a t r i xo fm o d e l w i t hq u a s ib i r t ha n d d e a t hp r o c e s sa n dm a t r i x g e o m e t r i cs o l u t i o nm e t h o d ，s o m ec o m p u t a t i o n a lm e t h o d sf o r s t a b l ei n d i c e sa n dr e s u l t so fc o n d i t i o n a ls t o c h a s t i c d e c o m p o s i t i o n s a r e g i v e n f u r t h e r m o r e ，w er e v e a lt h a tt h em m cq u e u ew i t hs i n g l ea s y n c h r o n o u sv a c a t i o ni st h e s p e c i a lc a s eo f t h em o d e lw ec o n s i d e r e d f i n a l l y , t h em m c kq u e u ew i t hm u l t i p l es y n c h r o n o u sv a c a t i o n so fp a r t i a ls e r v e r s a n di t so p t i m i z a t i o na r ec o n s i d e r e d i nt h ep a s t , i tw a sa l w a y sa s s u m e dt h a tt h ec a p a c i t y o ft h eq u e u ew a si n f i n i t ew h e nv a c a t i o nq u e u ew i t hm u l t i s e r v e rw a sc o n s i d e r e d i n f a c t ，t h er e a lq u e u e i n gs y s t e mi no u rd a i l yl i f ei sf i n i t e ，a n di ti sh a r d e rt os t u d yt h ef i n i t e q u e u es y s t e m i nt h i sp a p e r ，w eb r i n gt h ep o l i c yo fm u l t i p l es y n c h r o n o u sv a c a t i o n so f p a r t i a ls k , * l v e r st ot h ec l a s s i cm m c kq u e u e b yu s i n gf i n i t eq u a s ib i r t ha n dd e a t h p r o c e s sa n dt o t a lp r o b a b i l i t yd e c o m p o s i t i o n ，t h es t a t i o n a r yd i s t r i b u t i o n so ft h eq u e u e i n g s y s t e ma r eg i v e n s i n c et h ec a p a c i t yo ft h es y s t e mi sf i n i t e ，t h em o r es e r v e r sg o i n gf o r v a c a t i o n ( a u x i l i a r yw o r k ) ，t h em o r ec u s t o m e r sa r el o s t a l t h o u g hi ti n c r e a s e st h ei n c o m e o ft h ea u x i l i a r yw o r k , i td e c r e a s e st h ei n c o m eo ft h em a i nw o r k h o wm a n ys e r v e r s s h o u l dg of o rv a c a t i o n ( a u x i l i a r yw o r k ) w h e ns y s t e mi si d l e i no r d e rt om a x i m i z et h e i n c o m eo fs y s t e m ? s ow ed i s c u s st h en u m b e ro fs e r v e rg of o rv a c a t i o n ( a u x i l i a r yw o r k ) w h e ns y s t e mi si d l e t h ec o m p u t a t i o n a lm e t h o da n dn u m e r i c a le x a m p l ea r eg i v e n a b s t r a c t k e yw o r d s ：v a c a t i o nq u e u e ，v a c a t i o no f p r o c e s s ，m a t r i x - g e o m e t r i c d e c o m p o s i t i o n ，f i n i t es t a t e s h i p a r t i a ls e r v e r s ，q u a s ib i r t ha n dd e a t h s o l u t i o n ， c o n d i t i o n a ls t o c h a s t i c 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：亟! 亟日期：。0 7 年f 月媚 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：撕7 年月衫日 第一章绪论 1 1 排队系统概述 第一章绪论 排队是日常生活中常见的现象，诸如上下班坐公共汽车，等待公共汽车的排 队、病人到医院看病需排队等等；另一种排队是物的排队，例如文件等待打印或 发送。排队现象是由两个方面构成，一方要求得到服务，另一方设法给予服务。 我们把要求得到服务的人或物( 设备) 统称为顾客，给予服务的服务人员或服务机构 统称为服务员或服务台( 有时服务员专指人，而服务台专指给予服务的设备) 。顾客 和服务台构成一个排队系统，或称随机服务系统。 1 1 1 排队系统的组成部分 从决定排队系统的主要因素看，经典排队系统主要由三部分组成：输入过程、 排队规则和服务机构，而后两部分可构成极其复杂的服务过程。同时，经典排队 系统假定服务台完美无缺且服务员始终在线。 可修排队系统放弃服务台完美无缺的假定，认为它在服务过程中会因种种原 因而失效，从而中断顾客的服务。 休假排队系统则考虑到服务员不会始终在线，虽然他不中断顾客的服务，但 每逢顾客服务完成后，它将视情形是继续在线还是离线。 1 1 2 排队论研究的内容和目的 在各种排队系统中，随机性是它们的一个共同特性，而且起着根本性的作用。 顾客的到达间隔时间与顾客所需的服务时间中，至少有一个具有随机性，否则问 题就太简单了。排队论主要研究描述系统的一些主要指标的概率特性，分为三大 部分： ( 1 ) 排队系统的性态问题 研究排队系统的性态问题就是研究排队系统的概率规律，主要包括系统的队 长( 系统中的顾客数) 、顾客的等待时间和逗留时间，以及忙期等的概率分布，包括 它们的瞬时性质和统计平衡下的性态。排队系统的性态问题是排队论研究的核心， 电子科技大学硕士学位论文 是排队系统的统计推断和最优化问题的基础。从应用方面考虑统计平衡下的各个 指标的概率性质尤为重要。 ( 2 ) 排队系统的统计推断 为了了解和掌握一个正在运行的排队系统的规律，就需要通过多次观测、搜 集数据，然后用数理统计的方法对得到的数据进行加工处理，推断所观测的排队 系统的概率规律，从而应用相应的理论成果来研究和解决该排队系统的有关问题。 排队系统的统计推断是已有理论成果应用实际系统的基础性工作，结合排队系统 的特点，发展这类特殊随机过程的统计推断方法是非常必要的。 ( 3 ) 排队系统的最优化问题 排队系统的最优化包括系统的最优设计( 静态最优) 和已有系统的最优运行控 制( 动态最优) ，前者是在服务系统设计之前，对未来运行的情况有所估计，使设计 人员有所依据，例如电话局的规模、水库的容量大小等；后者是对已有的排队系 统寻求最优运行策略。因此，对于一个排队系统的设计或运行管理，就需要考虑顾 客与服务双方的利益，以便在某种合理的指标上使系统达到最优化。对于大多数 实际系统讲，若把输入看作是由客观条件决定的，不受控制( 有时也可采用控制输入 的手段1 ，则解决这种问题的关键是确定服务率或服务台数或选取顾客的服务规则 或这几种量的组合，使之在某种意义下系统达到最优化。优化的指标函数可以是 时间，也可以是费用或收入。学习和应用排队论知识就是要解决客观系统的最优 设计或运行管理，创造更好的经济效益和社会效益。 1 1 3 排队系统的主要数量指标 ( 1 ) 队长和等待队长 队长是指系统中的顾客数( 包括正在接受服务的顾客) ，而等待队长是指 系统中排队等待的顾客数，它们都是随机变量，是顾客和服务机构都十分关心的 数量指标，对系统设计人员更为重要，因为它涉及到等待空间的大小，空间小了 无法容纳，空间大了造成浪费，应确定它们的分布及有关矩( 至少是期望平均值) 。 显然队长等于等待队长加上正在被服务的顾客数。 ( 2 ) 顾客在系统中的等待时间和逗留时间 顾客的等待时间是指从顾客进入系统的时刻起直到开始接受服务为止的这段 时间，而逗留时间是顾客在系统中等待时间与服务时间之和。在假定等待与服务 彼此独立的条件下，等待时间与服务时间是相互独立的。等待时间和逗留时间是 2 第一章绪论 顾客最关心的数量指标，每个顾客都希望他等待的时间越短越好，应用中关心的 是统计平衡下它们的分布及期望平均值。 ( 3 ) 系统的忙期及闲期 从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间 是系统连续繁忙的时间，我们称为系统的忙期，他反映了系统中服务员的工作强 度。与忙期对应的是系统的闲期，即系统连续保持空闲的时间长度。在排队系统 中，统计平衡下忙期与闲期是交替出现的。而忙期循环是指相邻的两次忙期开始 的间隔时间，显然它等于当前的忙期长度与闲期长度之和。 ( 4 ) 输出过程 输出过程也称离去过程，是指接受服务完毕的顾客相继离开系统的过程。刻 画一个输出过程的主要指标是相继离去的闯隔时间和在一段已知时问内离去顾客 的数目，这些指标从一个侧面反映了系统的工作效率。 1 2 休假排队及其研究现状 1 2 1 休假排队系统介绍 休假排队系统是指利用闲期对服务设施进行调整维修，或指服务员在闲期中去 休假，或从事辅助工作的一种排队系统。2 0 世纪中期以来，随着计算机通信网络，柔 性制造系统( f m s ) ，异步转换模式( a t m ) 等高新技术领域的发展，提出了大量的复杂 系统设计和控制问题。这些系统的行为通常依赖于随状态而变化的参数经典排队 模型在处理这类阿题时表现出极大的局限性。休假排队系统正是在这种背景下始 于2 0 世纪7 0 年代。作为经典排队系统的推广，休假排队系统允许服务台采取各种 在某些时候不接待顾客的策略，这些暂时中断服务的时间f 通常是随机变量1 统称为 休假。 根据服务台的个数，我们可将休假服务系统分为单服务台休假排队系统和多服 务台休假排队系统两种。 1 2 2 多服务台休假排队系统研究现状 近3 0 年来，单服务台休假排队系统得到了深入的研究p “】，建立了以随机分解为 核心的理论体系，并在各种高新技术领域得到了广泛应用。关于单服务台休假排队 系统研究的方法、结果和文献，详见综述d o s h i l 4 ，t e g h g m i l 9 1 ，田乃硕1 2 0 , 纠或专著 3 电子科技大学硕士学位论文 t a k a g i 嘲a d o s h i l 4 l 指出：无论在理论上还是实际应用中，多服务台休假排队系统的研究都 更为重要。然而，由于问题本身的复杂性，只有少量的工作涉及到多服务台休假排 队。即便如此，几乎在开始研究单服务台休假排队的同时，l e v y 与y e c h i a l i2 2 1 就讨论 了休假时间服从指数分布的m m c ：排队系统。使用传统的生灭过程方法，他们建立 了队长和正在工作的服务台数联合分布的微分方程组，并导出了稳态分布满足的差 分方程。但是，这个庞大的方程组过于复杂，求解遇到了实质性困难。文献【2 2 】只给 出忙的服务台数分布和一个平均队长公式。2 0 世纪8 0 年代初，n c u t se 冽等推进了结 构矩阵分析方法在随机模型中的应用。v i n o dc 卅首先注意到，可用以矩阵分析为基 础的拟生灭过程处理m m c 休假排队系统在这样的处理中率阵r 将起核心作用。 v i n o d 只给出了拟生灭过程刻画，因未能求出率阵，因此没有给出稳态队长、等待时 间分布等各种指标。i g a k i i 矧讨论了只有一个服务台可进入休假的m m 2 排队系统。 对这个本质上仍是单服务台休假的模型，给出了各种稳态分布。总之，休假排队发展 的前2 0 年，多服务台休假系统的分析几乎未取得任何实质性进展。 最近1 0 年，多服务台休假排队系统的研究取得了一些重要成果。在单服务台 休假排队中稳态队长、等待时间均可分解成两个独立随机变量之和，一个是无休假 经典排队中对应的稳态指标，另一个是由休假引起的附加变量。称这类结果为随 机分解，它在单服务台休假排队的理论分析和实际应用中起核心作用。多服务台 休假排队是否仍存在随机分解规律? 这是普遍关注的重要理论问题。在多服务台 休假系统中，部分服务台工作时的情况相当复杂，只有所有服务台全忙时，才能 与对应的经典排队系统表现出明显的一致性。这就导致了在服务台全忙的条件下 比较两类系统的思想。对各种休假羡略的多服务台排队，在服务台全忙的条件下， 系统的顾客数、等待时间均可分解成两个独立随机变量之和 3 1 ，其中一个是对应无 休假经典系统中的同名条件随机变量，另一个是由休假引起的附加随机变量，称 这一结果为条件随机分解。取代单服务台休假排队的直接随机分解，在多服务台 休假排队研究中，条件随机分解理论占有核心地位。 目前多服务台休假排队的研究主要限于m 偶i ，c 系统，这类系统处理依据的理 论与方法主要是拟生灭过程和矩阵几何解，详见n e u t s 专著例。 与单服务台系统比较，多服务台系统中的休假策略将有更加纷纭复杂的变化。 迄今为止，研究工作基本上限于空竭服务类型：即当完成一个服务且系统中无顾 客等待时方可进入休假状态。与单服务台的空竭服务规则不同，现在一个服务台 完成服务时系统内无等待并不意味着整个系统是空的。目前，所研究的多服务台 4 第一章绪论 休假排队系统的休假策略主要是：同步休假、异步休假和限量休假。 同步休假( s y n c h r o n o u sv a c a t i o n ) 是指c 个服务台同时开始和结束休假，一旦系 统全空，所有的c 个服务台同时开始随机长度y 的休假，着休假结束时系统内无顾 客就同步进入另一次休假，直到某次休假结束时系统内有顾客等待为止。这称为 同步多重休假策略，简记( s ，m 。类似地，系统全空时c 个服务台恰好同步休假 一次，然后同步终止休假，视系统内有无顾客进入工作或通常的闲期，称为同步 单重休假策略，简记侣，s v ) 。当系统全空时，同时关闭所有服务台。再有顾客到 达时，所有服务台需同步经历一段启动期后才能接待顾客，称为同步启动时间策 略，简记( s ，s u ) 。对同步多重或单重休假及同步启动的m m c 排队系统，设服务 时间服从位相型分布嘲有册阶不可约表示( 指数分布是其特例) ，田乃硕等【“冽给 出了详尽的分析，利用拟生灭过程与矩阵几何解的方法求出了稳态队长和等待时 间的分布。在服务台全忙的条件下，得到了条件随机分解的结果，即等待队长可 分解成两个独立随机变量之和，一个是对应无休假经典m m c 中的同名条件随机 变量，服从几何分布，另一个是附加队长为m 阶离散p h 随机变量；同样，条件等 待可分解成两个独立随机变量之和，其中一个是对应无休假经典m m c 中的同名 条件随机变量，服从指数分布，另一个是附加延迟为m 阶连续p h 变量。文献 2 9 】 对上述三种同步休假m m c 给出了一个统一的处理。除上述三种休假系统外，夏 茂辉等还研究了同步n - 策略多重休假的m m c 排队系统，利用上面同样的方法 得到了稳态队长和等待时间的分布以及类似的条件随机分解的结果。 异步休假( a s y n c h r o n o u sv a c a t i o n ) 指诸服务台可分别的进入和终止休假。如果每 一服务台完成一个服务并遇系统中无顾客等待，它就单独的开始一个随机长度的 休假。这时，其它服务台可能正在工作，也可能处于休假状态。同样的，我们可 将异步休假分为，异步多重休假策略( a s ，m 、，) 、异步单重休假( a s ，s v ) 和异步启 动策略( a s ，s u ) 。l e v y 与y e c h i a l i ( 1 9 7 6 ) t n j ，v m o d ( 1 9 8 6 ) i 州先后研究了异步多重休 假和异步单重休假的m m c 排队系统，给出了稳态下忙的服务台数的分布和一个 平均队长公式。【3 1 】利用拟生灭过程和矩阵几何解的方法对异步多重指数休假 m m c 得到了详尽的处理。不但给出稳态指标的计算方法，而且证明了条件随机 分解定理。f 3 2 】对( a s ，m v ) 、( a s ，s v ) 和( a s ，s e t ) - - 种模型给出了一个统一的处 理。 限量休假o i m i t e dv a c a t i o n ) 指限制可进入休假状态的服务台个数。当系统中有 c 个服务台时，设0 s dsc 是非负整数，无论系统中有无顾客，最多只允许d 个服 务台进入休假，称为d 限量部分休假策略。在这种休假策略下，又可区别d 个服务 5 电子科技大学硕士学位论文 同步或每个服务台异步进行休假两种情况。而作为终止休假的策略，在每种情况 下又可讨论多重休假、单重休假等不同规则。限量休假最早由i g a k i 2 5 1 研究了只有 一个服务员可进入休假的m m 2 ，分析了n 一策略多重休假和单重休假两种模型。 在休假时间服从一般分布的假设下，使用嵌入m a r k o v 链方法给出了系统的稳态队 长分布，并且证明了在两个服务台全忙的条件下，系统中顾客数可分解成两个独 立随机变量的和。文献 3 3 ，3 4 分别研究了部分服务台同步多重和单重休假的 m m c 排队系统，在假设休假时问服从指数分布的前提下利用拟生灭过程和矩阵 几何解方法，给出了系统稳态指标的解析表示，并证明了条件随机分解结果。最 近，文献【3 5 】还研究了部分服务台异步多重休假的m m e 排队系统，得到了稳态 队长和等待时间的分布以及条件随机分解结果。 在前述各种模型中，休假总是在服务结束时开始即空竭服务规则。也可讨论中 断正在进行的服务而开始休假的策略。典型的例子是服务台可能发生损坏和维修 的排队系统。迄今，服务台可修的多台系统的工作也不多，而且局限于m m c 模 型。可修m j m c 的分析比休假系统更早些，m i t r a n i 与a v i i t z h a k 研究了服务台寿 命和维修时间都服从指数分布的m m c ”。n e u t s 和l u c a n t o n i 使用矩阵分析方法， 把上述工作推广到顾客到达率依赖于完好服务台数的情况p 。i 。v i n o d t “l 中的模型1 实际上是可修m m c 系统，在这类非空竭服务的多台休假系统中，尚不知是否存 在随机分解结果。 关于多服务台休假排队系统研究的方法、结果，详见田乃硕专著【3 】。 1 3 本论文研究的意义 自从2 0 世纪初排队论产生以来，随着经典排队理论研究的深入发展，排队模 型已经广泛应用到许多领域。在工程分析中，最常见的是利用基于生灭过程1 3 9 , ”1 和 指数发布的经典排队系统为实际问题建模，因为这样的模型容易获得解析解。但 是，由于复杂的实际背景及高新技术的出现，使得模型与实际情况有了或多或少 的偏差，牺牲了模型的真实性。因而，经典排队模型的应用受到很大的局限性。 而休假排队的研究弥补了某些欠缺，它不仅反映了服务可能发生中断这一客观事 实，考虑利用空闲时间从事辅助工作而增加系统效益的可能性；而且，各种休假 策略为系统的优化设计和过程控制提供极大的灵活性。因此，从2 0 世纪7 0 年代 起，休假排队引起了大家的广泛关注。 无论在理论上还是实际应用中，多服务台休假排队系统都更为重要。因此， 6 第一章绪论 许多作者已经对多服务台休假排队系统进行了详细的分析，主要文献集中在m m c 系统上。但是，由于多服务台休假排队系统高度复杂，很难给出稳态指标分布的 解析表达式。最近，这个领域的研究取得了一些实质性的进展。t i a n 与l i ，t i a n ， u 和c h a o ，c h a o 与z h a o 等，对各种休假策略的m m c ，g i m c 排队系统研究， 不但给出了稳态队长和等待时问分布的详尽结果，还揭示了“条件随机分解”规 律。此外，z h a n g 与t i a n 又引入了只允许部分服务台休假的策略，使得休假多服 务台模型的研究更加深入。然而，对这类部分服务台休假的多服务台排队系统等 待时间分布的研究没有新的突破，没能给出其解析表达式。 为了适应更加广泛的应用背景，深入研究多服务台休假排队系统，本文依次 讨论了部分服务台异步单重休假m m c 排队系统、部分服务台同步多重休假的 m m c k 排队及其优化。其中第二个排队系统的系统容量是有限的，研究这一系统 是因为在实际问题中系统的容量通常都是有限的，而以前人们研究的休假排队无 不假设系统容量是无限的，这与实际情况往往是不相符的，并且对容量有限的排 队系统研究理论难度较大，因此研究容量有限的多服务台休假排队不仅有重要的 理论意义，也有其实际的应用价值。 1 4 本论文的结构 论文共分为四章，内容包括：绪论、基础理论和方法、部分服务台异步单重 休假m m c 排队系统，部分服务台同步多重休假的m m c k 排队及其优化。 第一章为绪论。首先介绍了排队论的基础知识，包括排队系统的组成部分、 排队论研究的内容和目的，排队系统的主要数量指标；然后介绍了休假排队系统 及其研究现状，其中重点介绍多服务台休假排队系统。 第二章为基础理论和方法。简单的概括了研究所需的基础知识和理论，其中 包括拟生灭过程与矩阵几何解、条件随机分解。 第三章为部分服务台异步单重休假m m c 排队系统。刻画了部分服务台异步 单重休假m m c 排队模型。在建立排队系统满足的转移概率矩阵的基础上，利用 拟生灭过程和矩阵几何解方法，给出了系统的稳态指标，并且证明了这些稳态指 标的条件随机分解结果。 第四章为部分服务台同步多重休假的m m c k 排队及其优化。以前研究的休假 排队系统都假设系统的容量是无限的，但在实际问题中系统的容量通常是有限的， 而且对容量有限的排队系统研究理论难度较大，因此研究容量有限的多服务台休 7 电子科技大学硕士学位论文 假排队不仅有重要的理论意义，也有其实际的应用价值。本章在系统容量有限的 经典m m c k ( c c k l 排队中首次引入部分服务台同步多重休假策略，利用有限状态 拟生灭过程和全概率分解的方法，研究了系统的稳态队长分布和稳态等待时间分 布。因为系统容量有限，如果去休假( 从事辅助工作) 的服务台较多的话，势必 造成到达不能进入系统的顾客相对就多，这样虽然提高了系统辅助工作收入，却 减少了系统的主收入，因此自然就存在当系统空闲时让多少个服务台去休假( 从事 辅助工作) 才使得整个系统的总收益最大的优化问题。因此本章在前面讨论的基 础上，进一步讨论了系统空闲时允许同时休假的服务台的最佳个数问题，并给出 一个具体计算实例。 8 第二章基础理论和方法 第二章基础理论和方法 2 1 拟生灭过程与矩阵几何解 多服务台排队系统的研究主要限于m m c ：排队，这类模型可用拟生灭过程【3 9 】 处理。拟生灭过程是以指数分布为基础的经典生灭过程从一维状态空间到多维状 态空间的推广。正如生灭过程0 9 , 4 0 l 的生成元具有三对角形式一样，拟生灭过程的生 成元是分块三对角矩阵。e v a n s “l ，w a l l a c e ! ”1 首先研究了这类m a r k o v 过程，后者 引入了拟生灭过程这一术语。由于各种多因素、变动参数、随机环境的模型分析 的要求，拟生灭过程已代替生灭过程成为当代随机模型分析的工具。 考虑一个二维m a r k o v 过程f x ( f ) ，o ) ) ，状态空间是 q 一 ( 七，j ) ，k 乏0 , i s ，i 川 ， 称f x ( f ) ，( f ) 是一个拟生灭过程，如果其生成元可写成下列分块三对角形式 q 昌 4c o b 1 ac bac 曰4 ( 2 1 ) 其中所有子块都是m 阶的方阵，满足 ( - 4 0 + c o ) 口一( 两+ a + c ) p 。0 4 + 矗+ c ) 口- 0 4 和4 有负的对角线元素，其余子块均是非负阵。称状态集 0 ，1 ) ， ，2 ) ， ，m ) 为水平k 。若过程是常返的，以( x ，j ) 表示过程仁o ) ，o ) 的极限变量，并记 万茸t 炮尸 x o ) a k ，o ) - ， 一p x k , j n 其中k 乏毗jf f i m 。为适应q 的分块形式，将稳态概率按水平写成分段形式 p t 一阮i ，石1 2 ，r h ) ，k 0 因此有下述理论 定理2 1 1 【4 3 1 过程q 正常返，当且仅当矩阵方程 r 2 口+ r a + c 。0 的最小非负解置的谱半径s p 俾) t1 ，并且齐次线性方程组 9 电子科技大学硕士学位论文 石o ( a o + 咫1 ) 一0 有正解。 定理2 1 2 1 4 3 若矩阵g a + 曰+ c 不可约，率阵置满足s p ( r ) 石。c e ， 这里7 7 2 是生成元g 的平稳概率向量，满足 石? g 一0 ，石p 一1 。 定理2 1 3 【4 3 1当过程q 正常返时，稳态概率向量可用矩阵几何解表为 吒一r ，k o ，1 其中是方程组嘞( - 4 0 + r b x ) 一0 的解，满足正规化条件 ( j - r ) 。1 ea 1 。 在使用拟生灭过程方法研究多服务台休假排队时，通常使用边界状态变体。 当系统有c 个服务台时，边界水平k 一0 工，c 一1 通常有不同的维数。例如 巩= p h l ，啄2 ，, , g a n t ) ，0 s k c 一1 ， 这里m 。，小，m 。小于或等于c 。这时，对应的生成元形如 q = 4c o 口14 q 丑。- l4 - lc 。4 b c ac 露ac ( 2 2 ) 其中4 是聊i 阶方阵，b i ，c 1 分别是m tx 脚k - i ，m tx m m 矩阵，而a ，b ，c 都是 m 阶方阵。为使( 2 2 ) 式与( 2 1 ) 式形式上保持一致，可将( 2 2 ) 式分割成子块 日。一 4c o 置4c l 噩24 c 。一2 e 。4 。 吨籼m 。( 乏) 这里日。是m 一m o + + 。1 阶方阵，h ，h m 分别是m 胁+ 和册+ x r a 矩阵。于是 弘2 ) 式可改写成下列复合分块形式 1 0 第二章基础理论和方法 q 一 h n 4c 口4c 曰ac ( 2 - 3 ) ( 2 3 ) 式与( 2 - 1 ) 式的区别仅在于边界状态的转移，称为( 2 - 1 ) 式的边界状态变 体。置是矩阵方程 r 2 丑+ r a + ct 0 的最小非负解，并引入矩阵 。 b r 】一 ac 。 蜀4g b c 4 a c c c 4 b 。 r b + a 类似于标准拟生灭过程，对变体式( 2 - 3 ) 有 定理2 1 4 1 4 3 1 q + 正常返当且仅当s p 俾) 1 ，并且齐次线性方程组 j ，玛，吸归啤】一0 ( 2 4 ) 有正解。这时稳态分布表为 霭k - 玎c r 一，k c 。 而( ，码，) 是( 2 - 4 ) 式的正解，满足正规化条件 c - 1 吸e + 吒( f 一1 0 4 口一1 。 上述结果见田乃硕专著【4 3 1 。 2 2 条件随机分解 单服务台休假排队系统理论的核心内容是随机分解( s t o c h a s t i c d e , c o m p o s i t i o n ) ，即休假排队系统中队长，等待时间等稳态指标，通常可以分解成 两个独立随机变量之和。其中一个是对应经典无休假系统的同名指标，另一个是 休假引起的附加随机变量，称这样的结果为随机分解规律。各种随机分解结果及 导致这些结果的方法，是休假排队研究的一个特色。随机分解使休假排队与经典 排队的比较一目了然，便于分析各种休假策略对经典排队模型的影响。由于经典 排队系统的指标已经得到深入的研究，所以使问题得以简化。随机分解不仅在休 1 1 电子科技大学硕士学位论文 假排队的理论分析中占有重要的地位，也为各种背景下的实际应用提供了极大的 便利。 对一个经典的单服务台g i g 1 排队系统，以厶q ，形表示其稳态下系统中的顾 客数，排队等待的顾客数及等待时间。引入某种休假策略后，用添加下标的 工，q ，耽表示休假排队系统中的对应稳态随机变量。并以0 ) ，q 0 ) ，l q ) ， q v 0 ) ，形o ) ，矸0 0 ) 表示对应的母函数和l a p l a c e - s t i e l t j e s 变换( l s t ) 。在这些符 号下，随机分解结果可表为 l ，一l + l d ，l ( z ) 一l ( z ) 工d g ) q ，一q + q 。，q ，0 ) = a 0 ) q 。( z ) 职* w + ：，- 0 ) 一w + g ) 町0 ) 其中厶o ) ，蜴q ) 统称为( 由休假引起的) 附加延长，睨称为( 由休假引起的) 附 加延迟，而幺( z ) ，q 0 ) 及叨0 ) 是对应的母函数和l s t 。 f u h r m a n n 与c o o p e r ，l e v y 与k l e i n r o c k i “，s h a n t h i k u m a r 删等许多文献，相 继以各种不同的方法给出了m g 1 休假排队系统中的随机分解结果。d o s h ie 4 l 还从 理论上研究了g i g 1 休假排队中等待时间的分解性，d o s h i 4 7 1 进而把随机分解结 果推广到单服务台休假排队。田乃硕等 4 s - m j 在一系列工作中研究了g m 吖1 型休假 排队，并建立了平行的随机分解规律。正是这些随机分解结果，构成了单服务台 休假排队理论的基础。 在多服务台情况下，休假策略可有更灵活多样的变化，例如：诸服务台可以 同步进入或终止休假；也可个别的开始和结束休假；还可以限制进入休假的服务 台个数，只有部分服务台可以休假。那么，在多服务台休假排队中是否还存在单 服务台系统那样的随机分解? 这是多服务台休假排队研究的主要理论问题。 最近，注意到在多服务台休假排队系统中，当所有的服务台全忙时，与经典 无休假系统的行为没有区别。而部分服务台工作时的边界状态变体概率极其复杂， 且与对应的无休假多服务台排队系统几乎没有什么可比性。只有所有服务台全忙 时，才能与对应的经典排队系统表现出明显的一致性。因此，提出了在服务台全 忙条件下将多服务台休假系统与对应的经典系统加以比较的思想，并由此导致了 各种条件随机分解结果。 在经典多服务台排队系统g i g c 中，沿用上述单服务台系统中随机指标的记 号。以，表示稳态下正在工作的服务台数，j - c 表所有的服务台都处于服务状态。 引入条件随机变量 q ：”一f k c l l 苫c ，一c 第二章基础理论和方法 矸0 ”一 l 厶c ，j c 硝是已知服务台全忙条件下排队等待的顾客数。时。是已知顾客在服务台全忙条 件下到达所需要的等待时间。已经证明，在各种多服务台休假排队系统中，存在 下列条件随机分解规律：烈。和讳都可以分解为两个独立的随机变量之和 q ：一q 忙) + q , t ，q j ( z ) 一q 扣( z ) q d ( z ) k ，= w 忙) + 矸0 ，矸0 。卜( j ) 一w ( c 卜( s ) - 曙o ) 这里，q 。是对应经典无休假多服务台排队系统中服务台全忙条件下排队的顾客 数，q o 0 ) 是其母函数，w ( o 是对应经典无休假多服务台排队系统中已知顾客在 服务台全忙时到达的条件等待时间，矽( 0 ) 表其l s t 。q 。和i 仍称为附加队长 和附加延迟，它们的分布依赖于休假规则。称这类结果为条件随机分解。代替单 服务台休假排队中对稳态指标直接进行随机分解，在多服务台休假排队系统中条 件随机分解将在理论及应用中起重要作用。 电子科技大学硕士学位论文 第三章部分服务台异步单重休假m m c 排队系统 3 1 引言 正如前文所讲，与单服务台休假排队相比，多服务台休假排队有其特有的休 假策略，如只允许部分服务台休假，这一休假策略有其广泛的应用背景。例如1 3 l ， 有多个售票窗口的火车站，即使暂时没有乘客购票，关闭所有的窗口是不合适的， 仍需留下少量窗口继续接待随时到达的购票者。又如把每一辆救护车视为服务台， 即使没有救护任务，也应保持一定数量的救护车处于戒备状态。显然，部分服务 台休假更充分地体现了为顾客服务和在休假期间从事辅助工作两者兼顾的思想， 为系统的设计与控制提供了更大的灵活性。 目前，部分服务台休假排队已经得到了一些研究，例如文献 3 3 ，3 4 分别研究了 部分服务台同步多重和同步单重的m m c 排队，文献【3 5 】研究了部分服务台异步 多重休假的m m c 排队。但是，部分服务台异步单重休假m m c 排队系统尚未见 有研究，本章利用拟生灭过程和矩阵几何解研究了此系统，得到了稳态指标的解 析表示，并证明了条件随机分解结果，最后给出了一个应用实例。本章讨论的系 统模型描述如下： 在到达率为a 、服务率为的经典m m c 排队中，引入部分服务台异步单重 休假策略：设1 s ds c ，服务台完成某顾客服务，若此时系统中有顾客等待，他继 续为下一个顾客服务；若系统中无顾客等待且此时正在休假的服务台数小于d ，该 服务台开始休假；如果系统内无顾客等待但正在休假的服务台数大于或等于d ，则 该服务台进入通常的闲期。一个服务台只休假一次，若返回时有顾客等待就立即 开始服务，否则进入闲期。在这一系统中，任意时刻休假的服务台数不超过d ，至 少有c d 个服务台随时可供顾客利用。 此外，约定到达时间间隔、服务时间、休假时间是相互独立的，采用f i r s t - c o m e f i r s t s e r v e d ( f c f s ) 排队规则。 3 2 系统分析 l v ( t ) 表示时刻f 系统内顾客数，o ) 表示时刻加! 在休假的服务台数。休假时 1 4 第三章部分服务台异步单重休假m ，排队系统 间v 服从参数为0 的指数分布，独立于到达间隔和服务时间。仁。o ) ，( f ) t o ) 是 一个拟生灭过程，有状态空间 q 一 ，) ，k 乏0 ，0 王，s d 其中状态 ，歹) 表示系统中有k 个顾客，有，个服务台正在休假。系统中可能发生 的状态转移有：状态 ，) 一 + 1 ，) 表示系统中有