基于排队论的大型超市服务台数的最优设计

Classified Index: O226U.D.C: 519.872Dissertation for the Master Degree in ScienceOPTIMIZATION OF SUPERMARKRT SERVERSNUMBER BASED ON QUEUEING THEORYCandidate:Supervisor:Academic Degree Applied for:Speciality:Affiliation:Date of Defence:Degree-Conferring-Institution:Cai JingfengProf. Wang yongMaster of ScienceProbability Theory andStatisticDepartment of MathematicsJune, 2009Harbin Institute of Technology哈尔滨工业大学理学硕士学位论文摘要排队论是研究拥挤现象的一门数学学科，它通过研究各种服务系统在排队等待中的概率特性，来指导系统的最优设计和最优经营策略。它的理论已广泛应用到生活中的各个领域。对于超市而言，排队系统是其与顾客完成交易的渠道。因此，根据排队论的知识来优化超市的排队系统是非常具有现实意义的。计算机模拟就是利用计算机对所研究系统的内部结构、功能和行为进行模拟。由于排队论的应用已越来越广泛，排队特征、排队规则和服务机构也变得越来越复杂，解析方法已无法求解，而计算机模拟是求解排队系统和分析排队系统性能的一种非常有效的方法，并且计算机模拟具有成本低，运行速度快，准确度高的优点。将排队论与计算机模拟结合起来，是今后排队论发展的必然趋势。在本文中，我们首先介绍了排队系统中几个重要的概率分布、泊松过程、马尔可夫过程和统计检验以及排队论的基础知识，然后根据超市收银排队系统的特征和排队论的知识，将其抽象为数学模型，并在系统达到平衡、顾客在系统中的平均等待时间和平均等待队长小于顾客所允许的最长平均等待时间和最长平均等待队长的条件下，建立了超市收银排队系统的优化模型，并以哈尔滨市的某大型超市为例来考虑其服务台数的优化问题。在本文的最后一章中，我们介绍了离散事件系统仿真模拟的知识，并 用 C+语言编写计算机模拟程序，来模拟优化后的该超市的收银排队系统，并对程序输出的数据进行统计上分析。关键词：排队系统；超市；优化模型；计算机模拟-I-哈尔滨工业大学理学硕士学位论文AbstractQueueing theory is a mathematics subject which studies the crowdedphenomenon. It studies every kinds of service systems probability characteristic inthe queue of waiting, to guide the systems optimal design and optimal operatingstrategy. Its theory has been widely applied to various area of the life. For thesupermarket, queueing system is the channel in which it completes the transactionwith customers. Therefore, the optimization of supermarket s queueing systemaccording to the knowledge of queueing theory has the practical significance.The computer simulation is to simulate the studied systems internal structure,function and the behavior with computer. Because of wide application of thequeueing theory and because of the characteristics and rules of queueing andservice organization being more and more complex, the analytic method has beenunable to solve. But the computer simulation is a very effective method to solve thequeueing system and to analyze queuing systems performance. And the computersimulation has advantages of low cast, fast speed and high accuracy. Thecombination of queueing theory and computer simulation is the inevitable trend ofqueueing theory in future.In this paper, we first introduce several important probability distributions inthe queuing system, Poisson process, Markov process, statistical test and the basicknowledge of queueing theory. Then according to supermarket queuing systemscharacter and the knowledge of queueing theory, we abstract it to mathematicmodel. We establish optimized model of supermarket queueing system under theconditions that the system strikes a balance, the customer s mean waiting time andaverage length of the waiting queue in system is less than the longest mean waitingtime and the longest average length of the waiting queue which they can acceptrespectively. Furthermore, we take a supermarket of Haerbin for example to studyits optimization. In the last chapter, we introduce the knowledge of discrete-eventsystem simulation. We write the computer simulation procedure with the C+ tosimulate the optimized supermarkets queueing system and we analyze the outputdate of procedure.Key words: queueing system, supermarket, optimized model, computer simulation- II -哈尔滨工业大学理学硕士学位论文目录摘要. IAbstract . II第 1 章 绪 论 .11.1 论文的研究背景及意义 .11.2 国内外的研究现状 .21.2.1 排队论的研究现状 .21.2.2 排队系统优化的研究现状 .31.3 本文的主要研究内容 .5第 2 章 预备知识 .62.1 几种重要的概率分布 .62.2 几种重要的随机过程 .72.2.1 泊松过程 .72.2.2 马尔可夫过程 .72.2.3 生灭过程 .102.3 统计检验 . 112.3.1 极大似然估计法 . 112.3.2 c 2 拟合检验 .122.4 排队系统的基础知识 .132.4.1 排队论研究的内容和目的 .132.4.2 排队系统的基本组成部分 .142.4.3 经典排队系统的符号表示 .142.4.4 描述排队系统的主要数量指标 .152.4.5 Little 公式 .152.5 M / M / c / 系统的基础理论 .162.6 本章小结 .17第 3 章 超市收银排队系统的优化研究 .183.1 超市收银排队系统的优化模型 .183.1.1 超市收银服务系统的特征描述 .183.1.2 超市收银排队系统的假设 .18- III -哈尔滨工业大学理学硕士学位论文3.1.3 超市收银排队系统优化模型的建立 .193.2 某超市收银排队系统优化的实例分析 .203.2.1 实际数据的收集与整理 .203.2.2 顾客到达分布的研究 .253.2.3 服务时间服从分布的研究 .273.2.4 系统指标的计算 .293.2.5 系统的优化过程 .313.3 本章小结 .33第 4 章 超市排队系统的模拟 .344.1 计算机模拟的概念 .344.2 离散事件系统模拟 .344.2.1 离散事件系统模拟基本概念 .344.2.2 离散事件系统模拟的基本步骤 .354.2.3 离散事件系统的仿真策略 .354.2.4 仿真输出数据的分析 .364.3 超市收银服务系统的模拟 .384.3.1 随机数的产生 .384.3.2 模拟的目的 .384.3.3 系统的性能指标 .394.3.4 顾客流程与仿真模型活动分析 .394.3.5 模拟运行和数据分析 .434.4 本章小结 .45结论.46参考文献 .47哈尔滨工业大学硕士学位论文原创性声明 .50致谢.51- IV -哈尔滨工业大学理学硕士学位论文第1章绪 论1.1 论文的研究背景及意义排队现象是我们生活中常遇见的现象，例如：上下班做公共汽车，等待公共汽车的排队，顾客到商店、超市购物形成的排队，售票处购票形成的排队等。一般来说，当某个时刻要求服务的数量超过服务机构的容量时，就会出现排队现象。排队论 1是专门研究由于随机因素的影响而产生拥挤现象的科学，是运筹学的一个重要分支。它通过研究各种服务系统在排队等待中的概率特性，来解决随机服务系统的最优设计和最优控制。应该安排排队者排几条队伍、设立几个服务台以及如何调配服务工具才能使效用达到最大化以及如何提高队伍移动的效率来减少拥堵的现象，从而减少顾客的平均等待时间 2和平均等待队长，这些都是排队论研究的范畴。排队论起源于 20 世纪初的电话通话。1909 年至 1920 年丹麦数学家、电气工程师爱尔朗（A.K.Erlang）用概率论方法研究电话通话的问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则。 20 世纪 30 年代中期，当费勒(W.Feller)在排队论中引进了生灭过程时，排队论才被数学界承认为一门重要的学科。在第二次世界大战期间和第二次世界大战以后，排队论在运筹学这个新领域中才变成了一个重要的内容。随着对排队论研究的深入，它的理论越来越得到了广泛的应用，扩及到铁路、公路、水路、航空的运输管理，城市交通管理及控制 3、仓库贮运、水库蓄水、银行服务 4、医疗服务5、计算机设计 6、及物流的管理与控制 7等领域。在社会经济迅速发展的形势下，大型超市的数量在全国范围内越来越多，超市成了我们购物经常光顾的地方。但在日常生活中，我们常常看到下述不协调的现象：有时候超市中的顾客较多，而开放的收银台的个数相对较少，致使顾客在收银台前排了很长的队，这样大部分顾客的等待时间就会很长，影响顾客对超市的满意度；而有时进入排队系统的顾客较少，超市开放的收银台的个数又相对较多，从而导致收银员闲置，这对于提高超市的收益来说是非常不利的。所以，对于超市的经营者来说，在一天中的各个时间段内，应该开放多少个收银台数，显得尤为重要。因为只有这样才能一方面降低成本，另一方面获得顾客的满意度，总的来提高超市的整体收益，进而使系统达到最佳的运行状-1-哈尔滨工业大学理学硕士学位论文态。随着零售业的迅速发展及人们生活水平的不断提高，大型超市的数量大量的增加，这就导致他们之间的竞争日益激烈。 并且随着生活节奏的加快，人们更加珍惜时间，越来越没有耐心长时间排队。因此，作为服务场所的超市或商场，其与每位消费者完成交易的最终渠道排队系统就显得特别的重要。这是因为排队系统是超市和顾客接触的一个平台, 排队系统服务质量的好坏将会直接影响到超市在消费者心中的形象, 从而影响超市的整体效益。因此，优化排队系统 8是超市的经营者面对现实必须要解决的问题。而要从根本上解决排队问题,超市必须在可接受的经营成本下，尽可能的减少顾客的等待时间和等待队长，来获得顾客的满意度。只有这样，在同等条件的竞争下，该超市才具有较强的竞争力。由于排队系统是一个随机服务系统，顾客的到达和收银员对顾客服务时间都是随机的，因此，超市如果开放的收银台数目过少,将会导致顾客的等待队长和等待时间很长,引起顾客不满，从而导致顾客流失；若超市开放的收银台数目过多, 虽然可以减少顾客的等待时间和缩短顾客的等待队长, 但这样将会增加收银员的空闲时间，致使企业的经营成本增加。这就是上述提到的在超市或商场经常见到的现象。所以，管理者或经营者必须考虑如何在这两者之间取得平衡，一方面可以提高服务质量，另一方面可以降低经营成本。因此, 如何根据顾客流量及服务员对顾客的服务水平来动态地、合理地开放收银台的数目，是大型超市或商场等这类随机服务行业要解决的问题。所以，利用排队论的知识来研究如何根据不同时间段的不同客流量来动态的开放收银台的数目是非常有现实意义的。1.2 国内外的研究现状1.2.1 排队论的研究现状自 Erlang 开创排队论以来，排队论经历了近百年的发展历史，取得了一系列重要的结果。经典排队论主要研究和处理各种连续时间系统，已经形成了非常成熟的理论。国外很多作者对经典排队系统的扩展进行了比较详细的研究，例如考虑系统中有不耐烦的顾客 9-12以及有中断 13的情况等等。休假排队系统 14和可修排队系统是两类更广泛、更复杂的排队系统，是近年来比较活跃的研究方面。国内的田乃硕、徐秀丽、马占友、唐应辉等人在这方面做出了很多的贡献。徐秀丽、田乃硕在文献 15中使用了生灭过程的方法重新分析了工作休假的 M / M / 1排队，对稳态指标分布给出了更简单和直观的表示，并揭-2-哈尔滨工业大学理学硕士学位论文示了工作休假排队系统的随机分解规律。李继红和田乃硕在文献 16中研究了带有休假中止的 M / M /1工作休假排队系统。在文献 17中 Wu 和 Takagi 将工作休假模型分析扩展到 M / G / 1排队，在文献18中， Baba 使用了矩阵几何解方法研究了多重工作休假的 GI / M /1 系统，在文献 19中， Banik、 Gupta 和Pathak 讨论了有限等待场所的 GI / M /1/ N 工作休假模型，得到顾客到达前夕和任意时候的队长分布、稳态等待时间分布和消失概率等结果。随着计算机科学和信息技术的发展，激发了人们对离散时间系统的关注和探索，离散时间排队系统 20的研究正是在这种背景下发展起来的。由于离散时间排队更适合计算机系统的建模和性能分析，所以引起了大批排队论和通信工程专家的广泛关注，并迅速产生了大量的理论分析及实际应用成果。在文献 21中，马占友等提出了一个新的算法，用 Bernoulli 闸门服务来模拟 Geo / G /1双重假期模型。离散时间模型不仅丰富和扩展了经典排队论的研究，而且为计算机系统和通信网络的优化设计与性能分析提供了理论基础和数学工具。1.2.2 排队系统优化的研究现状排队系统的最优化 1就是通过调整和控制排队系统使其处于最佳的运营状态。研究排队系统的根本目的在于以最少的投入得到更大的效益。排队系统的最优化问题分为系统的最优设计和对已有系统的最优运行控制，前者也称为静态最优化，是指在服务系统设置之前，对未来运行的情况有所估计，使设计人员有所依据，例如输入结构与服务系统的最优设计、排队规则的最优设计等，这类问题一般较容易求解。后者也称为动态最优化，是指对已有的排队系统寻求最优运行策略，例如如何经营可使目标函数达到最优值，它是时间的函数，解决起来比前者要困难复杂的多，而且对不同系统控制的最优化问题，常常必须采用一些特殊的技术来处理，比如采用马尔可夫决策过程22，使用相对优先顺序 23的方法等。近几年内诸多学者都对排队系统的优化问题及其性能分析作了较为深入的研究，得到了一些比较好的结论，这方面的专著和论文也层出不穷。例如Boris M. Miller 在文献24中提出了用动态规划的方法来优化排队系统，在文献25中，Jau-Chuan Ke 提出用直接搜索算法来优化服务台不稳定且是双重休假策略的 M / M / c 有限缓冲排队系统，在文献26中，Kut C .So 提出根据拥挤指标 K 的值来优化收银台的数目，例如若系统中此时开放 m 个收银台，有 n 个顾客在系统中排队，若nm K ，则应再开一个收银台，若n nm m -1，则开-3- K 哈尔滨工业大学理学硕士学位论文放的收银正好，若nm -1 K ， 则 应 该 关 闭 一 个 收 银 台 。 在 文 献 27 中 ，Jongwoo Kim 等人探讨了 M / G /1排队模型的最优服务策略。一般来说，如果提高服务员的熟练程度或收银台的数目，均能提高服务效率，从而减少顾客的等待时间与等待队长，但这会增加经营的成本；但如果开放的收银台数目相对较少的话，就会影响顾客的满意度，因此，对于一个排队系统的设计或运行管理，就需要考虑顾客与服务双方的利益，以便在某种合理的指标上使系统达到最优化。对大多数实际问题而言，输入可以看作是由客观条件决定的，不受控制的（有时也可以采用控制输入的手段），因此，解决这种问题的关键是确定服务率或服务台或选取顾客的服务规则或这几个量的组合，使之在某种意义下系统达到最优 1。我们从费用结构上来考虑系统的最优设计问题，一般来说系统中有两种费用：一种是等待损失费即每个顾客在系统中逗留单位时间的费用，另一种是服务成本费用即每个服务台单位时间内的费用。令总费用为顾客等待损失费用与服务机构的服务成本费用之和，则当总费用的最小值存在时，对应的服务台数即为最优服务台数。考虑在一个排队模型中，设每个顾客在系统中逗留单位时间的损失费用为e 元，每个服务台单位时间服务成本为 a 元，则单位时间内平均损失总费用为F (c) = eL(c) + ha其中 L(c) 表示系统中开放 c 个服务台时顾客的平均等待队长。由上面的分析我们知道，使总费用 F (c) 最小的 c 即为最优的服务台数。即最优的服务台数 c* 应该满足下面的不等式组：F (c* ) F (c* -1) * *将 F (c) 代入得eL(c* ) + ac* eL(c* -1) + a(c* -1) * * * *化简整理得L(c* ) - L(c* +1) ae L(c* -1) - L(c* )由上式求出满足条件的 c*，就是最优的服务台数 28,29 。但是在现实生活中，顾客的等待损失费用是很难估计的。有很多学者在这方面进行了研究。例如，在文献30中， Zhe G.Zhang 讨论了具有双重休假策-4-F (c ) F (c + 1)eL(c ) + ac eL(c + 1) + a(c + 1)哈尔滨工业大学理学硕士学位论文略和二层限制条件的 M / G / 1 /排队模型的优化问题, 即服务员在二层限制的条件下，根据不同的队长来确定开放服务台的数量，但其前提假设是顾客平均等待费用是已知的且是线性的 8。在文献31中，Suresh Radhakrishnan 提出了一个简单的成本分配方案，通过对总的成本用逗留单位时间的损失费用加权来划分服务成本，同样模型的前提还是假设顾客的等待费用为已知的。在文献32,33中，作者对不同排队模型的最优价格进行了深入的探讨。在很多文献中，顾客在系统中逗留单位时间所产生的损失费用要么假设为一个常量，要不就是一个简单的线性函数。但在实际生活中，来自不同人群的顾客的等待损失费用往往很难确定，并且即使是同一个人他在不同时间的等待损失费用也是不同的，因此这种做法在现实中往往是欠缺的。1.3 本文的主要研究内容本文是从另一个思路来考虑服务台数最优设计的问题，主要内容如下：（1）首先我们介绍了相关的基础知识，包括 Poisson 过程、生灭过程、马尔可夫过程、统计检验以及排队论的知识，为后面的研究打下坚实的基础。（2）根据超市收银服务系统的特征描述，并在一定的假设条件下建立了超市收银排队系统的排队模型。然后，考虑在系统达到平衡、顾客的平均等待时间小于顾客所能接受的最长等待时间、顾客的平均等待队长小于顾客所能接受的最长等待队长的条件下，建立了超市收银排队系统的优化模型，最后以哈尔滨市的某大型超市为例来考虑其服务台的优化问题。（3）用计算机模拟优化后的超市排队系统，通过对系统中顾客的到达事件、离去事件等进行分析，用事件调度的方法来编写仿真程序，输出系统的各项数量指标，并对输出数据进行了统计上的分析。-5-哈尔滨工业大学理学硕士学位论文第2章 预备知识2.1 几种重要的概率分布1.定长分布定义 2.1设随机变量 X 以概率 1 取常数 a ，即 P X = a = 1，则称 X 服从定长分布或单点分布。它的概率分布函数为0, t a1, t a2.负指数分布定义 2.2一个连续型随机变量 X ，若它的分布密度函数为le-lt , t 0 0 , t 0)为常数,则称随机变量 X 服从参数 l 的负指数分布，其概率分布函数为1 - e-lt ，t 0 0定理 2.1 设连续型随机变量 X 服从参数为 l( 0) 的负指数分布，则(1) 对任意 t 0，s 0 ，有PX t + s | X s = PX t = e-lt(2) 对 任 意 一 个 与 X 相 互 独 立 的 非 负 随 机 变 量 Y ， 和 任 意 t 0 ， 在P X Y 0的条件下，有PX Y + t | X Y = PX t = e-lt我们把负指数分布的这个性质称为“无记忆性”或“无后效型”。正是因为负指数分布具有这个性质，其在排队论和可靠性理论等领域中起着非常重要的作用。3.泊松( Poisson )分布定义 2.3 若离散随机变量 X 的概率分布律为：pi = PX = i =l ii!e-l ， i = 0,1, 2, 其中 l( 0)为常数，则称 X 服从参数 l 的泊松( Poisson )分布，其期望平均值为-6-F (t) = PX t = f (t) = F (t) = ，t 0哈尔滨工业大学理学硕士学位论文EX = l ，方差为 DX = l 。2.2 几种重要的随机过程2.2.1 泊松过程定义 2.4考虑单个到达的输入过程，令 N (t) 表示在时间 (0, t内到达的顾客数，则 N (t), t 0是连续时间参数的随机过程（计数过程），如果满足1) N (0) = 0；2) N (t ),t 0有独立增量，即对任取的 n 个时刻： 0 t1 t2 0)为常数，则称 N (t), t 0是泊松过程，也可称为 Poisson流或最简单流 1。定理 2.2 N (t), t 0是参数 l( 0)的 Poisson 流的充分必要条件是 t n ,n 1独立、同参数 l 的负指数分布，其中 t n , n 1为到达的间隔时间序列。定理 2.3 设 N1(t), t 0与 N2 (t), t 0分别是参数 l1 与 l2 的 Poisson 流，且它们独立，则合成流 N1(t) + N2 (t), t 0是参数 l1 + l2 的 Poisson 流。定理 2.4 设 N (t), t 0是参数 l( 0) 的 Poisson 流，每一到达顾客以概率 p(0 p 1) 进 入 系 统 ， 令 N (t) 表 示 ( 0 t 内 到 达 且 进 入 系 统 的 顾 客 数 ， 则N (t), t 0是参数为 l p 的 Poisson 流。2.2.2 马尔可夫过程Markov 过程 34是在理论上和实际应用中都十分重要的一类随机过程。它是由苏联数学家 A.A. Markov(1856-1922)首次提出并进行研究，至今已形成内容丰富、理论完整、应用广泛的一门数学分支。特别的， Markov过程在工程系统中的噪声和信号分析、通信网络的模拟、统计物理学、生物学、数学计算方法、市场预测等领域中都有十分重要的作用和广泛的应用。同时，它在人工智能和人工神经网络等交叉学科中也有重要的应用。Markov 过程的特点是：过去只影响现在，而不影响将来。考虑定义在概率空间 (W, F , P) 上的随机过程 X (t), t T，其状态空间 E 是可列集或有限集。-7-t ) t , n n) )(ls)k -ls, 哈尔滨工业大学理学硕士学位论文定义 2.5 设 X (t), t T是定义在概率空间 (W, F , P) 上，取值于 E 中的随机过程，如果对任意的正整数 n ， t1 t2 tn tn+1 ， tk T (k = 1, 2,态 x1, x2 , , xn+1 E ，都有n +1) 及状PX (tn+1) xn+1 | X (t1) = x1, X