排队论基础及应用.ppt

  1. 1、本文档共77页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
排队论基础及应用

对上述排队系统,定义 上式中Lq写为 1981年,Miller得出系统中优先级1的客户数量为n1的概率 * 最后,考虑客户分为类型1客户和类型2客户(比如大人和小孩),到达速率和服务速率分别为λ1,μ1和λ2,μ2,但是排队不考虑优先级。 * 比较 我们考虑了三种排队系统: 有优先级,客户服务时间一样,λ1,λ2,μ 有优先级,客户服务时间不同, λ1,λ2,μ1, μ2 无优先级,客户服务时间不同, λ1,λ2,μ1, μ2 比较第一种和第二种,当 , ,这时λ1,λ2决定何种排队模型更优 * 比较第二种和第三种,它们的队列长度差别 如果 ,上式1,表示引入优先级可以缩短等待时间。 。 如果 ,上式1,表示引入优先级会延长等待时间。 。 规则:服务所需时间短的客户优先(priority assigned by shortest processing time, 简称SPT规则) * 例:理发店 一个理发店只有一位理发师。平均每小时有五位顾客立法,到达可视为泊松过程。到理发店的顾客中有1/3是理平头的,理平头平均耗时5分钟,而其余理发顾客平均耗时12.5分钟,均服从指数分布。理发师考虑优先给平头顾客理发,问这样做是否有助于缩短顾客的平均等待时间。 * 平头优先: 不考虑优先: * 先剪平头可以缩短等待时间 多个优先级 前面的讨论限于两个优先级。 我们考虑一个服务器,客户有多个(大于2个)优先级的情况。排队规则仍然是非先占优先的。 假设客户分为r个优先级,其中第k个优先级客户的到达速率为λk,平均服务时间为1/μk。泊松到达,指数服务时间。 定义: * 当ρ1,系统有稳态 考虑一个优先级为i的客户,他在队列中的等待时间为Tq。当该客户进入队列时,假设队列中已有n1个优先级为1的客户,n2个优先级为2的客户,...,nr个优先级为r的客户。并且假设在该客户在队列中等待期间,有n1’个优先级为1的客户,n2’个优先级为2的客户,...,nr’个优先级为r的客户进入队列。令S0表示该客户到达时正在被服务客户的剩余服务时间;Sk表示服务nk个优先级为k的客户的时间;Sk’表示服务nk’个优先级为k的客户的时间。 * 令Wq(i)表示优先级为i的客户的平均队列等待时间 求S0 服务一个客户的时间分布 另外 * 因此 由于nk和每个客户的服务时间Sk(n)是独立的 * Little’s law 类似地 因此 求解可得 注意 * r元线性方程组 整个排队系统的平均队列长度 如果不考虑优先级,即r种类型的按照FCFS获得服务,SPT规则继续有效,即如果按照优先级高低,有 ,则引入优先级可以最大地缩短客户的平均等待时间。 引入优先级,缩短平均等待时间的代价是客户在等待时间上的不公平。这是一个 Efficiency-Fairness Tradeoff * 多服务器优先级排队模型M/M/c/∞/PR 考虑多个服务器的优先级排队系统 客户有r个优先级,优先级i的客户到达速率为λi。非先占优先。 所有客户服务时间一致,为平均1/μ的指数分布。 定义 * 类似地,优先级i的客户的队列等待时间 其中Sk’,Sk和S0的含义同上。 求E[S0] * 根据M/M/c(由于所有客户服务速率一样),有 最后,类似M/M/1/∞/PR,得出 * * * * Erlang分布和指数分布的关系 k个独立同分布(i.i.d)的指数分布随机变量之和为k型Erlang分布。如果指数分布变量均值1/kμ,则它们之和的均值为1/μ,方差为1/k μ2 例如:一个产品经过4道检验工序,每道工序平均耗时1/4μ,则整个检验时间平均1/μ,服从4型Erlang分布。 * Erlang服务时间排队模型M/Ek/1 考虑一个排队模型:客户泊松到达,服务器有k个服务阶段,每个耗时1/kμ,指数分布。服务器仍然只能一次服务一个客户,即当前客户完成最后一个服务阶段,下一客户才能开始第一阶段的服务。 令pn,i为系统中有n个客户,且包括当前的服务阶段,被服务客户还有i个阶段需要完成(在第k-i个阶段)的概率。 情况1:被服务客户在阶段i,1≤i≤k-1,n≥2, 客户到达,(n,i)?(n+1,i),(n-1,i)?(n,i) 完成一个阶段服务, (n,i+1)?(n,i) 情况2:被服务客户在阶段k, n≥2 客户到达, (n,i)?(n+1,i),(n-1,i)?(n,i) 完成一个阶段服务,(n+1,1)?(n,k) 情况3:n=1, 1≤i≤k-1 客户到达,(

文档评论(0)

wnqwwy20 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:7014141164000003

1亿VIP精品文档

相关文档