（计算数学专业论文）运筹学中模型优化与算法研究.pdf

华中科技大学硕士学位论文 摘要 本文主要研究分析了随机服务和优化排样两类系统中的优化模型与算法，并 且运用v c 抖6 o 或m a t l a b 6 1 进行了仿真实验。这两类问题涉及到运筹学，数据 结构，算法分析，计算机图形学，人工智能，计算机网络，图论等多门学科的知 识。这两类问题在现实生产生活中大量存在，因此研究这两类问题的优化模型和 算法仿真有着极大的现实意义和社会价值。 通过随机服务理论在快餐店，银行，视频点播，网页访问中的应用研究，我 们建立了在这些领域里的不同的数学模型，并且分析了其算法和试验结果。其中 我们重点研究了排队理论在视频点播系统中的应用。我们根据节目的流行度分成 热门和冷门两类，提出了基于流行度的视频流控制方法，分析了系统的瞬间转移 概率，给出了不同流行度视频流的带宽预测公式。仿真结果表明这种方法也可以 有效节省服务器的资源，提高视频的服务水平。这种排队分析研究方法可以适用 于其它类似的随机服务系统。 排样问题广泛存在于产生实践中，我们主要研究矩形优化排样，矩形优化排 样就是将一系列矩形零件合理地排放在原料中，使原料的利用率最高，并且要满足： ( 1 ) 每个小矩形互不重叠，( 2 ) 必须排放在原料内，( 3 ) 满足一定的工艺要求。这是许多 行业都迫切需要解决的问题尉于非矩形零件我们可以通过计算机图形处理技术 将一个或几个零件套排在一个包容矩形中，然后对包容矩形进行排样，从而可以转 化为矩形件排样问题，可见矩形件优化排样问题的解决具有十分重要的意义。我们 建立了优化的数学模型，并且运用启发式算法和模拟退火算法求解了矩形优化排 样问题。求解结果表明了这些算法的可行性，鲁棒性和有效性。 关键词：排队论数学模型矩形排样 优化算法计算机仿真 华中科技大学硕士学位论文 a b s t r a c t q u e u i n gt h e o r y a n d p a c k i n gp r o b l e m i n o p e r a t i o n a l r e s e a r c ha r e m a i n l y c o n s i d e r e d a n ds i m u l a t et h e i rm o d e lw i t hv c 抖6 0a n dm a t l a b 6 1 t h et w os y s t e m s r e l a t et om a n ys u b j e c t s ，s u c ha so p e a r t i o nr e s e a r c h ，m a t h e m a t i cp r o g r a m m i n g ，d a t a s t r u c t u r e ，a r i t h m e t i ca n a l y s i s ，c o m p u t e rg r a p h i c s ，a r t i f i c i a l i n t e l l i g e n c e ，c o m p u t e r i n t e r a c t t h et w op r o b l e m se x i s ts om u c hi no u rr e a l i s m ，s oi ti sv e r yi m p o r t a n ta n d s i g n i f i c a n tf o ru st h a tw es t u d yt h e i rm o d e la n do p t i m a la l g o r i t h m w es e tu pm a n y m a t h e m a t i cm o d e la n d a n a l y s i st h e i ro p i m a la l g o r i t h mt h r o u g hq u e u i n gt h o e ya p p l yt o b a n ks e r v i c e ，n o s h e r ys e r v i c e ，v i d e o - o n - d e m a n ds y s t e ma n di n t r a n e t e s p e c i a l l yw e a n a l y s i st h ev i d e o o n d e m a n d w i 也t h er a p i dp e r f o r m a n c ei m p r o v e m e n t si nl o w c o s t p c s ，i tb e c o m e si n c r e a s i n g l yp r a c t i c a la n dc o s t e f f e c t i v et o i m p l e m e n tl a r g e - s c a l e v i d e o o n d e m a n ds y s t e m sa r o u n dp a r e l l e lp cs e v e r s b u tt h e s es y s t e m sa l lr e s e r v ea l a r g eo fs y s t e m sd e v i c er e s o u r c e w ei n t r o d u c et h ew a i tt o l e r a n c ec h a r a c t e r i s t i cw i t h n l m m m o d e lf o r s c h e d u l i n g i nv i d e o s y s t e m s a n da n a l y z ei t w es h o wf o u r p a r a m e t e r st h r o u g hs i m u l a t i o nt h a tt h ep r o p o s e ds c h e m e ss u b s t a n t i a l l yo u t p e r f o r mi n r e d u c i n gt h ev i e w e rt u r n - a w a yp r o b a b i l i t ya n dp r o p o s et h es c h e d u l i n gs c h e m ec a l l e d m a x i m u md e f e c t i o n p r o b a b i l i t y , i ti sp r o v e d t ob er e a s o n a b l ea n d p r i o r i w ed e a lw i t l lar e a l p r o b l e mo i l t h e p a c k i n g o fr e c t a n g l e s s y s t e mw i t ht h e i n t e g r a t e da p p l i c a t i o no f s i m u l a t e da n n e a l i n g f i r s t ，w ef o r m u l a t et h em a t h e m a t i c m o d e lo nt h e p a c k i n go fr e c t a n g l e so fs y s t e m s e c o n d w eg i v et h es t e p so ft h e a l g o r i t h ma n dc o m p a r et h eg e n e t i ca l g o r i t h mw i t ht h es i m u l a t e da n n e a l i n ga l g o r i t h m f i n a l l y ，u n d e rt h eo p t i m a lm o d e lo f t h er e a ld a t a ，w eg e tt h es a t i s f a c t o r yr e s u l t i nt h i s p a p e rt h ep r o b l e mo fc a l c u l a t i n go p t i m a lp a c k i n gp a t t e r n so fs m a l lr e c t a n g l e so na p a l l e t i sc o n s i d e r e d w ep r o p o s en e wh e u r i s t i c sw h i c ha r eb a s e do nt h e4 - b l o c k s t r u c t u r eo fp a c k i n gp a t t e r n sa n db u i l dt h em a t h e m a t i c a lm o d e l b yc o m p a r i n g ，t h e s o l u t i o n so ft h en u m e r i c a l e x a m p l e ss h o w t h ee f f e c t i v e n e s so ft h i sa p p r o a c h k e y w o r d s ：q u e u i n gt h e o r y m a t h e m a t i cm o d e l p a c k i n g p r o b l e m o p t i m a la l g o r i t h m i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承 担。 学位论文作者签名 p 吞髫丰易 f l e a ：扫d 妒年，7 月r 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密d ( 请在以上方框内打“4 ”) 学位论文作者签名：p 啄蹋牢荔 日期：泓降；月p 日 指导教师签名：咯岖 日期：甲年弓月，。e t 华中科技大学硕士学位论文 1 1 随机服务系统理论概况 1绪论 经典随机服务系统理论，即排队论( c f 1 - 5 ) ，源于e r l a n g 关于电话的研究。 第二次世界大战后得到迅猛发展，成为随机运筹学与概率论中最有活力的研究课 题。它不仅建立了比较完备的理论体系，而且在军事，生产，经济，管理，交通， 通讯，网络等领域得到了广泛应用( c f 2 1 _ 【3 0 ) 二十世纪中期以后，随着计算机通讯网络，柔性制造系统( f m s ) ，异步传输 模式( a t m ) 等高新技术领域的发展，提出了大量的复杂系统设计和控制的问题。 这些系统的行为通常依赖于随状态而变化的参数，经典的排队模型在处理这类问 题时表现出了极大的局限性。休假排队研究正是在这种背景下于2 0 世纪7 0 年代 产生了。作为经典排队系统的推广，休假排队中允许服务台采取在各种时候不接 待顾客的策略，这些暂时中断服务的时间统称为休假。近2 0 年来，为适用多层次， 变动因素，随机环境等系统分析的需要，随机模型的研究已经从主要依赖指数分 布发展到了广泛使用相型( p h ) 分布的新阶段。 本文根据对快餐店，银行，视频点播系统，网页访问中四个领域里随机服务 模型的分析，得到了一些新的研究方法，即用统计计算方法来刻画排队系统的总 体性能。从而使我们更好的控制和掌握类似的排队系统，为我们的生活和生产服 务。 1 2 排样系统 优化排样系统就是要解决生产实践中的一维下料问题，二维排样问题，三维 装箱问题! 这类问题我们统称为排样问题( p a c k i n gp r o b l e m ) 由于这类问题都是 n p h a r d 问题，所以我们主要是用一些现代常用的优化计算方法，如遗传算法，模 拟退火，启发式，禁忌搜索等算法来求解实践中的一些具体问题的近似最优解。 从而能使实际生产者提高其生产效率和经济效益! 最大限度地节约材料，提高材 料利用率是生产中提高效益的一个重要手段。而由于排样问题的广泛存在， ( e 1 1 2 一 1 3 如下料问题，报刊排版，服装裁减等，都需要在可接受的时间和客观 条件下得到最优和近似理论最优的解，因此解决这类问题有着重要的理论意义和 华中科技大学硕士学位论文 现实意义。 优化排样问题的理论研究涉及到线性规划( l p ) ，整数规划( i p ) ，动态规划( d p ) ， 计算机图形学( c g ) 及人工智能( a i ) 等多种学科。此类问题由于具有广泛和真实的 应用背景，所以许多国内外学者对此进行了长时间的研究和尝试工作。已经尝试 过的主要方法主要有启发式方法，模拟退火方法，遗传算法，基于学习的方法等。 零件排样布局的优劣，直接与产品的成本及企业经济效益有关。该问题同益 引起应用部门和学术界的兴趣。目前国内外已有一些关于一维，二维和三维排样 问题的软件，它们多半是提供交互排料和自动排料两种功能，但是从排样的效果 上来看，自动排料并未形成相对于人工排样的非常明显优势，这说明自动排样算 法还有进一步研究的必要，实际生产中还非常需要更多更好的排样软件。这也正 是我们今后不断努力奋斗的方向。 排样问题在现实生活和生产中大量存在。我们主要研究以下一些排样问题： - - 维( 1 - d ) ： f f 排样问题j 二维( 2 一。) 。 j f | l 三维( 3 一d ) - 这里我们主要考虑钢旨下料问题 生产规爿奈篓冀黝 零件形状 f 一般切割 矩形俐2 级切割 3 级切割 异性州篇恐 生产要非端笔篓黧：。 我们现在主要还是考惑装箱问题 从我们对排样问题的分类很明显可以看出来，二维排样问题是我们研究的重 点。其中矩形排样是我们的重中之重。我们研究这类问题最重要的原因就是要最 大限度的节约材料，提高材料利用率。 矩形件优化排样问题就是将一系列矩形零件q ，吼，合理地排放在原料p 中使原料的利用率最高，并且要满足：( 1 ) q d ，互不重叠；i ，j = 1 2 ，n ( 2 ) q 必须 排放在p 内；f - 1 2 ，h ( 3 ) 满足一定的工艺要求这是许多行业都迫切需要解决的 2 华中科技大学硕士学位论文 问题对于非矩形零件我们可以通过计算机图形处理技术将一个或几个零件套排 在一个包容矩形中，然后对包容矩形进行排样，从而可以转化为矩形件排样问题，可 见矩形件优化排样问题的解决具有十分重要的意义 排样问题的上述一般表示可以归结为数学规划问题，也可以归结为以零件排 放状态为结点，以废料增加为权值的带权有向图中的最短路径问题。但是由于约 束条件很难用可操作的数学公式表达，使得排样问题的求解不能套用现有的数学 规划中的优化算法求解。此外，图论中最短路径问题的已有算法，只对图的结构 固定且清楚，一个状态结点的后续结点个数有限的情况有效，如对矩形零件的排 样适用，但对异性零件就不适用。 从数学计算复杂性理论可知矩形件排样的优化问题属于n p 完全问题，但是 由于实际生产的需要，不少中外学者提出了一系列的算法现代优化计算方法主要 包括禁忌搜索( t a b us e a r c h ) ，模拟退火( s i m u l a t e da n n e a l i n g ) ，遗传算法( g e n e t i c a l g o r i t h m s ) ，神经网络( n e u r a ln e t w o r k s ) 干 1 拉格朗目等算法。这些算法涉及生物进 化，人工智能，数学，物理，神经系统和统计力学等概念，都是以一定的直观基 础构造的算法，我们称之为启发式算法。这里我们主要简单介绍遗传算法和模拟 退火算法。 遗传算法是在7 0 年代初期由美国密执根( m i c h i g a n ) 大学的h o l l a n d 教授发展 起来的。h o l l a n d 于1 9 7 5 年发表了第一本比较系统论述遗传算法的专着 ( ( a d a p t a t i o ni n n a t u r a la n d a r t i f i c i a ls y s t e m s ) ) 。遗传算法的主要技术问题：( 1 ) 解 的编码和译码。遗传算法的基础工作之一就是解的编码，只有在编码之后才可能 有其它的计算。( 2 ) 群体的选取和计算群体的大小。一般采用随机产生初始群体 或通过其它的方法构造一个初始群体。( 3 ) 适应函数的确定。一般情况适应函数 同目标函数相关，以保证较优的解有较大的生存机会。( 4 ) 三个操作数：种群选 取操作数，交配操作数，变异操作数。种群选取操作数是以一个概率分布轮 盘赌的形式选取个体而产生的。交配操作数主要考虑交配规则，一般的交配规则 有双亲遗传法，主个体副个体规则，单亲遗传规则等变异操作数是扩大染色体选 取范围的一个有效手段，通常遗传算法实现变异的方法是赋予每一个基因一个相 对比较小的变异概率，通过随机模拟而决定一个基因是否变异。 模拟退火算法的思想最早是由m e t r o p o l i s 在19 5 3 年提出来的。k i r k p a t r i c k 在 1 9 8 3 年成功的把这种思想应用到组合最优化中。模拟退火算法是局部搜索算法的 扩展。它不同于局部搜索之处就是它以一定的概率选取领域中费用值最大的状态 理论上讲它是一个全局最优解。 华中科技大学硕士学位论文 模拟退火算法的主要技术阀题：( 1 ) 解的形式和领域结构。解的表现形式直 接决定于领域的构造。( 2 ) 温度参数的控制。( 3 ) 算法终止原则。理论上是用一 个马尔可夫链描述模拟退火算法的变化过程，因此应该具有全局最优性。实际中 的退火算法是一个启发式算法。它有很多的参数需要调整，如起始温度，温度下 降的方案，固定温度的迭代长度及终止规则等，这些都需要人为的调整。但是人 为的因素造成计算结果的差异| 生很大。解决这个矛盾的方法主要是通过大量的数 值模拟计算，从中选取比较好的参数搭配。 1 3 本文的研究方法和研究意义 本文主要对随机服务系统在快餐店，银行，网页访问，视频点播系统等中的应 用模型进行分析，然后用v c 6 0 或m a t l a b 6 i 进行了仿真试验。一般情况下，我 们都是用以下三个指针来评价排队系统的性能：( 1 ) 顾客在系统内的平均逗留时f n j 。 ( 2 ) 系统内的平均顾客数。( 3 ) n 务员的负荷率。本文给出了一种新的刻画评价排队 系统性能的指针，即偏差估计的比较。我们根据节目的流行度分成热门和冷门两 类，提出了基于流行度的视频流控制方法，分析了系统的瞬间转移概率，给出了 不同流行度视频流的带宽预测公式。并且仿真试验表明此方法适宜很多随机服务 系统的分析和研究。 本文还用分支定界算法，启发式算法，模拟退火算法应用于一维下料问题和 二维矩形排样问题。通过在v c 6o 或m a t l a b 6 1 上的仿真试验表明这些优化算法 是行之有效的。 4 华中科技大学硕士学位论文 2 1 基本知识简介 2 随机服务系统 在研究一个系统的结构与运行的最优化方案时，首先是根据人们的需要提出 一个目标，然后调动有限的资源，以最佳的途径朝着这个目标推进。但是近代科 技的日新月异，使得我们研究的对象本身越来越复杂，所以我们必须要依靠一套 有条理的方法来了解和掌握客观的规律，进而拟定出最佳的途径。随机服务系统 理论已经广泛地应用于国民经济和生产实际中，具体的例子包括通信系统，交通 系统，存量系统，产生系统，计算机网络系统等( c f 1 4 - 【1 5 ) 。在这些领域里随机 服务理论和最优化的方法结合就可以成为一个强有力的管理科学工具。 主要数学记号： f 表示第i 个顾客的到达时间 x 表示第i 个顾客的服务时间 砒表示第i 个顾客在系统中的等待时间 s ，表示第i 个顾客在系统中的逗留时间( 包括等待与服务) ，s ，= x ，+ w z + l 表示第i 十1 个顾客与第i 个顾客到达系统的时间间隔 b ( f ) = p ( t 口 = p 卜 口 则称x 的分布是无记忆性的。 按条件概率的定义，我们有 尸缸 口+ x 卢 = ! 生生；群= 错 如果随机变量x 是无记忆性的，那么有 p b a + 3 = e x d p ( x 】 反之，如果随机变量满足上面的等式，那么该分布是无记忆性的。 指数分布具有以下性质： 设x ，y 分别是参数为口，口的指数分布随机变量，且相互独立，则 1 ) z = m i n x ，y 的分布也是指数分布，且参数为口+ 卢： 2 ) p x 0 ) 的p o i s s o n 过程。 p o i s s o n 过程定义( 2 ) ： 一个计数过程 ( r ) ，0 ) 如果满足 2 ) ( r ) ，r 0 ) 是独立，平稳增量过程 3 ) n ( t ) 满足以下两式 p n ( t + h ) 一n ( t ) = 1 - 2 h + o ( 矗) ；p n ( t + h ) 一n ( t ) 2 _ o ( h ) ( 这表示在充分 小的时间间隔里，最多有一个事件发生，而不能有多于两个的事件同时发生) 则称计数过程n ( t ) 是参数为五( 旯 0 ) 的p o i s s o n 过程。 定理：p o i s s o n 过程定义( 1 ) 与p o i s s o n 过程定义( 2 ) 等价。 p o i s s o n 过程的性质： 1 ) 令 n 1 ( f ) ，f 0 ) 和2 ( f ) ，0 分别是具有参数为a 和的独立的p o i s s o n 过程，则 n ( t ) = 1 ( f ) + 2 ( r ) ，f 0 是参数为口+ 的p o i s s o n 过程。 2 ) 对于参数为 的p o i s s o n 过程，假设发生的每个事件独立地以概率p 做了 华申科技大学硕士学位论文 记录，未做记录的概率为1 一p 。令，( f ) 是到r 为止被做了记录的事件数，n 2 ( t ) 是未被记录的事件数，则l ( f ) 和2 ( r ) 分别是参数为p 兄和( 1 一p ) 五的p o i s s o n 分 布，而且它们相互独立。 离散时间的m a r k o v 链( d t m c ) 一个随机序列 x 。) ，如果下一个状态值是x 。的概率仅依赖于现在状态的取 值而与以前的状态无关，那么这个随机序列 爿。) 就称为离散时间的m a r k o v 链。 它的数学表达式为： 研x n + = x x i = 置，x 2 = x ：，瓦= l - 尸【以+ ；= x 蜀= n 离散时间 的m a r k o v 链有一个特点，那就是每隔一个单位时间都要发生一次状态转移，转 移概率是任意的。离散时间的m a r k o v 链逗留在某一状态的时间服从几何分布， 连续时间的m a r k o v 链逗留在某一状态的时间服从指与起始时间数分布。无论是 连续时间还是离散时间的m a r k o v 链，只要状态转移概率与起始时刻无关，我们 就称之为齐次的。我们研究的都是齐次的m a r k o v 链。 连续时间的m a r k o v 链( c t m c ) 定义：对于随机过程“) ，若对于一切整数1 1 和序列 f i ，f 2 ，f “( f 1 ，2 0 ) l i t t l e 定理：在排队系统中的平均顾客数= 顾客的平均到达率平均逗留时间 即日( f ) 艇 j ， 。 系统稳定时的逗留时间是指顾客花在系统中的时间，包括等待时间和服务时 间。平均逗留时间为： 9 华中科技大学硕士学位论文 酬= 妻n = 0 驯w ) 刮州刮= 字薹( 川) p ” 进一步可以得到逗留时间的参数为( 1 一p ) 的分却 同样也可以得到等待时间的参数分布 等待时间分布的l a p l a c e 变换为 它的l a p l a c e 反变换为 只= 1 一p e 州1 9 ”，0 0 ) = 辫4 - j( 【一口 “ 2 3m g 1 模型分析 c 卜卅筹 s + ( i d i f ，( ，) = ( 1 一p ) 占 ) + “p ( 1 一p ) e 一1 9 ) 口 在m g 1 模型中，顾客到达服从参数为丑的p o i s s o n 过程，服务时间有一般 分布函数b ( t ) ，其阶矩和二阶矩和l s t 记为： 去= r 枷( n6 ( 2 = f ，2 柏( 吐日) = f e 。拈( 吐 ( 2 - 3 1 ) 假定达到时间间隔与服务时间相互独立，使用先到先服务( f c s f ) 排队规则。 l ( t ) 表示时刻t 系统中的顾客数，也称队长。以三。m 1 ) 表示的n 个顾客离去后瞬 对系统内的预客数， 上。 1 ；- g , y ol ( t ) 的嵌入m a r k m 壁，江，”1 1 满足下列递 推关系： 。+ = 2 三1 二彳 1 ( 2 - 3 - 2 ) ? t o 华中科技大学硕士学位论文 a 是一个服务时洄内到达的顾客数，有分布和均值 a ，= 跗= 肛r 掣e “卿) = 吣 ( 2 3 - 3 ) e ( 爿) ：兰：p “ ( 2 3 4 ) 尸称为系统的荷载或流通强度。非负整值上的m a r k o v 链 。，n 1 有转移概率矩 阵 尸 d 0口l d 0d 1 盘o 以下设p 1 ，l 表示l 。的极限，汜 口2d 3 啦口3 d i口2 g l ol 万，。p ( l 2 ) 21 i n p l 。= m ，= o 1 ， n 2 ( 万o ，万，) 定理2 3 1 当p 1 时，离去时刻的稳态顾客数l 有母函数 讹) = 砉甲= ( 1 - p 而) ( 1 - 瓦z ) b 丽* ( g 二( - 1 - z ) ) 托团。( 2 - 3 - 5 ) 定理2 3 2 在m g i 排队中，当p 1 时 z t = p k ，k 0 ( 2 3 6 ) 定理2 3 3 当尸 1 时，系统中排队等待顾客数q 有母函数 q ( z ) 2 瓦( 1 - 而p ) o - z ) ，( 2 - 3 - 7 ) 当p 1 时，w 表示稳态下到达顾客的等待时间，即从到达时刻算起，直到进入 1 1 华中科技大学硕士学位论文 服务台开始服务的时间，矿+ ( j ) 表示w 的l s t 定理2 3 4 当p 1 时，w 有l s t = d s 怒蒜s ，引 一 il 一廿l ” 平均等待时间为 即，= 篙= 却， ( 2 3 9 ) 定理2 3 5 在m g 1 排队系统中，忙期d 的l s t 满足函数方程 d ( s ) = b + ( s + 旯( 1 一d + ( 5 ) ) ) ( 2 3 1 0 ) 平均忙期为 e ( 。) = f 1 鬲= 而1 ( 2 3 一i i j n 策略是这样一种休假机制，直到积累发生第n 次到达时开始一个薪的忙 期。n = 1 时就是经典的m g 1 系统。现在恰好等于n 个到达时间之和。n ，策略 是诸多通称为“控制排队”策略的一种，曾由b a l a c h a n d r a n ( 1 9 7 3 ) 【3 4 l ， h e y m a n f 3 5 】f 3 6 】，与s o b e l ( 1 9 8 2 ) ，s h a n t h i k u m a r ( 1 9 8 i ) 1 3 7 等使用不同的方法研 究。n - 策略有明确的应用背景，设想从休假到忙期的状态转换需要一定的费用， 这样一来，系统中只有一个和少数几个顾客就频繁的实施转换，从经济效益上 看，未必是明智的。选择使系统收益最大的阀值n ，当积累到n 个顾客时才实 现从假期到忙期的转换，就是一个典型的排队控制问题。 忙期开始时系统内恰好有n 个顾客，g 的母函数和均值是 蜴( ：) = = 。，e ( q ) = n l 2 3 1 2 j 嵌入在离去时刻的队长 l 。，n 1 是m a r k o v 链，其转移概率矩阵是 2 华中科技大学硕士学位论文 其中 00 口0口】 c 0 口o a , v i 口n 2 o i t 3 n 盘一l 盘，= f o 孚“蝴，( 2 - 3 - 1 3 ) 返一矩阵仍属于m g 1 的边界状态变体。第一行元素是 一，= 之i i i ：岁：n 一- 。2 ( 2 - 3 - 1 4 ) 定理2 3 6 当p 1 时，n 一策略m j g t 系统中稳态队长可分解成独立随机变量之和 、= 上+ 岛，其中l 是经典无休假m g 1 稳态队长，母函数如式( 2 - 3 5 ) ：附加 队长l d 有母函数有 - 肛) 3 而1 - - z 2 - 3 1 5 ) 定理2 36 表明，虽然休假长度与到达过程不独立，但分解定理的结论仍然成立， 直接计算给出 蚴= 等，新篙+ 了n - i ( 2 - 3 - 1 6 ) n - 策略m g 1 中忙期d ，的l s t 和均值是 啪) = 叭s 北e ( 域) = 鬲n 丽，( 2 - 3 - 1 7 ) 服务台只有工作和休假两种状态，休假长度有n 个到达间隔组成，服从e r l a n g 分布，有l s t 和均值 v ( 5 ) ：( l ) ”，e ( y ) ：_ n 。( 2 。1 8 ) 以4 - j丑 从一个忙期结束开始，到随后的另外一个一庀期结束的时刻为止的时间称为一个忙 华中科技大学硕士学位论文 循环，忙循环的长度有均值 i n 十而n = 而n ( 2 - 3 - 1 9 ) z ( 1 一p ) 五( 1 p ) 稳态任意时间系统处于工作和休假状态的概率分别是 p 。：墨盟一：蚴，：璺兰) ：( 2 - 3 - 2 0 - - v j 1 - p ) 如5 葡而酉两2 砖肌。而再面i 2 n 一策略m g 1 中的休假时间v 依赖于到达过程。因此，顾客的等待时间与该顾客 到达时刻以后的输入间隔不在是相互独立的。由于指数分布的完全随机性，在休 假期内到达的n 个顾客中，任一顾砻恰为第k 个到达者的概率为n k ：1 , 2 ，n 第一个到达者的等待时间是n 一1 个到达间隔，第二个到达者的等待时间是n - - 2 个到达间隔与一个服务时间之和，如此等等。最后，第n 个到达者的等待时间是 n 一1 个服务时间。a v 表示事件“到达发生在休假期”，条件等待时间的l s t 是 哪) = 专蓑( 南“一邗。) j = 专( 熹) 五一( 丑+ s ) i b ( 5 ) 】 ( 2 3 2 1 ) 定理2 3 。7 当p 聊 其状态瞬时强度图如下： 五 五五 五五 聊+ ( n m ) r 图2 4 1 具有不耐烦用户的m i m m l o o 状态瞬时强度转移图 j 6 华中科技大学硕士学位论文 由生灭过程有如卞的平稳解 去( 鲁) ，”= 。1 ，：m 土仁1 m ! ：芝! ，疗，。 ! 、7 ( m l a + r ) ( m p + 2 r ) ( m t + ( n m ) r ) 其中p 。由p 。= l 确定。在实际中我们采用近似计算法计算p ，当”充分大时 # = 0 有 其中p ：尘p ，行“ p 肿m = m ”p ”8 pp 竺：旦：! ! m e ( 1 + 妒) ( 1 + 2 妒) ( 1 + n o )r e ! n ! p ” 眦飘等待概率= 弘。亲意。= 譬 平均等待队长为： 丙= 扣薹篙胪警 这种具有不耐烦用户的排队系统，单位时间平均损失的用户数为 一 = n r p 。= n r = l 单位时间被服务完的用户数为： 一， 2 4 4 视频节日分类 这里我们将视频节目分为热门与冷门两类流行度，根据节最的流行度的不同， 限制并发服务的视频流数量，即对每类流行度的节目设定个阈值。当新请求到 达时，系统检查该类节目流的服务数量是否到达闽值，如果到达阈值，则拒绝服 务，否则，为不同流行度的节目预留网络带宽，以保证节目播放的q o s 。如果服 务器不能够预留节日所需要的带宽，则拒绝接收该请求，否则，根据节目流行度 华中科技大学硕士学位论文 选择不同的播放方案，对热门节目按e p s 广播方案，对于冷门节目按点播方案。 下面我们来详细说明这种基于节目流行度的带宽预留算法。 由于视频节目的v b r 特胜，每个节目所需要的带宽是有差异的，我们设计 的系统可以为不同的节目预留不同的带宽。另外，一个流并不总是处于最大消耗 带宽的状态，如果按照最大带宽预留，服务器的利用率是很低的。为了提高服务 器利用率，可以用如下预留计算方法。 冷门节目的预留带宽为： c p r e ：口+ c 。+ b + c 口。 热门节目的预留带宽为： c ，。= ”+ ( a + c 。+ 6 + c 。) 其中，c 。、为一个节目所需要的最大带宽：e 。为平均带宽；d ，b 是两个大于零的 常数，且满足：a + 6 = 1 ， 为用播放一个热门节目所需要的信道数。这里信道 ( c h a n n e l ) 是指将传输一个视频流所需要的服务器及网络资源。 2 4 5 视频节目的阈值 视频点播系统是一个具有单一控制服务器并能提供多服务的双队列排队系 统，对节目的请求遵从p o s s i o n 分布。根据排队论的生灭模型，系统状态可以由 m a r k o v 链描述，具有状态空间q = ( n 1 ，n ! ) ：0 ”1 正，0 l 疋，n + h 1 + n 2 c 。 其中 ，”：分别表示系统目前已经被点播的热冷门节目的数量；c 是系统能同时服 务的最大信道数，z 为热门节目的阀值，l 为冷门节目的阈值。 按照( 图2 - 4 2 ) 可以简单分析基于不同流行度的多队列用户视频点播系统。 整个系统分两个阶段( f i r s ts t a g e ，s e c o n ds t a g e ) ，当第一个用户以参数为兄的 p o i s s o n 分布进入系统，由于节目的不是用户所喜欢的或其它原因，用户以概率p 离开系统，也就是说用户在以概率1 一p 。进入系统准备接受服务。因此当同时有n 个用户进入系统时，就会形成如图2 - 4 2 所示的状态。由于p o i s s o n 流的合流还是 p o i s s o n 流，因此系统的排队模型并没有变。 l r 华中科技大学硕士学位论文 f i r s ts t a g es e c o n ds t a g e & m m m ，m 图2 4 2 基于不同流行度的多队列_ f 1 = j 户视频点播系统 从数学上证明了计算阻塞概率的公式，但仅适用于单播系统，不适合具有e p s 广播方案和单播方案的混合系统。假设只要系统资源容许，对热门节日的阈值e 不 作限g o ( e 1 6 1 ) ，我们改进了计算拒绝服务概率的算法，给出了新的计算公式： b ，：旦c 盟 ( 2 - 4 - 1 ) 6 ， z u d t i c + y s i 最、= _ 殳一 g f - 1 其中，& 为热门节目阻塞概率：& 为冷门节目阻塞概率。 b 【f 】= p ，疋! + p i 一( i 一疋) !疋i c 一1 b i 】= 0 , 0 i = 1 ) 用边际分析法有：f ( m 4 ) = f ( m + + 1 ) 且f ( m 8 ) = f ( m + 一1 ) 通过计算最优服务台数m + 应该满足不等 式： ：( m + ) 一n ( m 4 + 1 ) = ( b h ) a = ( m 4 ) n ( m 十1 ) 。在实际应用中，a 和b 一 般比较容易得到。 2 5 2 算法的描叙 假定我们已经知道了某银行的最优服务台数为m + = 3 ，即我们根据该银行的a 和b 值可以算出m 。 我们给出该程序的事件类和仿真类的定义和结构。这些类描叙了该系统中各 个对象的重要属性。它们能很好的仿真我们现实的银行排队系统性能指针。 事件类的定义 c l a s se v e n t p f i v n e i m t i m e ； e v e n t t y p ee t y p e ； i n tc u s t o m e r i d ； i n tt e l l e r i d ： i n tw a i t t i m e ； i n ts e r v i c e t i m e ； p u b l i c ： e v e n t ( v o i d ) ； 2 2 e v e n t ( i n tt e v e n t t y p ee t ，i n tc n i n t1 1 1 ，i n t w t ，i ms t ) ： e v e n t t y p e g e t c u s t o m e r d ( v o l d ) c o n s t ； i n tg e t w a i t t f i m e ( v o i d ) c o n s t ； l mg e t t e l l e r i d ( v o i d ) c o n s t ； i n tg e t s e r v i c e t i m e ( v o i mc o n s t ； ) ； 仿真类的定义 c l a s ss i m u l a t i o n p r i v a t e ： i n ts i m a l a t i o n l e n g t h ； i n tn u m t e l l e r s ； i n tn e x t c u s t o m e r ； i n ta r r i v a l l o w , a r r i v a l h i g h ； i ms e r v i c e l o w , s e r v i c e h i g h ； t e l l e r s t a t st s t a t 11 ； p q a e u ep q ； r a n d o m n u m b e rr o d ； i n tn e x t a r r i a l t i m e ( v o i d ) ； i n tg e t s e r v i c e t i m e ( v o i d ) i n tn e x t a r a i l a b l e t e l l e r ( v o i d ) ； p u b l i c ： s i m