麻辣烫排队问题

前言:这是之前上《信号与系统》课程时做的一个作业。

摘要:本文从生活中很普通的食堂麻辣烫排队问题出发,研究两种不同排队方式的区别,粗略比较两种排队方式的优劣。

关键词:排队论

一、问题描述

买麻辣烫的同学服从服从参数为的泊松分布,每人只许买一份麻辣烫,买完就走。并行做麻辣烫的厨师有个,每位厨师任何时刻只能做一份麻辣烫,不同厨师做麻辣烫时间长度独立,且都服从参数为的负指数分布。同学到达麻辣烫窗口与厨师做麻辣烫相互独立。

有两种排队方式

  • A:排成一个大队列。只要有某位厨师空闲,他就给排在队列中的第一个同学做麻辣烫。新到达的同学排到队尾,直到排在他前面的所有同学都买到麻辣烫之后,他才有资格买。按照这种方式,当个厨师都忙碌时,同学们按照先到先得的原则在排一个大队列。
  • B:自选排成多个队列。每个厨师前面各排一个队列,厨师只给他负责的队列中的同学做麻辣烫。新到达的同学自行选择排哪一个队列。按照这种方式,当个厨师都忙碌时,同学们排成了个队列。

对于不同排队方式的优劣有一下几个评判指标

  • 平均同学人数
  • 平均等待同学人数
  • 每个同学花费的平均时间
  • 每个同学在系统中等待时间

在麻辣烫问题中,每个同学花费的平均时间和等待时间不会有本质的不同,因为即使是“服务时间”,同学也是在等待麻辣烫的制作。所以我们只取平均同学人数和每个同学花费的平均时间两个参量描述排队方式的优劣。

二、计算推导

1. 单队列方式

由于所有厨师做麻辣烫的时间是相互独立的,且都是参数为的负指数分布;买麻辣烫的同学服从参数为的泊松分布。因此这就是一个标准的模型,即输入输出过程是Markov的,有个服务台。因为厨师总数是,所以当排队同学人数 时,所有同学都处在等待厨师做完麻辣烫(即被服务)的状态,这时做麻辣烫的平均速率为;而当排队同学人数时, 所有厨师都在工作, 这时做麻辣烫的平均速率是

因此单队列方式,生灭过程的状态转移图如下图。

考虑系统进入平衡状态后,系统满足的状态平衡方程如下

将(1)带入式(2),从开始有


所以

式(3)就是M/M/1模型中的稳态方程,计算得到

又因为,所以

综上所述, 有

上式成立需要

其他指标

  • 平均同学人数
  • 每个同学花费的平均时间,由Little公式有
  • 关于上式的理解:平均花费的时间就是同学排到队尾后,他后面再排上平均队长所用的时间(这时他就“平均”拿到麻辣烫走了)

2. 多队列方式

多队列方式比单队列方式要复杂一点,主要因为每次来到同学会根据队伍长度做一个选择。根据选择方式,得到的平均等待人数和平均等待时间也会有所不同。

无选择均匀随机排布

如果来的同学根本不关心队伍长度,只是排队的话,这样这就是个标准的模型,可以直接利用的公式进行计算。

此时每个队列同学来的速度是,厨师处理速度是

  • 平均同学人数
  • 每个同学花费平均时间

注意到这里依旧满足

比较

因为,所以只比较平均同学人数即可。


文章标题:麻辣烫排队问题

文章字数:1183

本文作者:Mickir

发布时间:2018-05-31

最后更新:2018-07-17

原始链接: https://mickir.me/blog/malatang.html

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。