（应用数学专业论文）处理器共享的两类排队模型的研究.pdf

处理器共享的两类排队模型的研究 摘要 排队系统中当其中一个服务员前无顾客时，服务员的服务率就会发生变化的 情况，实际应用中在印刷行业非常多见。本文主要用解析函数边值问题理论研 究了两类处理器耦合的排队模型，一类是两个平行服务器耦合的排队模型，一 类是加入最短队的服务器耦合的排队模型。用解析函数边值问题理论来分析和 研究二维排队问题直是一个热点课题。 全文包括三大部分：第一章介绍了基本的背景、研究进展和文章主要采用 的方法；第二章研究的是有两个服务员共享的简单的排队方式的模型，即每个 服务员有各自的队列，两队队长互不相关，分析了代表两个队长的二维马尔柯 夫过程，推导出了二维过程的平稳分布的母函数的方程，并运用 p d e m a n n - - h i l b e r t 边值问题理论解出了母函数的表达式；第三章研究的是 j s q p s 模型( t h e j o i n i n gt h es h o n e s tq u e u em o d e lw i t hp r o c e s s o rs h a r i n g ) ，模型是 组合了加入最短队模型和处理器共享模型而成的有用排队模型。介绍了耦合的 问题，并给出了f ( x ，y ) 可以被看作复平面上的一个亚纯函数，在这章虽然给出 的是一个特殊的问题，但所得到的结果却适用于一般的二维随机游动。用解析 函数边值问题理论来分析和研究j s q p s 模型是一个较难课题，此课题的研究文 献中尚无报导。 关键词：服务员共享边值问题平稳分布母函数 t h es t u d yo ft w o t y p e s o fp r o c e s s o r s s h a r i n g q u e u i n gs y s t e m a b s t r a c t s y s t e m si nw h i c h t h es e r v i c er a t e so fs t a t i o n sc h a n g ea tt h em o m e n t st h a to n eo f s t a t i o n sb e c o m e se m p 毋, a r ek n o w ni nt h el i t e r a t u r ea ss y s t e m sw i t l lc o u p l e d p r o c e s s o r s i nt h i sd i s s e r t a t i o n ，w ed i s c u s st w ot y p e so fp r o c e s s o r ss h a r i n gq u e u i n g s y s t e m o n ei st w op a r a l l e lq u e u e sw i t hc o u p l e dp r o c e s s o r s ；t h eo t h e ri st h ej o i n i n g t h es h o r t e s tq u e u em o d e lw i t hp r o c e s s o rs h a r i n g t h ed i s s e r t a t i o nc o n t a i n st h r e ep a r t s ：i nc h a p t e r1 ，t h eb a s i ca p p l i c a t i o n b a c k g r o u n d ，a d v a n c e ds t u d i e sa n dt h em a i ni d e ao ft h i sp a p e ra r ei n t r o d u c e d i n c h a p t e r2 ，ic o n s i d e raq u e u i n gs y s t e mi nw h i c ht h e r ea r et w oe x p o n e n t i a ls e r v e r s ， e a c hh a v i n gh i so w nq u e u e ，a n da r r i v i n gc u s t o m e r sw i l lj o i nt h et w oq u e u e s s e p a r a t e l y , a n da n a l y z et h et w o - d i m e n s i o n a lm a r k o vp r o c e s sr e p r e s e n t i n g t h e n u m b e r so f j o b si nt h et w os t a t i o n s af u n c t i o n a le q u a t i o nf o rt h eg e n e r a t i n gf u n c t i o n o ft h es t a 虹o n a r yd i s t r i b u t i o no ft h i st w o - d i m e n s i o n a lp r o c e s si sd e r i v e da n ds o l v e d t h r o u g ht h et h e o r yo fr i e m a r m - h i l b e r tb o u n d a r yv a l u ep r o b l e m s i nc h a p t e r3 ，i c o n s i d e rt h es y s t e m 稍t l lt w op a r a l l e lq u e u e s ，i nw h i c ha r r i v a l sj o i nt h es h o r t e rq u e u e id e s c r i b et h ep r o b l e mo fc o u p l i n ga n ds h o wt h a tt h eg e n e r a t i n gf u n c t i o nf ( x ，y ) c a l lb ec o n t i n u e da sam e r o m o 删cf u n c t i o nt ot h ew h o l ec o m p l e xp l a n e ic o n s i d e ra p a r t i c u l a rp r o b l e mb u tt h er e s u l t so f f e rac o m p u t a t i o n , a l l yr e a s o n a b l es o l u t i o nw h i c h a p p l i e st ov e r yg e n e r a lt w o d i m e n s i o n a lr a n d o mw a l k s i ti sa d i f f i c u l tw o r ku s i n g t h ea n a l y t i c a lf u n c t i o n a lt h e o r yo f b o u n d a r yv a l u ep r o b l e m st os t u d yj s q - p sm o d e l k e y , t o r d s ：c o u p l e dp r o c e s s o r s ，b o u n d a r yv a l u ep r o b l e m s ，s t a t i o n a r yd i s t r i b u t i o n ， g e n e r a t i n gf u n c t i o n i i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所傲的贡献均已在论文中作了声明并表示 了谢意。 作者签名：阀址媚 日 期：j0 0 1 6 瞧 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交论 文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有 关数据库进行检索；有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 作者签名：囤缸捐 日期：卫蚀厶e 丛 处理器共享的两类排队模型的研究硕士学位论文 第一章绪论 排队是在日常生活中经常遇到的现象，银行取款要排队，火车站买票要排队，超市、 商店中购物付款要排队，乘公共汽车要排队，医院候诊要排队，打公共电话要排队，连刚 入学的大学生交费也要排队人们仿佛进入了一个排队的社会，排队成了人们生活的 一部分。此时要求服务的数量超过了服务机构( 服务台、服务员等) 的容量，也就是说， 到达的顾客不能立即得到服务，因而出现了排队现象。由于顾客到达和服务时间的随机性， 可以说排队现象几乎是不可避免的。但在中西文化的不断交流过程中，人们赋予时间的价 值逐渐提高。“时间就是金钱”、“时间就是生命”等类似的话语在人们心中逐渐生根。故此 人们往往不太乐意长时间排队。如何面对排队现象、解决排队问题呢? 这成为社会组织、 特别是服务企业所急需解决的问题。 1 1 排队论的应用与发展背景 排队论是运筹学的一个分支，又称随机服务系统理论或等待线理论，是研究要求获得 某种服务的对象所产生的随机聚散现象的理论。排队现象是工程技术和社会生活中广泛存 在的一种现象。它的存在，对相当广泛的一类工程与社会现象都有着重要影响。因此，采 用一定的方法，对它进行量的研究与评估，就成为数学和工程中的一项重要工作。 排队论由丹麦的a ，k e r l a n g 于1 9 0 9 年创立瞄“。后来，m o l i n a ，f r y ，p o l l a e z e k ，p a l m ， k e n d a l l ，l i n d l e y 和t a k a c s 等一大批杰出的现代数学家相继对排队论的发展做出了重要贡 献。这些贡献主要是：深入研究了那些可以用概率论和随机过程已有成果( 包括马尔柯夫 链和非马尔柯夫链理论) 求解典型输入方式( 即到达间隔分布) 和服务方式( 服务时间分 布) 下的排队现象；推出了这些情况下排队系统的部分输出变量( 如排队长度、等待时间 等的分布或其一阶矩【2 2 】和二阶矩或其拉氏变换) 。到了5 0 年代，从概率论和随机过程 的角度，研究典型情况下的排队问题的数学理论已趋于成熟。当时，已形成两种不同的理 论方法口4 】：种是e r l a n g 提出的微积分法；另一种是l i n d l e y 所成功采用的积分方程法。 当然，这两种方法中的方程都是基于所研究变量的概率。从6 0 年代起，排队论的发展主要 得益于计算机科学的发展。这主要表现在两个方面：一是计算机系统本身的大量工程问题 与理论问题需要排队论来解决；二是计算机的大量应用领域也需要排队论。美国加州大学 的k l e i n r o c k 曾断言，关于现代计算机系统的理论研究，远远落后于该领域实际工程技术的 处理器共享的两类排队模型的研究 硕士学位论文 发展。要弥补这个缺陷，唯有排队论能够担负此任2 ”。 1 。2排队论的数学基础 排队论的数学基础就是概率论与随机过程理论。事实上，排队论中研究的很多数学现 象早在它以前的数学问题中就已研究过。例如，在研究到达方式为泊松到达( 即m g 1 ) 型的系统中，出现的第r 批顾客的各顾客服务时间内独立地来到的新的顾客的数燕问题， 就是与g a l t o n 和w a t s o n 在1 8 7 3 年首次研究过的人口增长问题相同【2 ”。历史上，排队问 题本身也是有志于随机过程理论的数学家们的重要课题。因为它提供了既是平稳，又( 般) 是非马尔柯夫型的易于分析的最好实例陋j 。根据k e n d a l l 和p a l m 等人的研究结果， 在排队系统中，除m j m j m 型的输入以外，排队长度 n 所构成的随机过程都不是马尔柯夫 型的。我们知道，马尔柯夫链是研究不相互独立事件的最简单的实验概型，它是相互独立 实验概型的一种最简单的推广【z ”。如果一个实验概型既不是相互独立的、又不是马尔柯夫 型的，那末，它的研究就将变得相当困难。这就是为什么在所有输入类型的排队系统中， 唯有m m i l l 型的输出变量已得到解析结果的根本原因。 1 3 运用排队论研究排队模型的相关问题 定义：模型a 称为排队系统。它满足下列条件： 1 ) 它是关于具有排队现象的任何实际系统的抽象； 2 ) 它以顾客到达时间间隔的分布与服务时间的分布为输入变量； 3 ) 它以顾客等待时间、排队长度、系统时间( 从顾客到达至离开的时间) 等变量的 分布，或其一阶矩、二阶矩等数字特征，或其序列相关特性为输出变量。 排队系统是服务系统、交通运输、通信系统等许多领域中的问题简化后的数学模型。 顾客按照一定的分布率到达，然后按照特定的排队规则一次到达，一定数量的服务器为其 服务。服务器的服务时间按照一定的分布进行且与顾客的到达相互独立。顾客被服务结束 后离开排队系统。 排队系统的一般框架如下： 排队理论设计一个复杂系统，它包含： ( 1 ) 输入过程：它一般是一个更新流，称为“顾客流”。更广地，也可以是每次批量输入的输 2 处理器共享的两类排队模型的研究 硕士学位论文 入流。 ( 2 ) 服务设备( 服务员或服务线) 的数目：可以有1 个，n 个或0 0 个，它们之间彼此独立地 工作。 ( 3 ) 服务设备对于不同顾客的服务时间是独立同分布的随机变量，它们与输入过程独立。 ( 4 ) 服务规则：最常见的是先来先服务( 记为f i f o ，即f i r s ti nf i r s to u t ) 。 沿用k e n d a l l ( 1 9 5 1 ) 采用的方法，一个排队系统通常用符号a b x y z 作为记录的标 准，其中a 代表到达间隔时间分布的类型，b 代表服务器服务时间分布的类型，x 代表服 务器个数，y 代表队伍容量，z 代表排队规则。 m ：表示指数分布。 e k ：表示k 阶e r l a n g 分布。 g ：表示一般分布函数，再输入流中。有时也用g i 表示。 p h ：表示p h 分布。 常见的排队系统有m f m l ，m f m f n ，m m 7 q o ，g i v i ，m g 1 ，g u g i ( 也记为g g i i ) 对于排队系统中出现的非马尔柯夫型的随机过程，人们曾试图将其转化为马尔柯夫型 进行研究。虽然描述排队长度的随机过程( 一般) 不是马尔柯夫型的，对于m g 1 ，把注 意力指向于各顾客离开的时刻( 该时刻并构成一个再生点序列) ，则排队长度即构成一1 w 嵌 入的马尔柯夫链”。所谓“嵌入的马尔柯夫链”，是指将原来的非马尔柯夫链经过一个特定 的泛函厂+ 映射后所得到的马尔柯夫链。在这里，就是将时间t 限制在“顾客离去的时刻” 用离去时刻所构成的集万代换整个时间域，即r 石，而不是t ( 一o o ，。) 。转化过程如下： f n ( t ) = g ，i t ( - - 0 0 ，) ，是时刻t 的排队长度。若令f 石，则j ，p ) = n ( t ) i 。= q 代表离去时刻t 正在等待和正在被服务的顾客数。由于输入是最简单流， y ( 0 ) 就构成一 个马尔柯夫链，其物理意义是，“在离去一个顾客后所剩下的顾客数”。由于原来的 9 ) ) 并不是马尔柯夫链，因此，这个 y ) 就是嵌入的马尔柯夫链，又称为“受控的马尔柯夫 链” 2 7 1 。 除了排队长度序列 n ) 以外，排队时间( 等待时间) 序列( 彬) 也可进行一定的转换a t a k a c s 曾指出 2 9 】，如果用设想在指定时刻到达顾客的等待时间来表达系统的状态，则过程 竺矍矍茎墨堕堕鲞笙坠蔓型塑堑塞 堡主堂鱼笙塞 也可以看作是马尔柯夫型的。他指出，这种方法只适用于m m m 型和m l ( 3 m 型。这是因 为，对于这两种输入型，事件发生时刻序列 ) 都是泊松流( 最简单流) 事件发生时刻， 而服务时间吒是相互独立的随机变量，所以，等待时间序列 彬) 在给定时刻以后的随机性 态完全可由该时间的值彬决定。从而， 彬) 就是一个马尔柯夫过程。而对其它类型的输 入，如g m i m ，由于乙不是泊松流，因而 彬) 就不是马尔柯夫型。 对不是泊松流的输入，虽然 彬 - 一般不是马尔柯夫过程，但却是过程的马尔柯 夫点f 2 8 】( 又称再生点) 。如设 矿( 乙- o ) = 呒 w ( o ) = ( 1 _ 1 ) ( 1 2 ) 则 呒) 又构成一个马尔柯夫链。t a k a c s 采用研究一般马尔柯夫链的方法【2 6 l ，并引用 l i n d l e y 关于的概率分布函数的极限定理2 ”，推出了求 k ) 的分布函数的递推公式。 然而，他的结果，包括l i n d l e y 的定理，都需要求解一个所谓w i e n e r - h o p f 积分方程，其形 式为 荆= f f ( y ) g ( x y 渺 ( 1 3 ) 式中f ( x ) 在这个特定问题中是 睨) 的分布函数；g ( t ) 是随机变量= 一“的概率密 度函数( z 。，矗“分别是第n 个顾客的服务时间和第n 个和第n + 1 个顾客的到达时间间隔) 。 如果不假定是泊松流，方程( 1 3 ) 的求解是极其困难甚至是不可能的 2 i 】。不仅如此， 用l i n d l e y 的定理验f ( x ) 的存在性本身就是很困难的。 上述回顾与讨论，使我们感到，用泛函映射的方法，将非马尔柯夫过程转化成马尔柯 夫过程，确实可以解决某些输入类型下的排队系统输出变量的求解问题。这也是排队论本 身得以在十分困难的问题中艰难前进的途径之一。 4 处理器共享的两类排队模型的研究 硕士学位论文 1 4 目前的主要研究方法 排队系统中当其中一个服务员前无顾客时，服务员的服务率就会发生变化的情况，实 际应用中在印刷行业非常多见。k o n h e i n , m e i l i j s o n 和m e l k m a n 运用单值化方法，给出了在 完全对称的排队模型中( 即两个服务员有相同的服务率，两队有相同的顾客到达率) 的队 长的联合分布的母函数的表达式。c o h e n 和b o x m a 研究了服务时间服从一般分布的服务器 耦合的排队系统。 关于服务员共享的排队模型已有很多作者在这方面作了研究，用边值问题理论来分析 研究二维排队问题一直是热点的课题。 处理器共享的两类排队模型的研究 硕士学位论文 第二章平行的两个服务员共享的排队模型 2 1 引言 本文考虑的是有两个平行队列的服务员共享的简单的排队方式的模型，即每个服务员 有各自的队列，两队队长互不相关，分析了代表两个队长的二维马尔柯夫过程，推导出了 二维过程的平稳分布的母函数的方程，并运用k i e m a n n - - h i l b e r t 边值问题理论解出了母函 数的表达式。l f l a t t o ，h p m c k e a n 和a b r a h a m m e l k m a r t 已经研究过两个平行队列服务员不 共享的排队模型，并给出了两个队长的联合平稳概率的母函数的椭圆的积分表达形式。但 在本篇文章里我们研究的是两个服务员共享的情况，并且是运用边值问题理论来推导出两 个平行队列服务器耦合的排队模型的队长的联合平稳概率的母函数的表达式。由服务员共 享所引起的许多问题都需要通过函数方程来解。一般情况下，选所研究的模型的队长的平 稳概率的母函数作为未知的函数。 2 。2 模型介绍 我们考虑一个指数型的排队系统，有两个服务员，分别有各自的等待队列，记为i 和 i i ，我们假定如下： ( a ) 顾客按照两个独立的参数均为五的泊松流到达，到达后顾客分别加入两队，顾 客到达加入其中一队后则不可再移动到另一队； ( b ) 服务员的服务时间均服从参数为“的指数分布，服务员的服务规则是先到先服 务 ( c )顾客一到服务员就开始服务，服务对间与顾客到达相互独立； ( d )若其中一队无顾客时，此队服务员就去另一服务窗帮忙： 若队i 空时，“= 0 ，：= 2 ； 若队i i 空时，：= 2 , u ，胁= 0 ； ( a ) 一( d ) 就是本文章所要研究的排队模型。 6 竺墨量苎皇堕堕耋量坠竖型堕堡塑 堡主兰堡垒塞 a 图1 ：模型示意图 用乃p ) ，= 1 ，2 表示时刻t 在j 队中排队和正在被服务的顾客数，则 z ( f ) = 墨0 ) ，：p ) ) t 0 描述了一个状态空间 o ，1 ，2 ) 2 连续时间的马尔可夫链。此 模型的服务强度p ：曼 0 ( 2 2 + 2 p ) z ( m ，0 ) = a z ( m 一1 , 0 ) + 2 卢玎( 月 + 1 ，o ) + p z ( m ，1 ) ， m o ，”= 0 2 a z ( o ，0 ) = 2 t ； r ( 1 ，0 ) + 2 p z ( o ，1 ) ， m = 1 , l = 0 我们定义联合概率7 r ( m ， ) 的母函数 f ( x ，y ) = 疗( 坍，行弦” i x f 1 ，【y f i m = on o 其中 f ( o y ) = 万( o ，n ) y “；f ( x ，o ) = 万( m ，o ) x “；f ( o ，o ) = x ( o ，o 、。 n = om = o 当i x l l ，b ， 1 时，f ( x ，y ) 是解析的；当y 一定时，f ( x ，y ) 在h 1 时是正则的，在h 曼1 时是连续的，相反当x 一定时，对于y 也有前面的说法成立。有正规条件f o ，1 ) = 1 。 经过直接但复杂的计算( 参见文献 8 ) 可得到关于母函数的方程如下 t ( x ，y ) f ( x ，y ) = a ( x ，y ) f ( x ，0 ) + b ( x ，y ) f ( o ，y ) + c ( x ，y ) f ( o ，0 ) 丁( x ，y ) = 五( 1 一x ) + ( 1 一妄) + 兄( 1 - y ) + ( 1 一号) m ，y ) = 加一争一胛一vx 6 ( x ，y ) = ( 1 一三) 一( 1 一争 蝴一( 1 一 州1 一争 合y ：1 ，代入f 1 ) 式，a ( x v 、：b f x v 1 = 0 ，则( 2 1 ) 式简化为 8 ( 2 1 ) 处理器共享的两类排队模型的研究硕士学位论文 “u 一一j 册川2 孟- y )f(o，0)-筹。,uo 五( 1 + 一二) 1 一 ( 2 2 ) 在( 2 2 ) 式中，当y 斗1 时，我们得到f ( 0 ，o ) = 1 一p 。并且由于对称性f 0 ，o ) = f ( o ，苫) 。 2 3核的零点应用 核的分析：在分析方程( 1 ) 时，t ( x ，y ) 起着重要的作用。由于f ( x ，y ) 的正则性， 对于每一个在单位圆上或其内的数对佤y ) 来说r 0 ，y ) 均为零，这样( 1 ) 式的右边等于零。 这样就提供了我们两个未知函数f ( o ，y ) 和f ( x ，o ) 之i e i 拘 关系式。丁 ，_ y ) 是关于x 或y 的多项式，我们就可以构造两个r i e m a n n - - h i l b e r t 边值问题，分别是关于函数f ( 0 ，_ y ) 和 f ( x ，0 ) 。 在这一部分我们要推导出函数方程( 1 ) 的解，其中核丁0 ，y ) 起着非常重要的作用。 t ( x ，y ) ：丑( 1 一x ) + ( 1 一! ) + 五( 1 一y ) + ( 1 一三) 工 y 因为对每个x ，t ( x ，_ y ) 可看作是y 的二次多项式，这样对一个石值都可能有两个y 值与之 对应，即有t ( x ，y 。 ) ) = t ( x ，y ： ) ) = 0 ，解得；丁0 o ) ，y ) = t ( x 2 ( y ) ，y ) = 0 m ) = 坐竺型季型坚丝 ( 2 3 ) 其中a ( x ) ；a ( 1 一x ) + ( 1 一与 引理1 ：由t ( x ，y 0 ) ) = 0 所定义的代数函数_ y 0 ) ，有4 个实分支点x ，x ：，x ，x 。，且 0 x i x 2 1 x ， x 4 。 证明：由( 2 3 ) 式可得，实分支点既是判别式x = 五+ + 一 ) 2 4 枷= 0 的点。 9 处理器共享的两类排队模型的研究 硕士学位论文 即彳( x ) + ( 万_ ) 2 = 0 或者血2 + 卢。= ( + 七讧 ( 2 4 ) 其中= 2 2 + 2 z ，k = + - 2 4 石：令x = a + b i ，a 、b 为实数，4 - a ( 2 4 ) 式，可推得6 = 0 。 当_ i 取2 石时，a 可取四个值，l l l ，x 。，x ：，工，z 。，且满足x = 0 ，由( 2 4 ) 式可看出 x ，x ：，x ，x 。均为实正数，且由五+ z + k 知1 是在这些根中间的，则得 0 z 1 x 2 1 x 3 z 4 a j(s)=a+t+s-x(ai+,u+s)2-4一g,u， 当s o 时，x ( s ) 可验证为一个递减函数 上 再由二次方程的求根公式及两根之间的关系得： 一墨丝盟巫! ：二坚竺盟巫墅二丝 1 2 咒 x 3 = 兰 l x l x ；墨竺! 巫二巫! 二坚竺! 塑二亟! 二! 丝 2 五 “ = 一 九h 则引理可得证。 同理：女e t ( x ，y ) = o 看作是关于x 的二次方程，得到x 的表达式，引理1 对于函数x f y ) 的四个分支点y l ，y 2 ，y 3 ，y 4 是同样适用的，从而解得： x f y l ：墨竺皇壁! 圭巫坐墨业2 二丝， 上 其中b ( y ) ：五( 1 一y ) + ( 1 一与； 得到： 1 0 处理器共享的两类排队模型的研究 硕士学位论文 胪型巫显盈巫 2 y 32 - = 。 l y l 胪坐巫塑堕地垫 “ y 4 = 。 z y 2 且0 y 1 y 2 1 y 3 y 4 。 引理2 ：当z i x 。，x ：】，对应的两个根y 。 ) = 厕，因此y = y 0 ) ：i x ，x ：】j l ，把x 平面上的区间i x 。，x ：】映射到y 平面上的闭曲线l 上，l 是关于实轴对称的。 证明：因为当z = x l ，石2 时，x = 0 ；当膏0 1 ，石2 ) 时，z 1 ，歹研是 y 0 ) 的复共轭。 注释：莩 或等 _ ( d ) 就是本文章所要研究的排队模型。 2 t 图1 ：模型示意图 用置( f ) ，= 1 ，2 表示时刻t 在j 对中排队的顾客数，则石p ) = 暖，o ) ，x 2 ( r ) ) r o ) 描述了一个状态空间 o ，1 ，2 ) 2 连续时间的马尔可夫链。此模型的服务强度p ：互 1 1 6 墼型堂苎! 盟堕耋苎坠堡型盟竺塞 里主堂垡丝壅 ( 2 2 + 4 + 鸬驴。= 2 丑p 。一1 + 2 五矽，一1 。+ “p 。+ 1 。+ 脚+ l ；m 0 ( 2 2 + 4 + 2 ) p 。+ 1 。= 2 印n + l 。一l + 卸捌+ 声 p 。+ 2 。+ 脚n “。+ 1 ；甩 0 ( 2 2 + 4 + 鲍扫黼l = 2 丑p 。- l 。“+ 劫删。+ m p 。+ 1 ，“+ 脚。“。+ 2 ；m 0 ( 2 2 + 4 + 段咖朋= 2 印册- 】+ 声 p 。+ h + ，如p 。，。“；m 咒+ 1 2 ( 2 a + m + 乜扫枷= 2 卸。q 。+ m p 。“。+ 声屯p 。+ 1 ；n 埘+ l 2 我们定义联合概率p 。的母函数 f ( x ，y ) = 仇。聋”少h 1 ，f y f 1 f ( x ，o ) = z p 。o 矿； 1 0 f ( o ，y ) = p o 。y ”；f ( 0 ，o ) = p o o n ；o 对上面的方程做如下变化： 1 ) ( 2 兄+ 正) p 。= ，p o 肿1 + 声 p h ；玎 1 ( 2 五+ 正加o ”= ，厶o 。“+ 肛p 1 ” ( 2 a + 正) 砂p 。y ”= 正x z p y + 4 y p 。x y “ h = 2n = 2n = 2 2 ) ( 2 见+ 彳) p 。o = 声扫。+ l o + ，妒，1 ；m 1 ( 2 2 + 4 ) x y p 。= 硝y 岛+ 1 0 x ”1 + 鸬z p 。l x “y m = 2m = 2m = 2 ( 2 五+ 衍) x y f 0 ，o ) 一p o o a 一 = 知 f ，o ) - p 0 0 一p l o x - p 2 0 x 2 + 肛一z p 。i x ” y m 2 3 ) ( 2 a + “+ ，如归m = 2 五p 册一1 + 2 印舯l 卅+ 胁p 。+ 1 胛+ 肫p 。卅】；m 0 ( 2 2 + 4 + 鲍) 砂p 。妒y “ m = l = 2 a x y 2 p 。- 1 x ”y 4 + 2 a x 2 y p 。1 。z 。1 _ y “ m = lr n = - i + 彬z p “乒砖”+ 声p 。+ 一“ 4 ) ( 2 2 + 4 + 卢2 ) p 。+ 1 。= 2 丑p 。“。一1 + 五p 。+ 声 p 。+ 2 。+ 脚。“；n 0 1 7 处理器共享的两类排队模型的研究 硕士学位论文 ( 2 丑+ m 十鸬) ) z p 。+ 1 。x ”+ 1 y ”= 2 z x y 2 z p n + l n - i x ”+ l y ”一1 + 2 x 2 y z p 。x ”y “ n - - 1 n = ln = - i + m y z p 。+ 2 2 y + 胁x z p 。+ 1 。+ 1 x i y “ n = 1月矗 5 ) ( 2 旯+ “+ 心驴。+ 1 = 2 印川洲+ 印栅+ 声妒。“剃+ 能p 川。+ 2 ；m 0 ( 2 五十“+ 总泗p 删+ 1 x “y ”1 = 2 a x 2 y e p m - l m + l x “y ”1 + a x y 2 z p 。，妒y “ m = lm = lm = l + - 白y z p m + l r n + l x ”l y ”1 + p r x z p “。”2 m = l m 1 6 ) ( 2 + m + 胁汩删= 2 劫册一1 + 卯卅l 。+ 脚舢+ 1 ；m 珂+ 1 2 ( 2 五+ 触+ 如渺工y = 2 , g v y 2 0 y 1 m = 3n = l m = 3 月= l m - 2 m 一2 + m y p 。+ ，”1 + 缈z z p 。+ r r m y ”1 7 ) ( 2 五+ 照+ 声乞) p 。= 2 五p 。- i 。+ m p 。+ l 。+ 脚。州；以 掰+ 1 2 ( 2 五+ m + 肫) 砂p ，一y = 2 a x 2 _ y p ，m x m - 1 y n + f l y zz p m x m + l _ y ” n = - 3r n f f i l h = 5 m = 1月司m f f i l n - 2 + p 2 x p m 。石勺“ 我们假定m = 2 = ，硝= z ：= 2 p ；再把上面的7 个方程相加可得到如下的结果 ( 2 五+ 2 ) 砂【p 。y ”+ 。+ p 。”+ p m 善”8 + z p 。“x 8 y “ n = 2m = 2m=1，忙l m = l + z z p 。乒”+ p 。乒” = 2 触【p ，。乒”+ p m + 一”“ m 甸胆1n - - 3 m = lm = l m = l + 妻呈p 肿，m 一 + 2 a y 2 e 宝p 。，“+ 妻以。，“+ 杰笼p 。7 “ + y p l 捌4 + p m 声“+ p 。+ l 一”+ z p 。2 “+ 2 y “+ p m + l m + 广l y “ n=2，#2 m l# l 1 8 竺里塑苎皇塑堕耋生坠堡型堕里塞 堕主堂垡笙塞 zn-2 ” + z z p 。+ t ”i y ”+ z z p 。+ ，8 ” + ， p 。+ “+ e p ， + 妻p 。，“十艺p n + l n + 一“+ “+ 主p 声m + z + 妻篁p 。n + z z p 。+ 一勺”1 】+ 缸了p 痧“+ 幻2 p 。一y + z p x y ”1 + p 。“一”“ 考虑至整个服务系统的对称性：我们认为a x 2 y ，铆2 在意义上是相等的，即 _ z 2 y = 五叫2 ，则上面的等式可变为 ( 2 a + 2 t ) x y e p o 少+ z p 。庐”+ z p ，。工一y + p n + l n x n + l y ”+ z p 。“x “广1 n = 2m = 2m = ln = lm = l - 2 n - 2 + p 。乒“+ p 。一” = 触2 y p 。”+ y p 。+ 一”1 m ；jn = ln = 3m - im = l m = l 月一2 一2 + p 。一，乒“专”+ z p ，。一+ z p 。一声”“+ p 一一勺n - 1 n = 3 m = lm - 1脚m - , 3n = l m 一2 + 幻2 【p 。0 ”y , - 1 + z p n + l n _ i x ”l y ”1 + p ，。- 1 y ”1 + z p 。- 1 ，x ”l y “ m = l忙1m = 3n = l d n - 2 + z p 。+ p , n - l n ；c ”+ p ，4 + p ，。萨”1 + p m + l ” m ；】i 了m 司 n = 2 卅2 m = l - 2on - 2 + z p m 乒”+ p 。+ 一”1 + p 。+ ，乒”+ p 。”“ h = 1 m = lm = 3n = 1月_ 3m = l + x p o n + l y “+ p m l x “y + e p 。m + l x “_ y “+ p 。+ 1 x n + l y ”1 mm = im = lb l r n - 2n - - 2 + p m r ，l + 声 ”2 + p 。”+ p 一一y n + 1 m = lm , - 3n = ln = 3m = 1 + 触2 一p 。矿y “+ 细2 p 。y ”+ 雕p o n + l y ”1 + p 删x ”1 再继续对上式做变化得到：( 2 a + 2 f 1 ) x y f ，y ) 一p o o p 1 庐一p o l y 1 9 p y m z 航p 。d + ” y m x hmp m “。d + +mmp 。l + m y 肛 x 十p 。稍 r 【y 2 x丑 i i 竺堡墨苎皇塑亘壅塑坠堡型塑堑塞 一坐垡兰；生一 + 宝p 。一”l + 艺篁p 。一一7 “ + 匆2 宝p 一声”1 + 芝p 。，”一 + 妻艺p 。、一7 * ，+ 妻p ，。乒“+ z 。，p m - l m + lq - 萎善n - 2 p 。乒”】 + 删【妻p 。一十艺p 。一“+ 妻p 。x “y ”+ 妻p + 2 x “y 一p 。z m + l y “ + z z p 。”“+ z z p 。t 乒”“】 + 膨 妻“+ 艺，+ 耋p 一一7 “+ 萋以“”“1 + 萎p 一7 “ t t = 2 m埘ml 肛i ”一 + p 。”+ z z p 。+ 一“ + a x 2 y 艺p y + 细，：宝p 。“+ 肛芝p 。“+ 芝p 。，一“ ( 2 a + 2 b ) x y f ( x ，y ) 一p o o p l o x p r a y ：触2 y f ( x ，) 一艺p ，石”一p o 。】十匆2 旷 ，y ) 一p 。x 7 ”一p 0 0 + ，【f o ，y ) 一z p o 。y “一p 一p l o x p 2 声2 一p 1 r c y + 声啊【f o ，y ) 一p 。o x ”一p o 。一p o 一p 2 一p i 】 + a x 2 y 妻p n _ y n + 五掣2 薹p 。x ”_ y ”+ 肼萎p 。“1 + 删丕“一“ n=l”2i “叶 。 把下面的三个式子带入上面的式子： 2 a x y p 0 0 = 2 , u y p l 一+ 2 f l x p m y ( 2 2 + 2 ) x y p l o x = 2 , u y p 2 0 x 2 + p x p x y + a x 2 y p 0 0 ( 2 3 + 2 p ) x y p 。t y = 2 u y p 。2 y 2 + ) p n 习，+ 允驯2 p 0 0 得到 【( 2 丑+ 2 ) 习，一。x 2 y a x y 2 - # y 一, u x f ( x ，y ) 一( 2 x + 2 p ) x y p 0 0 ：一取2 y 妻p 。x “y ”一以2 即o o - a 掣2 薹p 。y l 枷2 p o o - 荟p o l 朋炳。 m 1 月5 i 一 ：缸2 y c 妻p 。- l m x “y ”+ 芝p 。，“+ 荟萎n - 2p ，一。x 州y “+ 善p 一，y “m = l m = l2 ” 竺墨璺苎皇堕亘鲞苎坠堡型! 塑 堡主堂垡堕壅 胁2 ) ，善x “y “+ 细2 d o o x ”y “+ 2 d y p 2 0 x 2 + 脚。俐+ 2 x 2 y p 0 d + 2 聊2 + g y p l + 五掣0 0 + ，优p 。肿州+ 工p 。h 一肼1 即得到： ( 2 + 2 , u ) x y 一2 x 2 y 一，t 列2 一, u y 声掰】f ( x ，y ) = 一缈妻m “一脚。一聊，声p x 芝p , o x m - 卿0 0 - 卿。 + 垆2 2 + 脚。2 + 肛杰+ “+ 窆p 庐m + l + ( 2 x + 2 u ) x y p 。 即： ( 2 五+ 2 ) 习，一a 蔗了一匆2 一，一u x f ( x ，y ) 2 叫妒( o ，y ) 一舻o ，o ) + 御2 0 x 2 + 卿2 + 膨p 。“+ p y 艺p 卅+ l 萨“ + ) p l o x + z x p o y + p 熠o o + f l x p o o + ( 2 2 , + 2 p ) x y p 呻一