（系统工程专业论文）生产库存系统中排队模型性能分析及应用.pdf

江苏大学硕士学位论文 摘要 本课题研究的库存来自于本企业的生产。对于生产型企业而言， 产品的库存量对企业的经营效益有着直接的影响，而产品的生产率与 销售率又对产品的库存量有着重要的影响。如果产品的生产率远大于 销售率，将会积压商品，从而造成流转资金的大量积压，影响企业的 经济效益。但反之就会造成产品的供不应求，造成缺货损失，亦会使 企业经济效益降低。库存量不仅因顾客的需求到达而变化，而且库存 量还因本企业的生产而随时间呈连续变化，因此生产一库存系统属于 复杂的离散一连续系统，并具有诸多不确定因素。所以，在现代化生 产企业管理中，必须确定合理的库存水平，并加以控制，库存管理就 是研究如何解决这方面的问题的。 本文首先在生产一库存系统中利用马尔可夫“无后效性 的性质， 来研究它在市场预测和决策中的作用，并结合实例来说明。其次，研 究了生产一库存系统中的物流调度系统。假设不存在损失制，把自动 化立体仓库输送系统和自动引导车( a u t o m a t e dg u i d e dv e h i c l ea g v ) 运输系统看作随机服务系统，利用排队论来研究这种物流系统的性能 及相关的概率特性。最后，主要描述了多服务台休假排队模型，讨论 了m m c 模型，引入只允许部分服务台休假的策略，使用拟生灭过程 和矩阵几何解的方法，得到系统稳态队长的分布及条件排队等待顾客 数与等待时间的分布，证明了该模型的可行性和正确性。 关键词：排队论，生产一库存，马尔可夫链，物流调度，( e ，d ) 策略， 拟生灭过程，矩阵几何解 江苏大学硕士学位论文 a b a s r a c t t h i sr e s e a r c hc o m e sf r o mt h ei n v e n t o r yo ft h ee n t e r p r i s ep r o d u c t i o n f o rt h ep r o d u c t i o n - o r i e n t e de n t e r p r i s e ，t h ep r o d u c ti n v e n t o r yh a sad i r e c t i m p a c to nt h eb u s i n e s so p e r a t i o ne f f i c i e n c y a n dt h ep r o d u c t i v i t ya n dt h e s a l e sr a t eo fp r o d u c t sh a v ea l li m p o r t a n te f f e c to nt h es t o c k i ft h e p r o d u c t i v i t yi sf a rg r e a t e rt h a nt h ep r o d u c t s a l e sr a t e ，t h eb a c k l o go fg o o d s ， r e s u l t i n gi nal a r g eb a c k l o go fc a p i t a lf l o w s ，a n dt h e ni t w i l lm a k eab a d i m p a c to n t h ee c o n o m i ce f f i c i e n c yo fe n t e r p r i s e s o nt h eo t h e rh a n d ，i tw i l l c a u s eas h o r t a g eo fp r o d u c t s ，r e s u l t i n gi nt h el o s so fs t o c k ，a n di tw i l la l s o r e d u c et h ee c o n o m i cb e n e f i t s i n v e n t o r i e sh a v ec h a n g e sn o to n l yb e c a u s eo f t h er e a c ho fc u s t o m e r sn e e d sb u ta l s ob e c a u s eo ft h ep r o d u c t i v i t yo f e n t e r p r i s e a n dc o n t i n u o u s c h a n g e o v e rt i m ei nar o w s ot h e p r o d u c t i o n i n v e n t o r ys y s t e mb e l o n g s t ot h e c o m p l i c a t e d d i s c r e t e c o n t i n u o u ss y s t e m , a n dh a sal o to fu n c e r t a i n t i e s t h e r e f o r e ，i nt h em o d e m p r o d u c t i o nm a n a g e m e n t ，i ti se s s e n t i a lt od e t e r m i n er e a s o n a b l ei n v e n t o r y l e v e l sa n dc o n t r o lt h ep r o d u c t i o n i n v e n t o r ym a n a g e m e n ti sh o wt os t u d y s o l v i n g t h i sp r o b l e m i nt h i s p a p e r ，f i r s t l yw eu s et h en a t u r eo f “m a r k o vp r o c e s s i nt h e p r o d u c t i o n - i n v e n t o r ys y s t e m ，s t u d d i n gi t sr o l ei nt h em a r k e tf o r e c a s ta n d d e c i s i o n - m a k i n g ，c o m b i n i n gw i t he x a m p l e sf o re x p l a n a t i o n s e c o n d ，i th a s as t u d yo ft h el o g i s t i c sd i s p a t c h s y s t e mi nt h ep r o d u c t i o n i n v e n t o r y s y s t e m a s s u m p t i o nt h a tt h e r ei s n ol o s s ，w et a k et h er st r a n s m i s s i o n s y s t e m sa n dt h ea u t o m a t i cg u i d e dv e h i c l e 弘g 叨t r a n s p o r ts y s t e ma sa r a n d o ms e r v i c es y s t e m ，u s i n gt h eq u e u i n gt h e o r yt os t u d yt h i sl o g i s t i c s s y s t e mp e r f o r m a n c ea n dt h ec h a r a c t e r i s t i c so fp r o b a b i l i t y f i n a l l y ，i tm a i n l y d e s c r i b e st h em u l t i - s e r v e rm o d e ll i n eu pv a c a t i o n , d i s c u s s i n gt h em m c 江苏大学硕士学位论文 m o d e l ，i n t r o d u c i n gt h es t r a t e g yt h a to n l yp a r to ft h ed e s kc o u l dl e a v e ，u s i n g t h eq u a s i - b i r t ha n dd e a t hp r o c e s sa n dt h em e t h o do fm a t r i xg e o m e t r i c ，a n d h a sb e e nc a p t a i no ft h es t e a d y s t a t ed i s t r i b u t i o ns y s t e ma n dt h ed i s t r i b u t i o n o fc u s t o m e r sl i n eu pt ow a i tf o rc o n d i t i o n sa n do fw a i t i n gt i m e ，p r o v i n gt h e f e a s i b i l i t ya n dc o r r e c t n e s so ft h em o d e l k e yw o r d s ：q u e u et h e o r y ，p r o d u c t i o n i n v e n t o r y ，m a r k o vc h a i n ， l o g i s t i c sd i s p a t c h ，( e ，d ) p o l i c y ，q u a s i - b i r t h a n dd e a t h p r o c e s s ，m a t r i xg e o m e t r i c 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论 文的全部内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口 本学位论文属于，在年我解密后适用本授权书。 不保密四 学位论文作者签名：王易岛 7 伊锣年f 只ib 日 指剥嗽：拗 矽扩年1 2 月，名日 独创性申明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中己注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 三宏匆 日期：溯年f 2 月嘭日 江苏大学硕士学位论文 第一章绪论 本章简单介绍了生产一库存系统的概况及应用背景，阐明了本课题研究的背 景、主要内容，指出了本文的主要框架。 1 1 研究背景 在现代企业生产和经营过程中，经常遇到合理的安排生产与库存的问题。一 方面如果生产不足，会影响销售，直接影响到企业的经济效益，另一方面，如果 库存过多，会产生资金积压和增加库存费用。因而将生产车间和仓库结合成一个 整体来研究就显得必要，在这里把这种系统称为生产一库存系统。 大多数旨在获取利润的制造企业有三个主要目标：( 1 ) 最大的客户服务；( 2 ) 最小的库存投资；( 3 ) 高效率( 低成本) 的工厂作业。达成这些目标的过程中主要 的问题是这些目标基本上是互相冲突的。若把库存水平提得很高而且不惜通过改 变生产水平与生产日程去满足客户需求的变化，就可以提供最大的客户服务。但 这种做法要以牺牲第二，第三个目标来达成第一个目标。若生产水平难得更改， 不发生加班加点，机器一旦调整好之后就长期地运转，只生产这一特定产品，则 工厂作业可保持高效率；然而，其结果却是在达成最高工厂效率这一目标的同时 带来巨大的库存量与不良的客户服务。倘若使客户等待而且强迫工厂对客户需求 的变化与生产的中断迅速作出响应，则库存可以保持低水平。在现实世界中，由 于上述的三个目标对于持久的成功几乎同等地重要，很少有哪家公司能当得起只 顾全其中一个目标而排斥另外两个目标。生产与库存控制基本上就是同为在工厂 作业中协调这些目标所需的日常决策提供所需信息这件事打交道。对于企业的一 名生产经理，这些目标基本冲突这一事实是明摆着的。他对工厂中的机器设备投 入了他的资金，他控制着自己的制造只程，他又是他自己的销售代表。当一家客 户要求立即交货时，他的对策是清楚的或者花钱去调整机器与加班加点，或 者让客户等待。他也可以采取为未来的生意持有库存成品、零件或原材料一 一的对策，以便有可能给他的客户以更好的服务。在这样一个只有一名经理的公 司中就存在着这些目标之间的冲突，它们不是容易解决的，但至少该经理能看到 江苏大学硕士学位论文 这个冲突并权衡自己的诸种对策。 在今日的一家大的制造公司里，为客户服务的责任落在组织中的一个部门， 即销售部，它很少考虑提高工厂效率或降低库存水平的责任。另一方面，制造部 门的人员通常对库存感觉不到较大的责任，对客户服务也许感觉有稍多一点责任。 事实上，许多车间经理与监工人员恐怕从来也不是从客户的观点来看待他们的活 动的。往往，这些人员的绩效并非以他们对公司总体目标的贡献来衡量，而是以 他们达成他们被委派的有限目标的能力来衡量的。例如，很少有第一线的监工人 员是以他们控制提前时间与保持存货中有物品的能力来衡量的。但他们的事业很 大程度上取决于他们完成生产任务有多好，同工会打交道有多好以及能否满足预 算的开销目标。由于同样的原因，很少有销售人员是按他们对利润的贡献来判断 的；他们完全是根据销售更多产品的能力来评价的。在今日的商业界有一种被说 得过了头的陈词滥调，这就是：让一家公司内部的经理们互相竞争是健康的。如 果这些经理是为着同一些目标而竞争，那么这种说法之中确有真理，因为这样竞 争能产生极好的结果，但若他们开始为着不同目标而竞争，则其结果将是浪费、 冲突与挫折。 在一家现代化的公司里，经理们的责任已经明确划分，他们的绩效度量鼓励他 们去搞次优化，在这种公司里要去协调这些互相冲突的目标成了一个挑战性的问 题：试图解决这一问题便是生产与库存计划与控制的主要功能。生产与库存控制 要通过一个信息系统来起作用，它编制计划，对照计划度量实际绩效，然后将信 息传递给必须采取校正行动的直线管理人员，其功能就是去协调这些目标以满足 公司总的利润目标。 生产控制与库存控制是分开来发展的。在最初，生产控制只是直线主管人员 要完成的许多功能之一。他订购材料，通过雇佣与解雇人员确定工人人数与生产 水平，通过他的部门催稽工作并通过库存来控制客户服务，而库存多少又是他努 力的结果。由于工作量的增加，用一名文书作他的助手，以关照计时，保管各种 记录及电话应答等职能。这使得文书在回答工作状态与有关交货允诺的查询时经 常同销售部门发生接触；除了跟踪工作进展之外，文书还开始作物料订货与生产 上所需的其它准备工作的计划。这种文书实际上就是生产控制职能的开始。后来， 随着记录保管活动被转移到了主办公室，这个文书发展成为一名催货员。在1 8 9 0 2 江苏大学硕士学位论文 年，一家著名的新英格兰公司中有一个部门就叫“催办部 很容易想象这些 人的责任与活动，对生产控制有过一些使之成为更加有组织并更加科学的方法的 企图。在1 8 8 0 年，某兵工厂( w a t e r t o w a r s e n a l ) 曾设置相当广泛的生产控制系统， 但第二次世界大战以前它并未得到普遍的应用。 在第二次世界大战中，催货员的处境是名誉扫地，因为在同事心目中他是同 危机、混乱、压力与麻烦相伴的。造船公司老板h e n n yk a i s e r 把他公司里的催货 员取名为催稽员。他通过读者文摘上的文章，推广了催稽员作为一名志向行 动的能干而有进取心并对满足生产日程作出极其重要贡献的人的概念。在1 9 5 0 年， 在书本里往往用催稽这个词来定义生产控制。当时的一位实际工作人员把他自己 的活动描述为收到一位客户的订单之后他先订购装配所需要的零件，然后，当客 户来查问为何未能如期交货时，则追踪订单，找出这些零件在哪里，并贴上“急 件 标签。即使今天，催稽员仍是大多数生产控制系统的必要组成部分之一。 1 2 本课题的国内外研究现状及发展趋势 库存控制是沿着更为科学的( 至少在理论上) 路线发展的。经济批量的基本概 念发表于1 9 1 5 年，确定订货点的统计方法在1 9 3 4 年由r h w i l s o n 提出。然而， 这些相当复杂的库存管理系统技法很少获得应用。也许这是因为由于1 9 3 0 年与 1 9 4 0 年间不是鼓励科学管理的年代。在1 9 3 0 年的经济衰退时，对大多数公司而言 最重要的目标是生存。就像在大洋上空一架失事的飞机上的人们为了减轻飞机的 载荷而往机外投掷食品与珍贵物品那样，在大衰退的年代里长期利润与成长变成 次要的了。1 9 4 0 年代后期，当被抑制的需求为所能生产出来的每件东西提供一个 现成的市场时，库存控制的目标平准工作负荷或在客户服务的基础上竞争一 一在大多数企业经营中也不是重要问题。自从1 9 0 0 年代早期到第二次世界大战， 在t a y l o r ，e m e r s o n ，g a n n t ，g i l b r e t h 以及其他人所创导下的科学管理运动使得人 们公认生产计划与控制应该是一种参谋活动，其结果是在大多数公司里建立了明 确的生产与库存控制职能一旦它通常是非常原始的。生产控制，除了有一些简 单的机器加载技法以外，在大多数公司里仍基本上是靠催稽，库存控制虽然开发 出了一些科学的理论，但并无多大实际的应用。 从第二次世界大战迎来了运筹学，即应用科学技术方法去解决战争问题的学 3 江苏大学硕士学位论文 问。在战争中有限资源的分配是关系到战争胜负的大事。运筹学的方法在二次大 战中显得相当管用。当这些做过运筹工作的科学家回来处理和平世界的问题时， 他们的注意力集中到了生产与库存控制问题上，因为该问题的要素可用数字表达， 用得上概率统计理论，而且这方面有许多决策是平衡多种解决方案的结果。在预 测、库存控制与数学规划方面得出了一些值得注意的结果。虽然运筹学并未完全 解决它存在的事务性问题，但它确实引发了采用一种更加合理的方法去控制生产 与库存的新的兴趣。 在实际生产环境下，许多生产因素是模糊的，如用确定型或随机型生产一库存 模型来描述会出现很大的误差。故从上世纪9 0 年代起，很多学者将模糊数学和随 机模型引入库存理论，如文献n 刮讨论了当某一个或两个生产要素是模糊而其他要 素为常数、时变量或随机变量时的情形，并利用扩张原理建立模型求解，其过程比 较复杂。所以近年来，国内外学者对各种库存控制系进行了更加深入的研究，如 q b c m a n 和k i m 呻1 0 1 研究了需求和服务均是指数分布的生产库存系统。他们分别研 究了所定货物瞬时到达库房和所定货物的到达有一定延迟的生产库存系统，并且 都解决了最优订货策略问题。文献f 1 1 1 研究了订货反应时间为零，订货策略为 刀( 口o ”的生产- 库存系统，给出了每件产品的平均费用函数。b c r m a n ，k a p l a n 及 s h i m a s k n 2 1 研究了需求率与服务率均事常数的生产一库存系统，在假设库房无储备 不见式系统中到达的需求要排队等待的前提下，为了使总费用最小，他们解决了系 统的优化控制问题，确定了最优订货量。文献f 1 3 1 则假设部分需求量被延期交货， 另一部分丢失，导出了一种再订购模型，并得到最优结果。在国内如侯玉梅啪1 研 究了订货延迟是一个指数随机变量的生产一库存模型，张秀n 4 1 等人研究了一种订货 带有折扣的生产一库存系统模型，它们从不同角度都确定了最优订货量，并使费用 目标函数达到最小。随着企业之间竞争的加剧，一种性的库存管理模式“供应商管 理库存 ( v m i ) 开始兴起。通过v m i 的应用，能有效改善供应商、制造商、分销商、 零售商和客户之间在供应链中的关系，提高整个供应链的盈利水平和竞争力 1 5 , 1 6 , 1 7 其中如文献1 8 1 特别关注了一个仓库，多个零售商的情况。a x s a t e r 等假设仓库采用 常规的点仓库批量订货策略，同质的零售商采用联合补充策略，成本较高。c h e n n 们 采用仿真方法研究了分层、分布式、动态库存( h d d i ) 管理调度问题，并引入了紧 急补充概念。c c t i n k a y a 啪1 等针对供应商管理库存系统提出一个整合的库存补充和 4 江苏大学硕士学位论文 交货计划，供应商用( s ，s ) 策略补充其库存，以及基于时间的运输联合策略发送订货， 从而更好地进行库存成本控制。 现在世界上已有很多单位建立了计算机管理的物资存贮系统，为库存管理的 科学化、现代化，在理论和实践方面作出了成绩，在加速物资、资金的流转、减 缩开支方面起了很大的作用。现代制造业的一些新的概念，象j 、连续物流和跨 码头直接发运( c r o s s d o c k i n g ) 使得库存量和库存时间都大大减少。存储越来越被认 为是一个物流的过程而不只是一种静态的存储技术。通过应用缓冲站、积累区以 及一些相关操作，仓储已不只是一个短暂的物料停留过程。 最近的趋势包括动态存储系统的发展。例如v l m ( v e r 涮l i f tm o d u l e s ) 的应用， s i k o r s k y ss t r a t f o r dc o n n 飞机制造厂采用5 个v l m 存储3 0 0 0 0 可重用的模具和 3 2 0 0 0 一次性的工具。将原来的存储区域减少至原来的1 1 0 ，工具的提取时间由原 来的3 - - 5 m i n 减少至4 5 s 。库存软件现在也能跟踪工具在何时、何地被何人领取， 也因此可以将库存降低到原来的一半。并且操作由原来的人上下移动来取工具， 变为工具上下移动到人适合提取的位置。再比如通过一个振动的气缸将负载从流 动的巷道中移下，由于不是通过重力，所以不需要有斜坡，负载是在一个水平面 上移动，大大节省了空间。 全面的库存控制是高效的仓库管理的关键，新的w m s ( w a r e h o u s em a n a g e m e n t s o f t w a r e ) 库管理软件，提供了一个基于小型机、p c 机、服务器的，对仓储、分 配和制造等操作提供实时的库存管理，并将它们集成在一个软件包内。美国的集 成化物流系统i m 4 s 软件是当前物流行业中最完整的一体化解决方案，目前国内 大长江摩托车集团和玉溪( 红塔) 烟草集团已经引进了该系统。它的主要特征为：( 1 ) 开放的、客户机服务器结构。( 2 ) o r a c l e 、s q l 等大型数据库。( 3 ) 面向对象的设计。 ( 4 ) 扩展的仓库管理功能( 包括供应商管理、拼盘管理、零部件检验与质量跟踪、存 储、生产计划管理、b o m 管理和销售管理等) 。( 5 ) 具有在线监控仿真和离线设计 仿真，与物流管理系统集成并能够自动转换。( 6 ) 投资成本估算。( 7 ) 大量采用新技 术( 支持w e b 数据库、并行数据处理与仿真和虚拟现实技术) 。卖主管理库存w m i ， v e n d o rm a n a g e di n v e n t o r y ) 是制造者和客户之间一种新型的合作关系。它允许制造 者依据产品的用途以及用户所提供的库存水平信息来对客户的库存进行补充。电 子数据交换( e d i ，e l e c t r o n i cd a t ai n t e r c h a n g e ) 使这项操作成为可能。 5 江苏大学硕士学位论文 1 3 本课题研究的内容及解决问题的方法 库存管理是现代企业生产经营管理的一个重要组成部分，库存产品可以起到 缓冲、调节和平衡的作用。库存是生产、销售和为顾客服务得以正常进行的保证， 然而库存要占用资金。由于库存是实物的存储，所以要支出一定的保管费、耗损 费和利息。因此，库存将使企业的赢利减少。供应链上制造企业库存水平( 即库存 量) 的高低一方面影响制造商的成本，另一方面影响客户服务水平和企业对市场波 动的适应能力。所以，在现代化企业管理中，必须确定合理的库存水平，并加以 控制。库存管理就是研究如何解决这方面的问题的。 本文首先在第三章中应用马尔可夫链”无后效性 的性质“，在生产一库存 系统中利用这种性质来研究它在市场预测和决策中的作用，并结合实例来说明。 其次，在第四章中主要研究了生产一库存系统中的物流调度系统。在研究过 程中，先假设不存在损失制，把自动化立体仓库输送系统的调度和自动引导车 ( a u t o m a t e dg u i d e dv e h i c l e , a g v ) 运输系统看作随机服务系统，利用排队论来研 究这种物流系统的性能及相关的概率特性。 最后，在第五章中主要描述了多服务台休假排队模型，讨论了m m c k 模 型，引入只允许部分服务台休假的策略，使用拟生灭过程和矩阵几何解的方法， 得到系统稳态队长的分布及条件排队等待顾客数与等待时间的分布，也验证了文 献中相关结论证明了该模型的可行性和正确性。 6 江苏大学硕士学位论文 第二章排队相关理论及主要工具 很多生产问题都会或多或少地涉及到排队。只要在生产过程中存在随机分布 现象，就肯定会产生排队，各种库存实际上就是对排队的缓冲。完全的均衡分布 在现实中是不存在的。在这一类问题中，会在随机不定的时间间隔内遇到需要某 种服务的人、部件或机器。为满足这种服务所需要的活动，往往会花长短不一的 时间。在一定的到达率和服务率的条件下，可以运用数学方法计算并安排排队问 题。在当代，排队分析被广泛应用在诸如通讯系统、交通系统、生产系统以及计 算机管理系统等服务系统上。排队论提供了一种数学手段，能够预测某个特定排 队的大概长度和大概延误时间，以及其他相关重要数据，包括排队场地安排、优 先服务处理、排队成本控制、排队长短与发生事故的关系等等。掌握这些信息， 会使人们更有针对性地解决相关的随机分布问题，做出明智的决策。 排队论是运筹学的重要分支，也是应用概率论的重要组成部分。它的基础是 概率论和随机过程。排队论已经发展了近一个世纪形成了一系列较成熟的研究方 法，并取得了丰富的成果。下面简单介绍排队论相关知识及几种常用的研究排队 模型的方法。 2 1 排队论的基本概念 2 1 1 排队论发展的简介 排队论又名随机服务系统理论，是研究拥挤现象的- i j 科学。在人们的口常 生活中，常常会遇到拥挤排队的现象。这种现象给顾客增添了困难和不便，也使 服务机构的工作效率降低。然而，人们往往不能摆脱这种困境。增加服务机构， 固然可以减少排队现象，但却增加了服务成本；反之，减少服务机构，固然可以 提高服务机构利用率，降低服务成本，但却又增加了顾客排队等待时间，这是互相 矛盾的。排队论就是研究如何才能既使顾客的要求得到充分满足，又使服务机构 的花费最经济的一门学科。 排队论起源于e r l a n g 对电信系统的研究，第二次世界大战以后，特别是随着 计算机和通讯技术的迅速发展，也得到重视和迅猛的发展，并且发展成为运筹学 7 江苏大学硕士学位论文 的一个重要分支。它通过研究各种服务系统在排队等待中的概率特性，来解决系 统的最优设计和最优控制。 2 0 世纪3 0 年代中期，当费勒( w f e l l e r ) 引进生灭过程时排队论才被数学界承 认为- - i 0 重要的学科。2 0 世纪5 0 年代初肯德尔( d g k e n d a l l ) 对排队论作了系 统的研究，他用嵌入马尔可夫链( a m a r k o v ) 方法研究排队论，使排队论得到进 一步发展。2 0 世纪6 0 年代起，排队论研究的课题日益复杂，很多问题很难求得其 精确解，因而开始了近似方法的研究。排队论的产生与发展来源于实际的需要， 实际的需要也必将决定它今后的发展方向。 2 1 2 排队系统的特征 排队是日常生活和工作中常见的现象。比如排队买票，排队购物以及排队上 车，这些都是排队系统的一部分，当然还有其他排队，像计算机数据的处理、产 品存储问题等也是一种排队。 尽管排队系统是多种多样的，但从决定排队系统的主要因素看，它主要有输 入过程、排队规则、服务机构和输出过程。 1 输入过程输入过程是描述顾客来源及顾客是按怎样的规律到达排队系 统。( a ) 顾客总数：顾客的来源可以是有限的也可以是无限的。例如在中小型工厂 里需要修理的机器可以看作有限的。到达火车站窗口等待购票的总人数可以看作 无限的；( b ) 到达类型：顾客可以是单个到达，也可以是批量到达；( c ) 相继顾 客到达的时间间隔所服从什么样的概率的分布：定长分布、负指数分布、几何分 布、超几何分布、e r l a n g 分布、一般分布等。 2 排队规则一般分为等待制、损失制和混合制。( a ) 等待制：指顾客来到 系统发现服务台均被占用，他们就排队等待服务。等待制又分为先到先服务、后 到先服务、随机服务、优先权服务等；( b ) 损失制：指顾客到达时，发现服务台 均被占用，顾客不愿意等待或服务机构不允许顾客等待等条件下离开系统；( c ) 混合制：等待制和损失制相结合。分队长有限的混合制，等待时间有限的混合制， 此外还有顾客强占性服务以及服务后反馈等规则。 3 服务机构刻画服务机构主要方面：( a ) 服务台数可分为单服务台、多 服务台，而在多个服务台中又可分为并联和串联；( b ) 服务台提供给顾客的服务 时间服从什么样的概率分布以及对每个顾客的服务时间是否相互独立，本课题研 8 江苏大学硕士学位论文 究的服务时间概率分布是一般分布；( c ) 是单个服务或是批量服务，以及一个服 务台连续为顾客提供多种服务或顾客可以有选择地接受服务台提供的服务，休假 策略等。 4 输出过程即指接受服务完毕的顾客相继离开系统的过程。刻画一个输出 过程的主要指标是相继离开的时间间隔及在一段已知时间内离开的顾客数，顾客 可以单个离开，也可以批量离开。这些指标也能反映系统的工作效率。 2 1 3 排队系统的表示方法 1 9 5 1 年肯德尔用三个字母组成的符号删来表示排队系统。其中a 表示到 达时间分布，b 表示服务时间分布，c 表示服务机构中服务台的个数。一般用m 表示指数分布，用g 表示一般分布，后来在前两个字母的右上角加字母以表示每 次到达几个顾客与每次服务几个顾客。一般还假定到达间隔时间序列为独立同分 布的随机变量序列，服务时间序列也为独立同分布的随机变量序列且这两个随机 变量序列也相互独立。 2 1 4 排队系统的主要指标 一个排队系统要从两方面考虑，即服务机构和顾客的利益来考虑，顾客希望 等待的时间越短越好，那就需要服务机构的服务台越多越好，服务速度越快越好； 而服务机构要想获得高的利润就必须优化考虑服务台的个数、服务速度以及服务 策略等。综合考虑排队的几个重要指标：队长、等待时间、服务台的忙期、系统 的服务强度和损失率等成为排队论的主要研究内容。 1 队长队长是指系统中的顾客数，即正在服务的顾客数与等待服务的顾客数 之和。它一般是一个随机变量，通常要求其分布和前两阶矩。 2 等待时间从顾客到达时起一直到开始接受服务时止这段时间称为该顾客 的等待时间。而从顾客到达系统时起一直到他被服务完离开系统时止这段时间为 该顾客的逗留时间，即顾客的等待时间和服务时间之和。通常我们要求它们的分 布和前两阶矩。 3 忙期忙期是指空闲的服务机构从有顾客到达开始服务时起一直到服务机 构又没有顾客时止这段时间。与忙期相对应的是闲期，它是指服务机构从开始没 有顾客时起一直到服务机构有顾客时止的这段时间。对于有刀个服务台的系统，一 9 江苏大学硕士学位论文 般还有讨论其k 阶繁忙期。从系统中开始有k 个顾客在等待时起一直到有一个服务 台空闲时止这段时间称为该系统的k 阶繁忙期。忙期、闲期、k 阶繁忙期也是随机 变量。一般也要讨论他们的分布和二阶矩。 当然，对于不同的系统，上述三个指标的重要性也是不同的，有时甚至是没 有意义的。例如，m m o o 系统与m i m l n l n 系统，讨论顾客的等待时间是没有 意义的。 2 2 马尔可夫链 马尔可夫过程是一类很重要的随机过程。这一类过程的特点是：当过程在时 刻岛所处状态已知时，f 0 以后过程所处的状态与岛以前过程所处状态无关。这个特 性叫做无后效应，也叫马尔可夫性。通俗的说就是“已知现在，将来和过去无关”。 定义2 1 2 2 1 设随机过程留( f ) ，t 丁) 的状态空间s 为r 中的可列集，如果对t 中任意刀个 f 2 0 ， p u 一1 ( f ) = ，r + 0 ( f ) ，z ，= o ，当i l 时， 0 ， p ，( t ) = 1 一( 丑+ 。) f + 0 ( f ) ， p ，( ，) = 0 ( f ) ，i s i i 2 ， 则称讧o ) ，0 ) 为生灭过程。生灭过程的状态是相通的。易见有 q i = 以+ 以，吼，f - 。= “，q o = o ，i j - i l 2 。生灭过程的密度q 矩阵为 q = 一( 以+ 以) 九 如果生灭过程满足条件以- - 0 ，则称它为纯生过程，如果生灭过程满足条件 五兰0 ，则称它为纯灭过程。生灭过程的前进柯氏方程为 lp j ( f ) = 一( 丑+ ，) p ( f ) + 乃一。p 一。( t ) + l u p ，( f ) ，1 ， 【p ：( f ) = 一厶p 。( t ) + l 。p ，( f ) 如果在时刻0 过程处于状态f i ，则上方程的初始条件为 1 1 2 2 2 0 1 p p p 恐 丑 一 厶”鲍 一 肌 江苏大学硕士学位论文 只( o ) = 1 ，p k ( o ) = o ，k 萑f 。如果生灭过程的平稳分布 巩，k o ) 存在，它应满足方程 组： 一( 乃+ z ) 万+ d v l y 一l + ，+ l 万j + l = 0 ，j = 1 ，2 ，3 ， 一九万o + l 万l = 0 ， 巩= 1 ， t 1 由第一式得 j + l 万j + l t 万= 7 一乃一l 万一l = = t l y 1 一九万o 。 由第二式得乃= 鱼，从而得 万。：型地即 由第三式得 铲( 妻k = l 等 ， 、一i 从而知级数妻玉生蔓生 。如果c o 玉生蔓尘 o o ，则生灭过程的平稳分从而知级数罗鱼尘生丑 。如果罗鱼尘生鱼 o ，k 弓：1 ，即谤，j ：o 工，七j 为平稳分布。 j - - o c 2 ，对无限状态e = o 2 ， ) 的生灭过程，若有条件+ 薯去差i 弩 o ，o o 弓：1 ，即也，j ：0 ，1 ，2 ， 为平稳分布。 j = o 2 4 拟生灭过程及矩阵分析法 定义2 5 ( 拟生灭过程) 1 2 5 考虑一个二维m a r k o v 过程留( f ) ，j ( f ) ) ，状态空间 是 q = ( 七，j ) ；k 0 ，j = 1 , 2 ，m ) ， 称伍( f ) ，( f ) ) 是一个拟生灭过程( q u a s ib i r t ha n d d e a t hp r o c e s s ，简记q b d ) 。如果将 状态按字典顺序排序后，其生成元可写成下列分块三对角形： q = a oc o 曰l ac bac 曰a 其中所有子块都是m 阶方阵，满足 ( 鸽+ c o ) e = ( 骂+ 4 + c ) p = ( 彳+ b + c ) p = 0 a 和a 有负的对角线元素和非负的非对角线元素，其余子块都是非负阵。称状态 集 ( k ，1 ) ，( 七，2 ) ，( k ，m ) ) 称为水平七，k 0 。若过程是正常返的，以( x ，) 表示过程 x ( f ) ，( ，) 的极限变 量，并记 = l i me x ( t ) ：k ，( f ) = ) = 尸 x = 后，d = j ) 。 其中k 0 ，1 优。为适应q 的分块形式，将平稳概率按水平写成分段形式 万i = ( 万t l ，刀1 2 ，t i 。) ，k 0 。 q b d 是经典生灭过程从一维状态空间到二维状态空间的推广。经典生灭过程 的状态x ( f ) = 七视为被分解成m 个子状态敝山，( 七，聊) ) 。这一结构顺应了刻画过 江苏大学硕士学位论文 程在多层次、多相位及变动参数情况下演化的要求。e v 趾s ( 1 9 6 7 ) 首先在排队论分 析中使用这类过程，w a l l c a e ( 1 9 6 9 ) 毛e 算机系统研究中也遇到这类过程，并由他引 入了“拟生灭过程”这一术语。 迄今广泛使用的只是一类特殊的q b d ，即生成元q 中的子块从某一水平开始 不再发生变化的情形。这时，过程生成元如： q = a ，一lc ，一l ba c ba c 二十世纪7 0 年代以来，n e u t s ( 1 9 8 1 ) 等系统地发展了处理这种特殊q b d 的矩 阵分析方法，通过求率矩阵来求解。对于一般的q b d ，尚未建立起平行于经典生 灭过程的理论和处理方法。 从2 0 世纪8 0 年代到9 0 年代田乃硕等把n e u t s 的矩阵几何解方法引入到休假排 队模型中，促进了多服务台休假排队系统的研究，并且初步建立起多服务台休假中以 条件随机分解为核心的理论框架，为经典排队论的发展和应用开辟了更为广阔的前 景。 该方法主要从计算概率的角度解决随机模型研究中的数值计算问题，其突出 特点在于用该方法得出的结果均以矩阵形式给出，便于在计算机上进行计算。 1 4 江苏大学硕士学位论文 第三章马尔可夫链及其在生产一库存系统中的应用 在现实生活中，经常会发生经济环境、经营条件变化的情况。为了研究这种情 况，首先要收集有关经济环境的变化的信息，得到经济环境变化的规律，并假定这 样的规律在未来时期仍成立。为了说明方便，有时对于不同的经济环境，就说系统 处于不同状态。在实际经济现象中，系统在任一时期所处的状态都与它前面一些时 期所处的状态有关，其中有一种最简单、最基本的情况，就是每一时期系统处于各 状态的概率只与这一时期的前一个时期所处的状态有关，而与更早时期的状态无 关。这种性质就是所谓的“无后效性 。与此有关的预测问题，称为马尔可夫预测。 在生产一库存系统中，经常需要订购物资及生产资料。而物资订购量的多少 与需求量的大小密切相关，而需求量的大小，有些部门是根据上级下达的指标、 任务而定，即根据任务，结合核定的消耗定额，计算需求量；有些则需要预测未 来市场的需求量而定。但总的来说，对未来需求量作出定量的预测是很重要的， 是存贮决策的重要依据。对未来需求做预测，对于公司管理者制定决策计划、生 产计划和营销策略等都十分重要。对未来需求的预测构成了物流所有战略和计划 决策的基础。从供应链的“推拉观点 看，所有推动流程都是依据对用户需求的 预测来进行的，而所有拉动过程又都是依据对市场需求的反应来进行的。对于推 动流程来说，物流管理者必须规划产品的生产能力；对于拉动流程来说，物流管 理者必须提高供给需求的水平。在上述情况下，管理者首先要考虑的就是预测顾 客未来的需求量。下面我们就利用马尔可夫的这种性质来研究它在市场预测和决 策中的作用，并结合实例来说明。 3 1 基本概论 如果对于每一个f 和都满足，尸 t + 。= l 五= f ) = p x l = jx o = 小t = o ，1 ， 则称转移概率是定型的，并用弓表示。乞就是上一个时期出现状态珀勺条件下，本 期出现，的概率。这种只与前一时期的状态有