[管理学]排队论方法.ppt

---排队论方法 1 排队现象 有形的队伍 超市出口处排队付款 餐厅排队买饭 银行排队等待服务 …… 无形的队伍 114查号台等待服务 网络中数据包传输 …… 某些系统也可能根本不允许排队 交换机处理呼叫 … 1 排队现象 排队现象的抽象 要求服务的——顾客 满足对方要求给予服务的——服务窗 顾客与服务窗构成一个排队系统，或称之为随机服务系统 排队现象的产生 顾客的到达时刻是随机的 服务窗服务完一个顾客的时间也是随机的 在某时刻，要求服务的顾客数超过所有服务窗的总容量时，顾客就要排队等待服务 (Kleinrock) We study the phenomena of standing, waiting, and serving, and we call this study Queueing Theory. Any system in which arrivals place demands upon a finite capacity resource may be termed a queueing system. 2 学习排队论的目的 1.求出各种排队系统的规律性，使设计人员掌握这种规律，设计出最优化的排队系统； 2.使管理人员掌握这种规律，调整与控制排队系统使它处于最佳运营状态 design analysis 主要内容 一 排队论的基本概念 2. 排队系统的三个基本要素 输入过程 排队规则 服务窗 2.排队系统的三个基本要素 一、输入过程 顾客到达时间间隔可分确定型（如定期航班）和随机型（看病的病人） 顾客源可以有限或无限 顾客到达系统的方式可以逐个或成批 顾客到达系统可以是独立的或者相关的，输入过程可以是平稳、马氏、齐次的等 2.排队系统的三个基本要素 二、排队规则 损失制－ 顾客到达系统时，如果系统中所有服务窗均被占用，则到达的顾客随即离去 等待制－ 顾客到达系统时，如果所有服务窗均被占用，则系统能够提供足够的排队空间让顾客排队等待 混合制－ 是损失制与等待制混合组成的排队系统，此系统仅允许有限个顾客等候排队，其余顾客被拒绝 2.排队系统的三个基本要素 服务规则 先到先服务 后到先服务 随机选择服务 优先级服务（特快专递） 2.排队系统的三个基本要素 三、服务窗 窗口个数可一个或多个 多个服务窗时，顾客可以平行多队排列，串列或者串并同时存在的混合排队 一个服务窗可以为单个顾客或成批顾客进行服务 各窗口的服务时间可为确定型或随机型。服务时间往往是平稳的 排队系统的三大要素就是排队系统的已知条件 输入过程 顾客到达间隔时间的分布 排队规则 队列允许的最大长度 (以便确定系统最大容量n） 服务窗 服务窗个数 m 顾客占用服务窗时间的分布 3. 排队模型的分类与记号 通常用3~5个字母X/Y/Z/m/N/C来表示排队模型 X 顾客相继到达系统的间隔时间 t 的概率分布类型 Y 为服务窗口所耗费的服务时间 ? 的概率分布类型 Z 并行工作的服务机构内服务窗的个数 m 系统内最大排队容量或顾客在系统中排队所允许的最大长度（包括正在服务和排队等待的顾客） N 顾客的最大数量，如果不写则表示顾客源为? C此排队模型的服务规则 3. 排队模型的分类与记号 常见的分布类型 M：(Markov, Memoryless) 负指数分布 D：( Deterministic) 确定性分布 Ek：( k-stage Erlangian) k阶爱尔兰分布 G：(General) 一般分布 GI：(General Independent)一般独立的分布 负指数分布 K阶爱尔朗分布 统计平稳条件下的记号 二 单服务台的排队模型 （Ls, Ws, Lq, Wq） M/M/1 举例 2.M/M/1/N/?(系统容量有限制） M/M/1/N/? 举例 所有服务台是空的概率P0,和所有服务台都在忙的概率 P?,需要下面比较复杂的公式。 M/M/c 举例 (系统容量有限的服务系统) 其他模型 M/M/c/K/K 顾客来源是有限的服务系统. 例如： 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客. M/D/1 服务时间不变的服务系统. D/M/1 确定性到达模式, 及指数分布服务时间. 例如：医生赴约治病的时间表. M/E k/1 服务服从 Erlang 分布. 例如：用相同平均时间去完成一些程序。 排队系统的最优化问题 校园网的设计和调节收费问题 1.1 问题的提出 随着计算机技术的飞速发展，校园信息网已经在全国高校中普及。 某高校拟建一个校园信息网，并与Internet连接，用户可以通过网络通信端口拨号上网。 因此，需要用户的数量，研究通信端口的设计规模。 校园网的设计和调节收费问题 通常