高级运筹学-排队论.ppt

Queuing Theory
排队论
第四章
Where the Time Goes
美均要花费---
6年 吃
5年 排队等待
4年 做家务
2年 回电话不成功
1年 寻找自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的爱尔朗电话损失率公式。
。
上世纪50年代，美国数学家关于生灭过程的研究、. Kendall提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；
上世纪60年代更多的应用于生产线，交通等问题；
上世纪70年代应用于计算机网络、通信等领域；
如今通信系统仍然是排队论应用的主要领域,同时在运输、港口泊位设计、机器维修、库存控制等领域得到广泛应用，特别是服务行业。
排队论发展简述
本章大纲
排队服务系统的基本概念
输入与服务时间的分布
生灭过程
几种不同类型排队系统分析
标准M/M/1/∞/∞
有限队列模型 M/M/1/N//
顾客为有限源系统M/M/1/∞/m
多服务台系统M/M/s
排队系统的优化
排队服务系统的基本概念
排队系统的一般表示
一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。
要求得到服务的对象称为顾客
服务者称为服务设施或服务台
顾客的到达和离开称为排队系统的输入和输出。
顾客的总体称为顾客源或输入源。
因此，任何一个排队系统是一种输入-输出系统。
排队系统基本结构
顾客源
等候队列
服务设施
到达
输入
输出
离开
排队系统
排队服务系统的基本概念
商业服务系统
系统类型 顾客 服务台
理发店 人 理发师
银行出纳服务 人 出纳
ATM机服务 人 ATM机
商店收银台 人 收银员
电影院售票窗口 人 售票员
机场检票处 人 航空公司代理人
内部服务系统
系统类型 顾客 服务台
秘书服务 雇员 秘书
急救中心 病员 护士
传真服务 雇员 传真机
物料处理系统 货物 物料处理单元
维护系统 设备 维修工人
质检站 物件 质检员
运输服务系统
系统类型 顾客 服务台
公路收费站 汽车 收费员
卡车装货地 卡车 装货工人
港口卸货区 轮船 卸货工人
等待起飞的飞机 飞机 跑道
航班服务 人 飞机
出租车服务 人 出租车
电梯服务 人 电梯
消防部门 火灾 消防车
停车场 汽车 停车空间
急救车服务 人 急救车
排队系统的三个基本组成部分：
输入过程 (顾客按照怎样的规律到达)；
排队规则 (顾客按照一定规则排队等待服务)；
服务机构 (服务机构的设置,服务台的数量,服务的方式,服务时间分布等)
排队系统的组成
一、输入 Arrival Characteristics
顾客源是有限集还是无限集（Size of the arrival population）
工厂内待修的机器数是有限集，售票处购票顾客源可认为是无限集。
顾客到达系统的方式是单个的，还是成批的（Behavior of arrivals）
如到达宾馆服务台住宿有散客，也有团体
相继到达系统的时间间隔是确定性的还是随机性的（Pattern of arrival at the system）
如自动装配线上待装配部件到达各工序的时间间隔是确定的。
而多数顾客到达都是随机的，随机的服从何种概率分布：二项、负指数、爱尔朗分布等。
到达过程(输入过程)的内容
顾客总体数或顾客源数
有限或无限
顾客的到达类型
单个或成批
顾客的到达间隔时间
间隔时间分布
二、排队规则 Queue Discipline
顾客来到排队系统后如何排队等候服务的规则
1、即时制（损失制）：当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统；
如电话拨号后出现忙音，顾客可马上挂上电话。
2、等候制：当顾客到达时，所有服务台都已被占用，顾客就加入排队队列等候服务。排队规则：
FIFO /FCFS 先到先服务，最常见
LIFO：乘电梯的顾客是后进先出
SIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换
优先权服务：重病优先、老年人优先等
3、混合制：即时制和等候制相结合的一种排队服务规则。
队列长度有限制时：排队等候的人数超过预定数量，后来的顾客就自动离开。
旅馆的客房等
排队时间有限制时：顾客