某超市结账柜台排队系统

I 题目 某超市结账柜台排队系统的仿真研究某超市结账柜台排队系统的仿真研究 摘要 近年来 形形色色的超市不断兴起给我们的生活带来了诸多便利 但由于许多 原因 许多超市的结账柜台排队系统并不十分的完善 时常出现排队过长或结账柜 台空闲等等问题 因此 优化超市结账柜台排队系统 缩短结账时间具有极大的意 义 本文将针对永辉超市结账柜台排队系统进行优化 首先会介绍排队论及其相关 知识 对多队列 多服务台等待制 M M c 排队模型进行了重点阐述 其次对 永辉超市的顾客到达时间 顾客服务时间进行调研 在取得原始数据后 代入排队 模型公式进行数据分析与参数计算 得出计算机仿真所需的参数与变量 同时确定 永辉超市的最佳结账柜台的数量 然后运用 FLEXSIM 对结账柜台排队系统进行仿真 以确定该优化方案是可行的 最后 本文给出了一些超市发展的建议 本文的研究结论可能对相类似的排队系统具有一定的借鉴意义 关键词 超市 结账柜台排队系统 建模 仿真 II Title Simulation and research on the checkout counter queuing system of supermarket Abstract In recent years the various supermarkets have brought many conveniences to our life But there are many reasons to lead many supermarket checkout counters queuing system is not very perfect The long queue or spare checkout counters and so on Therefore the optimization of the supermarket checkout counters queuing system can help the supermarket to profoundly shorten the check out time This thesis aimed at to optimize the checkout counter queuing system of Yonghui supermarket At first the knowledge about queuing theory has been introduced and the Multi queue multi service platform for M M c queuing model has focused on Secondly a survey of customer arrival time service time and other basic data has conducted at Yonghui supermarket Next In the raw data by using the FLEXSIM service system to conduct a simulation finding out the optimization is feasible Finally this thesis has give some advices about how to development the supermarket The conclusion of this paper may have some reference significance to similar queuing system Keywords Supermarket Parts inventory Simulation the checkout counter queuing system III 目录 1 绪论 1 1 1 课题研究背景与意义 1 1 2 国内外研究现状 1 1 3 论文的主要研究内容与组织结构 3 1 3 1 论文主要研究内容 3 1 3 2 论文主要组织结构 4 2 论文相关概念与理论 5 2 1 排队论 5 2 1 1 排队论的概念与发展 5 2 1 2 排队论的主要研究内容 5 2 2 排队系统 6 2 2 1 排队系统的组成 6 2 2 2 排队系统的主要指标 7 2 2 3 排队系统的最优化 8 2 3 排队系统的建模 9 2 3 1 系统建模的要求 9 2 3 2 系统建模的原则 9 2 3 3 系统建模的方法 10 2 3 4 系统建模的步骤 10 2 3 5 排队系统建模的符号与分类 11 2 3 6 M M c 模型 11 2 4 排队系统的仿真 12 2 4 1 离散事件系统仿真 12 2 4 2 FLEXSIM 软件的介绍 13 3 数据采集与输入数据建模 14 3 1 数据采集及原始数据 14 3 1 1 数据采集 14 3 1 2 原始数据 14 3 2 输入数据建模 15 3 2 1 仿真方案设计 15 3 2 1 1 方案介绍 15 3 2 1 2 目的 15 3 2 2 顾客到达单位时间服从分布的研究 15 3 2 3 顾客接受服务时间服从分布的研究 18 3 3 系统性能指标计算 20 3 4 系统优化方案 21 3 4 1 增加结账柜台 21 3 4 2 变更为单队列排队系统 21 IV 4 仿真建模 22 4 1 模型假设 22 4 2 仿真建模 22 4 2 1 添加发生器 23 4 2 2 添加其他实体 24 4 2 3 连接实体 24 4 2 4 设置发生器 25 4 2 5 设置暂存区与处理器 27 4 2 6 运行模型 查看 导出统计数据 28 5 仿真结果与优化方案分析 29 5 1 仿真结果分析 29 5 2 优化方案分析 29 6 论文总结 31 致 谢 32 参考文献 33 北京邮电大学世纪学院毕业设计 论文 1 1 绪论 1 1 课题研究背景与意义 排队系统在我们实际的生产生活中有着较为广泛的应用 如计算机网络数据 存储与转发 交通堵塞 医院排队看病 电话占线 超市排队结账等都可以通 过排队系统来解释 同样的 我们也可以通过排队系统对这些活动进行仿真模 拟与研究 用来判定有效并且合理的 可以解决实际问题方案 在数学理论中 研究排队系统的理论是排队论 排队论是运筹学的一个分支 又称随机 排队 系统理论或等待理论 排队系统的基本组成部分主要包括输入过程 排队规 则 服务机构 1 我国市场经济发展 进程中 超市以其 特有的经营方式 与服务理念 渐渐的 成为了人们采买生活用品的主要场所 在超市中 如果服务 设施不足 或服务 效率过低便会使拥挤加剧 排队成龙 但 添加服务设施 的同时会使服务成本 增加又或是 造成系统空闲 因此 通过对排队系统的结构 与规律进行研究 以便更好的设置人员设备 对经营者来 说 降低成本 提高效率 使 排队系 统达到最佳 状态十分重要 本文以 永辉超市 为研究对象和应用背景 在参阅有 关排队论研究和应用文献的基础上 从永辉超市 现状入手 对其结账柜台 排队 系统进行调研 并在所获得的 数据上利用排队论建立超市 结账柜台排队 系统 的仿真模型 再基于 Flexsim 对其进行仿真 根据仿真 模型运行后的相关数 据 对排队系统进行 数据分析 对得出的 结论进行优化 改进 结账柜台排队 系统的效率 从而提高超市的效益 1 2 国内外研究现状 随着现代社会的发展 人民生活水平的不断提高 超市作为我们生活中不可 或缺的一个购物场所慢慢变得越来越重要 这也导致了 现在超市购物结账时 排队现象的 日趋严重 尤其是在各个 大型超市 中 这类问题尤为凸显 2 目 前国内外对 该问题的关注 度逐渐上升 而该问题可以归结 为多队列 多服务 台的排队问题 即在一定的情形下 开启最少的 结账柜台 在保证服务效率又 可将运营成本控制在最低 具体来讲 解决这类排队系统最优化问题需要 通 过排队论之中的优化算法 找出排队系统在某 运行条件下的最优解 北京邮电大学世纪学院毕业设计 论文 2 一般的排队系统组成 部分分为 排队规则 输入过程 以及服务机构 3 通常把需要服务的实体统称为顾客 排队系统中 存在一个对立的 方面 顾客 服务机构 顾客希望进入 排队系统 后立刻结账 希望在 排队系统中停留越 短越好 既是希望 结账柜台 开启的越多越好 这样 就可以减少 顾客在排队系 统中的停留时间 使其所受的损失降低 另一方面 在 服务提供者 看来 增 加结账柜台 时就等同于变相 增加运营成本 虽然 增加结账柜台 可以增加服务 率 但自身的运营成本 也随之增加 同时 如果开放 过多的结账柜台 又十分 容易导致 结账柜台 闲置 这样更加 提升了超市的运营成本 所以 由于各方面 条件的制约 服务提供者一般 不会开放过多的结账柜台 对于排队系统 来说 其设计与运行需要 同时考虑到 顾客与服务 提供者的 利益 促使两方 利益能够 在特定的情况下 达到最优 对于多数实际 情况 输入过程是 不受人为因素控 制 由客观条件决定的的 所以 确定 结账柜台 数量 确定服务率 选取顾客 的服务规则又或是这三个量的组合是处理 的关键 最优化问题要么从 服务机 构 顾客双方考虑 要么单独处理 服务一方 或顾客一方 优化的指标可以是 费用也可以是 时间 4 目前最主要的研究方法则是 从系统仿真 费用优化模型 以及排队论算法 这三方面对排队系统 的优化问题 着手 系统仿真是通过 软件建立能反映真实系统规律的仿真模型 对仿真模型进 行实验 进行 输出数据分析 从而做出 系统的方案评价分析 计算机仿真 的 优势在于对 优化模型和原型系统 的长期模拟测试 5 当确定了一个优化方案 后 就可以 通过软件 在计算机中建立起 优化模型 然后让 优化模型 在计算机 虚拟环境中运行 相对较长的时间 得出一些 系统运行的 数据量化系统 指标 根据这些 数据量化系统指标来评判优化 方案能否起到优化原型 系统的作用 由于计算机 仿真对原型系统 有较强的模拟 能力 因此在 一定的条件下 计算机 仿真可以作为 优化方案应用前的检验 方法之一 6 费用优化模型是以费用为主进行优化的方法 以超市为例 组成超市 排 队系统主要有两部分 分别是顾客和 结账柜台 超市希望可以以较少的 结账 柜台进行服务以减少成本 而顾客则是希望超市增加结账柜台 以减少等待时 间 而结账柜台 的增加势必导致了超市成本费用的增加 因此 出于对两方利 益的考虑 就可以以费用为优化目标 求出超市结账柜台 的最佳台数 令两 北京邮电大学世纪学院毕业设计 论文 3 方的总成本最小 可以设总费用 等于排队损失的费用 加上运营 费用 假设 服 务能力恒定 有结账柜台 数是运营费 用的增函数 结账柜台 数是排队损失费 用的减函数 在最小费用发生 时 对应结账柜台 数量便是最优解 而这种方 法是将顾客等待费用与运营成本 的总和作为目标函数 求得一个最优解 但是 前提是知晓顾客等待时所消耗的费用值 但是在现实生活 中 顾客的等待 时 消耗的费用难以衡量 另一方面 由于现在 市场经济下行业 竞争十分激烈 服务提供者更 应提高和改善 顾客对服务的 满意度 努力将提高服务 评价放在 第一 所以 在现实当中 这种方法 几乎没有可行性 7 排队论算法是通过对对象 到达 服务时间的统计研究 得出 数据指标 等待时间 排队长度 忙期长短等 的规律 然后根据得出的规律来改进 或重组排队系统结构 使得 排队系统既能满足 既定需要的同时 满足其他所 需指标的最优 8 它是运筹学的分支学科 也是研究 排队系统 中排队现象随 机规律的学科 广泛应用于计算机网络 生产 运输 库存等各项资源共享 的随机排队系统 排队论研究的内容有 3 个方面 统计推断 根据资料建立模 型 系统的性态 即和排队有关的数量指标的概率规律性 系统的优化问题 其目的是正确设计和有效运行各个 排队系统 使之发挥最佳效益 也有人将 排队论的理论应用到超市 结账柜台 排队系统 中 9 但是 由于缺乏对数据的科 学收集以及合理的分析处理 使得统计数据不能为管理者的决策提供可靠的信 息 因此合理利用排队论相关知识来分析超市结账柜台 排队系统 具有重要的 现实意义和经济价值 该系统是一个动态的多服务台等待制随机排队系统 通过对该系统中队长 等待时间等指标的分析研究 找出不同时段需要开放的 最佳的结账柜台的数量 以达到优化系统 提高工作效率和服务质量的目的 10 1 3 论文的主要研究内容与组织结构 1 3 1 论文主要研究内容 本文以永辉超市 的结账柜台排队系统为 原型系统 其属于多队列多服务台 排队系统 运用排队论的思想和相关方法对其进行 系统仿真 运用多队列多 服务台 M M c 排队模型对超市结账柜台排队系统进行 分析 对永辉超市 进行了数据采集 与分析 计算出了 相关数据 并且对其进行仿真 以确定合理 性 在发现问题后提出改进策略并 进行优化 北京邮电大学世纪学院毕业设计 论文 4 1 3 2 论文主要组织结构 本文共分为 六章 主要内容如下 本文第一章为绪论 对文章选题的背景进行阐述 对国内外对排队系统研 究现状进行 阐述 对文章的组织结构 以及主要内容 进行阐述 第二章主要介绍排队论的相关知识 介绍排队系统与系统建模的相关概念 介绍离散事件的系统仿真 介绍所使用的仿真软件 FLEXSIM 第三章主要介绍 了目标模型的 情况 以及输入数据建模 的过程 将运用 排队论的 主体思想和操作方法结合到超市结账柜台排队 系统当中 把调查 得 到的数据代入排队模型进行 数据分析 计算出 模型目标 参数 并对 超市结账 柜台排队 系统进行优化 确定该超市在调研时段应当开启的 结账柜台个数 第四章主要介绍了计算机仿真的 操作步骤 对 超市结账柜台排队系统 进 行了计算机仿真 建模分析 同时对超市结账柜台 排队系统的主要相关参数技术 指标进行了分析 并对优化前后超市结账柜台排队系统的主要性能指标进行了 比较 第五章主要介绍了仿真结果的取舍方法进行了介绍 着重介绍了序贯法 并 且通过序贯法对仿真结果以及优化方案进行了分析处理 第六章是全文的工作进行总结 北京邮电大学世纪学院毕业设计 论文 5 2 论文相关概念与理论 2 1 排队论 2 1 1 排队论的概念与发展 排队论 或称随机 排队系统 理论 是通过对服务对象到来及服务时间的统 计研究 得出这些数量指标的统计规律 然后根据这些规律来改进排队系统 的结构或重新组织被服务对象 使得 排队系统 既能满足服务对象的需要 又能 使机构的费用最 为经济或某些指标最优 11 它是数学 运筹学的分支学科 也 是研究排队系统 中排队现象随机规律的学科 广泛应用于计算机网络 生产 运输 库存等各项资源共享的随机 排队系统 排队论研究的内容有 3 个方面 统计推断 根据资料建立模型 系统的性态 即和排队有关的数量指标的概 率规律性 系统的优化问题 其目的是正确设计和有效运行各个排队系统 使之发挥最佳效益 排队系统的一般模型图如图 2 1 1 所示 下图表明每个顾客需按照排队 规则排队等候服务 结账柜台 则按服务规则对顾客进行服务 顾客接受服务后 离开 图 2 1 一般模型图 2 1 2 排队论的主要研究内容 2 1 2 1 排队论的 规律性 在一个排队系统中 队长是随机的 顾客等待时间及服务时间也是随机 的 排队系统的规律性主要是 确定排队队长的 等待时间 服务时间 的分布 排队结构 排队规则 服务台 服务规则 顾客到达顾客离开 北京邮电大学世纪学院毕业设计 论文 6 2 1 2 2 排队系统的最优化问题 对排队系统 来说 把输入 作为随机问题 则解决这种问题就是确定 服务 规则 结账柜台 数量的组合 使 排队系统在达到最优 学习和应用排队论知 识的目的就是 为了解决系统的最优设 计与控制 以达到预期的目标 2 1 2 3 排队系统的统计 分析 对于正在运行的排队系统 要想了解 它的规律性 就需要对其进行 适当 的数据采集 然后通过对采集到的书记进行加工分析来 推断所观测排队系统 的规律 再 通过适当的方法对所发现的问题进行解决 2 2 排队系统 2 2 1 排队系统的组成 在现实中的排队系统是多种多样的 但一般的排队系统主要由以下三部 分组成 即输入过程 排队规则和服务机构 11 输入过程 输入是指顾客到达排队系统 1 顾客总体数 是指顾客的组成情况 顾客可以是有限的 也有可能是无 限的 2 到达方式 是指顾客到达的方式 顾客可能是 单一到达 的 也可能是 成批到达 3 间隔时间 是指顾客相继到达的间隔时间 但到超市购物的顾客属于 随机型的 对于随机型的 间隔时间 要确定其 概率分布 4 顾客到达 是指顾客的到达 是否相互独立 即之前到达的顾客对后续 顾客有没有影响 排队规则 排队规则指的是 排队系统 是否允许排队 顾客愿不愿意接受 排队 在 排队系统 允许排队等待的情形下 其服务顺序是什么 排队规则一般 分为 损失制 等待制与混合制三种类型 1 损失制当顾客到达服务机构时 如果所有的结账柜台 都被占据 此 时的服务机构又不允许顾客等待 那么顾客只有自动离开到其他地方接受服 务或者被迫放弃服务要求 顾客当即离去的称为即时制或称损失制 北京邮电大学世纪学院毕业设计 论文 7 2 等待制指的是当顾客到达服务机构时 如果所有结账柜台 前都有顾 客在接受服务 结账柜台 没有空闲 这时顾客就会自动加入队列排队等待服 务 一直到服务完成后才离开 3 混合制 是指这是由损失制与等待制共同组成的系统 在这类系统中服 务机构只允许有限 数量的顾客等待 当顾客的数量超出一定数量之后 多余的 顾客就要离开 像这样的系统就是混合制系统 另外有些顾客在队长短的时候 往往选择等待 在队长很长的时候就没有耐心不愿意等待而选择离开 有的系 统则规定顾客的等待时间不能超过某时间T 否则就要离开 以上这些都属于 混合制系统 服务机构 服务机构按照机构形式和工作情况来看有以下几种情况 1 结账柜台 数量是指服务机构中 结账柜台 的数量不是固定不变的 可 以有一个或者多个 结账柜台 2 结账柜台 排列是指在有多个 结账柜台 的系统中 结账柜台 的排列有 多种情形 主要有 单队 列单服务台的情形 单队列多服务台的情形 多队 列多服务台的情形 3 服务规则是指服务台的服务方式可以对单个顾客进行 也可以对成批 顾客进行 4 服务时间 分为确定型和随机型 实际中 服务时间都是随机型的 需 要确定它的概率分布 2 2 2 排队系统的主要指标 在使用排队论解决问题 的时候 要确定模型类型 同时通过数据采集 来 确定的顾客到达间隔 的时间分布和服务时间分布 其他的因素都是在问题提出 的时候给定的 11 解决排队问题的 目标是提高排队系统效率 评价系统性能 并确定 排队 系统参数 最优值 所以要确定基本的数量指标 通过数量指标我们来判断系 统运行的 好坏 解决排队 系统的问题要先确定这些数量指标的概率分布 排 队论中的性能指标有两类 一是瞬时性能指标 另一类是稳定性指标 它指的 是在经过足够长的运行时间之后 排队系统所处的状态 这时 t 的各 个性能指标不再随时间 t 的变化而发生变化 工作状态处于稳定 由于本文 北京邮电大学世纪学院毕业设计 论文 8 主要对稳定性能指标 做研究 故不再对瞬时性能指标进行赘述 Ls 平稳状态下系统的平均对长 即系统内顾客数的均值 Lq 系统的平均等待对长 即系统内排队等候的顾客的均值 Ws 指一个顾客 从进入到离开 系统的平均时间 Wq 指一个顾客在系统中的平均等待时间 忙期 Tb 服务台服务时间长度 2 2 3 排队系统的最优化 排队系统的最优化就是通过 变更排队 服务规则 使排队系统 处于最佳 的运行状态 排队系统的最优化 有两类 设计最优化和控制最优化 设计最优 化的目的是使 服务台达到最大的 效率 控制最优化是对于一个 确定的系统 怎样运行才能使目标达到最优值 排队系统由三个方面组成 即输入过程 排 队规则和服务机构 输入过程 当作顾客 在排对系统的组成中顾客方面希望能 在进入排队系统 后立刻得到服务 他们 不希望在系统中停留较长时间 因而 希望开放更多 服务台 但反过来说的话 增加服务台就会增加 运营成本 虽 然提高了服务效率 但 运营成本 也随之增加了 与此同时 开放的服务台过 多非常容易造成服务台 的闲置 这样 就会降低服务台的利用率 由此可见 排队系统的设计与运行 需要 尽量顾及到售卖 双方的利益 以便在某种 情况 下使两方的利益达到最优 最大化 多数问题 输入 数据可以看作是不受控 制的 因此 解决这种问题的实际就是确定服务规则或服务台数量或这它们的 组合 使系统达到最优 最优化要么从 提供服务的 一方进行考虑 要么进行 双方综合考虑 优化的指标 既可以是费用 也可以是 时间 11 若仅从费用这个方面进行考虑的话 那么使得等待时顾客所损失的费用与提 供服务一方的运营成本之和最小即为最优值 同时也是最高服务水平 在费 用模型中总费用 即为服务成本费用 与顾客排队损失费用 之和 服务成本费用 和排队损失费用 都是服务水平的函数 当总的费用最低的时候 它所对应的服 务水平即为最优服务水平 假定每个顾客在系统内等待单位时间的损失费用为 元 每个服务台单 位时间的服务成本为 y 元 那么单位时间内的平均损失的总费用为 f c Ls c cy 式 2 1 北京邮电大学世纪学院毕业设计 论文 9 其中 Ls c 表示开放 c 个服务台 时系统中的等待队长 那么使得总费用 f c 最小的 c 值即为应开放的最优 的服务台数量 为求出最优的c 值 可 采用边际分析法 即所求的c 必须同时满足 f c f c 1 式 2 2 f c f c 1 式 2 3 即 Ls c yc Ls c 1 y c 1 式 2 4 Ls c yc Ls c 1 y c 1 式 2 5 由上式即可求出 c c 即为所求的最优服务台数 作为一个 经营者 一项主要 工作就是根据 实际的顾客 到达规律 对 排队 系统中的各种 排队规则 服务台数量 进行调节 使 排队系统处于一个 良好的 运行状态 使系统能在优化后的整体运行效率有所提高 并且控制整个系统的 运行成本 在满足系统需求的同时控制整个运行成本 又或者在系统运行之 前 依据以往顾客到达分布规律对系统进行调整 并且制定合理的服务规则 从而使系统拥有较好的适应性 能够最大的满足售卖双方需求 2 3 排队系统的建模 2 3 1 系统建模的要求 对于系统建模 的要求可以 归为三条 现实性 简明 化 标准化 1 现实性即在一定程度上能够 很好地反映出系统的实际 状态 把系统特 征和关系反映 出来 又不影响真实 性 2 简明化既是在满足现实 化的基础上 尽量使模型简洁易懂 3 标准化既是建立系统模型时 应尽量采用标准化模型 以上要求的三条 常常相互抵触 因此 要根据 目标系统的具体情况 按照 顺序进行选择 2 3 2 系统建模的原则 建立系统模型的基本原则主要有以下几点 1 现实性原则 要求仿真 模型能准确的反映目标系统 北京邮电大学世纪学院毕业设计 论文 10 2 简明化原则 系统模型不是 目标系统本身 因此 在满足现实性的基 础上 去掉 无关的内容 从而简化 模型 便于 后续处理以及模型工作量 3 适应性原则 仿真模型应当具备一定的外部环境适应性 4 借鉴性原则 如果存在标准化 模型应当尽量采用标准化模型或修改后 的标准化模型 既可提高效率 又可增加仿真模型的可靠性 2 3 3 系统建模的方法 针对不同的系统对象 可以采取不同的方法建模 其中主要的方法如下 1 推理法指对于内部结构和特性已经清楚的系统 即所谓的 白箱 系 统 例如大多数的工程系统 可以利用已知的定律和定理 经过一定的分析和 推理 得到系统模型 2 实验法指对于那些内部结构和特性不清楚或不很清楚的系统 即所谓的 黑箱 或 灰箱 系统 如果允许进行实验性观察 则可以通过实验方法测 量其输入和输出 然后按照一定的辨识方法 得到系统模型 3 统计分析法 指对于那些属于 黑箱 但又不允许直接进行实验观察的 系统 例如非工程系统多数属于此类 可以采用数据收集和统计分析的方法来 建造系统模型 4 类似法指建造原系统的类似模型 有的系统 其结构和性质虽然已经清 楚 但其模型的数量描述和求解却不好办 这时如果有另一种系统其结构和性 质与之相同 因而建造出的模型也类似 但是该模型的建立及处理要简单得多 把后一种系统的模型看成是原系统的类似模型 利用类似模型 按对应关系就 可以很方便地求得原系统的模型 例如很多机械系统 气动力学系统 水力学 系统 热力学系统与电路系统之间某些现象彼此类似 特别是通过微分方程描 述的动力学方程基本一致 因此可以利用成熟的电路系统来构造上述系统的类 似模型 5 混合法 指大部分系统模型的建造往往是上述几种方法综合运用的结果 2 3 4 系统建模的步骤 1 明确仿真建模目的 与要求 2 对系统进行一般语言描述 3 分析系统 相互关系 北京邮电大学世纪学院毕业设计 论文 11 4 确定模型结构 5 确定模型可能用到的 参数 6 输入数据建模 7 数据分析处理 2 3 5 排队系统建模的符号与分类 影响排队模型的分类方法最大的特征有三个 11 第一个是相继顾客到达 间隔时间的分布 第二个是系统服务时间的分布 第三个是系统服务台的个数 根据这三个特征进行分类 并用一定的符号进行表示 称之为 D G Kendal 记号 它的符号表示是 X Y Z 其中 X 表示顾客相继到达间隔时间的分布 Y 表示服务时间的分布 Z 表示并列的服务台个数 在排队论中一般令 M 表示负指数分布 D 为确定型分布 Ek 为 k 阶爱 尔朗分布 G 为一般分布 GI 为一般相互独立的时间间隔分布 如 M M c 排队模型表示顾客相继到达间隔时间和服务时间均服从负指数分 布 系统内设有 c 个服务台 系统容量无限扩大的等待制排队模型 在 1971 年一次关于排队论符号标准化会议上决定 将 D G Kendal 记 号 扩充成为 X Y Z A B C 其中的前三项的含义不变 后三项的意义分别是 A 表示系统的容量限制 即可容纳的最多顾客数 B 表示顾客源的数目 C 表示服务规则 2 3 6 M M c 模型 在 M M c 中 假定顾客到达过程服从参数为 的泊松分 布 顾客的服务时间服从参数为 的负指数分布 顾客的到达时间和服务时 间是相互独立的 并且系统中有c 个服务台 如果顾客到达时 服务台全部 处于繁忙的状态 则进行等待 在多队列多服务台排队系统 排队模型中 我们有如下的定理 若 X t 表示时刻 t 系统中的顾客数 队长 则 X t t 0 是状 态空间 E 0 1 2 且 北京邮电大学世纪学院毕业设计 论文 12 生率为 k k 0 1 2 灭率为 k k k 1 2 k c k c 1 的生灭过程 11 2 4 排队系统的仿真 2 4 1 离散事件系统仿真 仿真技术是以数学理论 相似原理 信息技术 系统技术及其应用领域有关 的专业技术为基础 以计算机和各种物理效应设备为工具 利用系统模型对实 际的或设想的系统进行试验研究的一门综合性技术 具有安全性 经济性 可 重复性等特点 11 离散事件系统和连续系统在性质上是完全不同的 这类系统中的状态在时间 上和空间上都是离散的 像交通管理 各种通讯系统和社会经济系统等都属于 离散事件系统 在该类系统中 各事件以某种顺序或在某种条件下发生 并且 大都具有随机性的特点 或者是由于随机性质的输入 所以使得难以用常规的 方法研究解释它们 具体步骤如下 1 系统建模 离散事件系统的模型一般可以用流程图或网络图的方式来描 述 它们反映了临时实体在系统内部经历的过程 永久实体对临时实体的作用 以及它们之间的逻辑关系 2 选择仿真算法 离散事件系统的仿真算法包括两方面的内容 其一是如 何产生所需的随机变量 其二是采用怎样的仿真方法对离散事件系统进行仿真 即仿真策略 仿真的方法 主要有事件调度法 活动扫描法 进程交互法 三 阶扫描法 三阶段法 等 3 建立仿真模型 根据已经确定的仿真算法 建立被仿真系统的计算机模 型 它是系统状态转移的动态描述 包括系统状态变量的定义 系统事件及其 有关属性定义 仿真钟的定义 仿真钟是仿真模型中必不可少的部件 它的推 进方法由仿真算法决定 4 设计仿真程序 仿真程序是仿真模型的实现 可以使用通用计算机语言 或专用仿真语言 如 GpSS SLAM SIMAN 编写 北京邮电大学世纪学院毕业设计 论文 13 5 仿真结果分析 由于离散事件系统输入固有的随机性 每次仿真运行所 得到的结果仅仅是随机变量的一次取样 同时 当仿真对象复杂时 不可避免 会碰到一些问题 包括模型扰动对仿真结 果的影响 以仿真为依据的系统推断 和决策的可行度等 主要的分析方法有灵 敏度分析 比对分析方法 统计学方 法 2 4 2 FLEXSIM 软件的介绍 Flexsim 是美国 Flexsim 公司开发的 迄今为止世界上第一个在图形环境 中集成了 C IDE 和编译器的仿真软件 在这个软件环境 C 不但能够直接 用来定义模型 而且不会在编译中出现任何问题 Flexsim 是 PC Base 的数 字虚拟企业的仿真系统 来建立各种经营 管理 制造等模型 并且可在微软 公司的 Windows 98 NT Windows 2000 及 Windows XP 等不同作业平台上执行 的全服务台化 3D 专业仿真软件 通过预先创建系统模型 可以考察各种假设的场景 同时不会产生改变实际 系统时所面临的中断 成本和风险 应用范围广泛的系统和过程中 任何制 造业 物料处理和业务流程快速 轻易 高效的描述出来 同时Flexsim 的 资料 图像和结果都可以与其它软件公用 它可以从Excel 表读取数据和输 出数据 可以读取线上事实数据 以作分析功能 Flexsim 也允许用户建立自己 的实体来满足用户自己的 仿真建模要求 北京邮电大学世纪学院毕业设计 论文 14 3 数据采集与输入数据建模 3 1 数据采集及原始数据 3 1 1 数据采集 本文数据主要是在两个周末共四天的9 00 10 00 的时间对永辉超市的结 账柜台排队系统进行采集的 主要采集的项目为顾客到达时间以及 结账时间 其中结账柜台 开启数量为 3 个 而超市顾客量处于逐渐增长时间 处于结账 柜台钱的队伍也在逐渐加长 3 1 2 原始数据 表 3 1 为部分原始数据 表 3 1 原始数据 顾客到达时间 到达时 间间隔 min 与前一位 顾客的间 隔时间 min 结账时间 second 1 9 000 0 27 2 9 055 5 21 3 9 077 2 23 4 9 1212 5 29 5 9 1818 6 36 6 9 2121 3 61 7 9 2424 3 103 8 9 2828 4 38 9 9 3131 3 66 10 9 3737 6 17 11 9 4040 3 18 12 9 4444 4 23 13 9 4848 4 52 14 9 5454 6 21 15 9 5757 3 23 16 10 0060 3 44 北京邮电大学世纪学院毕业设计 论文 15 3 2 输入数据建模 3 2 1 仿真方案设计 3 2 1 1 方案介绍 由于通过直观判断 目前原型系统的处理能力不能满足世纪需求 所以 通过采集到的数据对原型系统的性能指标进行分析计算并评判系统 同时提出 系统的改进方案并对原型系统和改进方案进行仿真实验 通过仿真结果分析以 及优化后的相关性能指标与原型系统进行对比选择 3 2 1 2 目的 通过这次对超市结账排队系统的仿真研究 希望能够对永辉超市目前的结账 排队系统进行分析 同时查找出其可能存在的问题并提出针对性的改进意见 通过二次建模比对 提出合理的优化方案 改善原型系统的等待结账顾客排队 过长 等候时间过久的问题 提高超市的客户体验 3 2 2 顾客到达单位时间 服从分布的研究 对顾客的到达情况统计整理如表3 1 所示 表 3 2 顾客到达数 开放结账柜台的数量 c 到达时间 3 序号分组频率 10 126 21 241 32 331 43 434 54 527 65 622 76 713 87 82 98 91 109 100 北京邮电大学世纪学院毕业设计 论文 16 通过对原始数据进行 整理计算 我们可得到顾客 在单位时间内 的平均到 达时间为 0 2736 分钟 单位时间内的 平均到达率 为 3 6548 人 分钟 且可绘 制线图如图 3 1 所示 图 3 1 顾客到达单位时间概率线图 通过比较 图 3 1 中趋势线与泊松分布质量曲线相似 所以假设顾客到达 单位时间服从泊松分布 拟合优度检验是利用样本 数据对总体分布做出推断的一种方法 检验 总体是否服从理论分布 11 其方法是把样本分成 K 个互斥的类 然后根据要 检验的理论分布算出每一类的理论频数 与实际的观察值进行比较 建立假 设如下 H0 顾客到达率服从泊松分布 Ha 顾客到达率不服从泊松分布 因为含有未知参数 故可以利用 极大似然法 1估计法得出 的估计值 我们就能通过泊松累积分布表求出与不同 值相联系的理论概率 然后将这 一理论频数乘以 c 便得出对每一个 值的理论频数 假设顾客到达服从泊松分布 因此可以得出 式 3 1 0 1 2 1 极大似然法 对未知参数点估计的一种方法 0 11 22 33 44 55 66 77 88 99 10 5 0 5 10 15 20 25 30 35 40 45 频率 趋势 北京邮电大学世纪学院毕业设计 论文 17 极大似然函数表达式为 式 3 2 1 则可以得到参数 的似然函数 式 3 3 1 1 1 1 两边取对数得 式 3 4 1 1 对上式两边进行求导运算得似然方程 式 3 5 1 0 解得 式 3 6 1 又因为 式 3 7 2 2 2 8 557 故在置信水平 0 05 因此认为顾客平均到达率 分布服从参数为 3 65 的泊松分布 3 2 3 顾客接受服务时间服从分布的研究 对顾客的到达情况统计整理如表3 4 所示 表 3 4 顾客服务时间统计表 序号分组频率 10 2561 226 3528 336 4522 446 5519 556 6516 666 7514 776 8511 886 9510 996 1058 10106 1154 11116 1252 12126 1351 13136 1451 根据调查的原始数据可以计算出顾客的平均服务时间为 59 62 秒以及平 均服务率 为 0 017 人 每秒 绘制线图如图 3 2 所示 北京邮电大学世纪学院毕业设计 论文 19 图 3 2 顾客接受服务时间概率线图 通过比较 图 3 2 中趋势线与指数分布质量曲线相似 所以假设顾客到达 单位时间服从负指数分布 下面用极大似然法来估计理论分布中的未知参数 首先我们假定顾客 的服务时间服从负指数分布 则有 式 3 8 0 0 0 在此例中 讨论的是 结账柜台 排队系统在稳 态时 所以可以 取是正 因 此得到参数 的似然函数 式 3 9 1 1 1 对上式两边取对数 式 3 10 1 在对上式两边求导 导数等于0 的似然方程 式 3 11 1 0 解得 式 3 12 2 2 1 2 1 0 故参数 的最大似然估计量 1 所以 1 0 0 1 6 7 7 3 0 9 5人 秒 9 6 3人 小 时 0 25 26 35 36 45 46 55 56 65 66 75 76 85 86 95 96 105 106 115 116 125 126 135 136 145 0 10 20 30 40 50 60 70 频率 趋势 北京邮电大学世纪学院毕业设计 论文 20 下面就统计数据是否符合参数为 0 016773095 负指数分布进行拟合 检 验 概率 其中 ai 和 ai 1 是 13 1719 故在 0 05 的置信水平下 该超市 结账柜台 排队系统 结账柜 台结账时间分布服从参数为 0 02675 的负指数分布 通过上面的 验证得知 该超市 结账柜台排队系统属于 多队列多 结账柜台 M M c 排队系统 3 3 系统性能指标计算 顾客到达系统 服从泊松分布 接受服务 的时间服从负指数分布 若 假设 各结账柜台 平均服务率 相同 且各结账柜台 相互独立 互不干涉 则有模型符 号 N 系统中的顾客人数 顾客平均到达 率 北京邮电大学世纪学院毕业设计 论文 21 平均服务率 服务强度 Lq 稳态平均队长 Ls 平均等待队长 Wq 平均逗留时间 Ws 平均等待时间 c 结账柜台 数量 P0 任意时刻系统空闲的概率 式 3 13 0 1 0 1 1 1 1 1 顾客到达率 为 219 29 顾客服务率为 60 39 则根据服务强度可 求得当前系统的服务强度 1 21 1 系统会非常拥挤 3 4 系统优化方案 3 4 1 增加结账柜台 为使服务强度 1 则取 c 4 都可满足系统要求且不再拥挤 同时 结 账柜台的服务强度不能过低 否则会造成系统资源的浪费所以本文以服务强度 为 80 为标准对系统进行优化 表 3 6 优化后性能指标 结账柜台 数 c 服务强度 空闲概率 P0 平均等 待队长 Lq 平均人数 Ls 平均等待时 间 Wq 平均时间 Ws 490 79 0 0111202 7 9 12 2 3607107 6 3 35436559 572 63 0 0260119 2 1 5 0 36332891 35698373 从表 3 6 中可以看出 开放 4 个结账柜台时 顾客的平均等待时间为 0 03935 平均队长为 9 服务强度为 90 79 系统不会拥挤 的同时也不会造 成服务强度过低 导致系统资源的浪费 而且队长也不会过长 所以开放4 个 结账柜台比较适合 既不会造成系统资源的浪费 同时也能较好的保证顾客的 平均等待时间 北京邮电大学世纪学院毕业设计 论文 22 3 4 2 变更为单队列排队系统 由于变更为单队列后 系统服务强 度并未发生变化所以在此不做考虑 北京邮电大学世纪学院毕业设计 论文 23 4 仿真建模 4 1 模型假设 因为计算机仿真是利用模型 展现原型 系统中发生的 实际过程 并通过对 原型系统 的实验来研究 起系统中 存在问题 所以 需要对所 建模的原型 系统进 行分析 假设 整理 对于一些可排除的客观条件可以 做一些假设把一些实 际问题合理化 下面根据一般排队系统的三 个方面做如下的 整理 4 1 1 输入过程 结账柜台 的服务对象是进入系统的顾客 顾客的到达是随机的 当然顾客 也可以看作是无限的 本文假定顾客单个 随机到来且相互独立 假设顾客到达时间间隔服从 负指数分布 从而 0 t 内到达的顾客 分布服从泊松分布 其参数为 4 1 2 服务规则 顾客到达时 如果有空闲 结账柜台 则结账 若所有的 结账柜台 都在结账 中 则顾客选择 排队较短的队列加入等待 结账 在队列中的排队规则有三种选 择 包括 先到先服务 后到先服务和有优先权的服务 本论文中以先到先服务 为服务规则 4 1 3 服务机构 结账柜台单 次只为一个顾客结账 在排队系统中 结账柜台 台对客户的 服务时间服从参数为 的负指数分布 综上 该超市的结账柜台排队系统属于 一个等待制 M M c 的排队系统 4 2 仿真建模 现已确定 排队系统 的模型为 M M c 其中 c 为结账柜台 的 台数 图 4 1 为该排队系统 的流程图 北京邮电大学世纪学院毕业设计 论文 24 队队列列1 1 队队列列2 2 队队列列3 3 队队列列n n 服服务务台台1 1 服服务务台台2 2 服服务务台台3 3 服服务务台台n n 队列选择顾客到达 离开系统 图 4 1 多队列多服务台 一般模型图 现利用 Flexsim 软件对排队 系统进行仿真 步骤如下 4 2 1 添加发生器 从实体库中拖拽一个发生器放到视图中 如图4 2 1 所示 图 4 2 添加一个发生器到新建模型中 北京邮电大学世纪学院毕业设计 论文 25 4 2 2 添加其他实体 分别将暂存区 处理器 吸收器从实体库中拖拽到试图当中 并按照位置顺 序进行排布 如图 4 2 2 所示 图 4 3 添加其他实体 4 2 3 连接实体 按住 A 键 点击 发生器 然后拖拽到暂存区 连接每个处理器到储存区 连接每个处理器到吸收器 这样就完成了连接过 程 完成连接后 得到了模型如图4 2 3 所示 图 4 4 完成连接实体 北京邮电大学世纪学院毕业设计 论文 26 4 2 4 设置发生器 根据对系统要求以及临时实体 行为特性的要求 对发生器的参数进行设 置 双击发生器打开 参数设置页 如图 4 2 4 所示 图 4 5 发生器参数设置页 设置临时实体种类为 TaskExecuterFlowitem 到达时间间隔为渐近线为 0 比例为 16 4167 随机数流为 1 的指数分布函数 同时勾选0 时刻到达选项 设置完成后如图 4 2 5 所示 图 4 6 发生器参数设置 北京邮电大学世纪学院毕业设计 论文 27 然后对临时实体流进行设置 分别 设置发送至端口为可用排队最短的 同 时勾选使用运输工具 并选择将任务执 行器作为临时实体使用 设置完成如图 4 2 6 所示 图 4 7 设定临时实体流 然后对触发器进行设置 在离开触发中添加设置名称与实体颜色 便于实验 过程中区分临时实体 设置完成后如图4 2 7 所示 图 4 8 设定触发器 北京邮电大学世纪学院毕业设计 论文 28 4 2 5 设置暂存区与处理器 双击暂存区 打开暂存区参数 设置页 修改最大容量 为 10000 因系统 无容量限制 设置实体堆放为水平堆 放 完成后 如图 4 2 8 所示 图 4 9 设定暂存区参数 双击处理器 打开处理器参数设置页 在处理时间的下拉列表框中选择 比例为 59 62 随机数流为 1 的指数分布 如图 4 2 9 所示 图 4 10 设定处理器参数 对其他暂存区和处理器进行如上操作即可 北京邮电大学世纪学院毕业设计 论文 29 4 2 6 运行模型 查看 导出统计数据 在模型运行前 应当先对模型进行 重置 随后点击运行按钮 可以看到 临时实体 shopper 在系统中的运动轨 迹 可以通过速度条来 调整模型运行 速度 在模型运行前可以点击 Dashboard 按钮 然后从左侧实体库中拖拽需要 观测的数据项到模板中 如图 4 2 10 所示 图 4 11 数据面板 在运行结束后 可以通过报告与统计生成Excel 文档 以便后期的数据处 理 北京邮电大学世纪学院毕业设计 论文 30 5 仿真结果与优化方案分析 5 1 仿真结果分析 系统仿真的目标是研究复杂的实际系统 实际系统的动态行为特征就体现在 得到的仿真结果中 那么对仿真结果采用正确的分析方法是离散事件系统仿真 的关键问题之一 运行随机系统仿真模型所得到的结果具有随机性 不能把从单次仿真运行中 获得的系统参数值作为该参数的 真值 而只能作为一个样本数据 需