运营管理(Operations Management) 第12章 作业计划 主讲：季建华教授

等待是日常生活的一部分

什么时候需要排队？

有趣吗？

为什么会出现排队现象？ 顾客 到达 顾客 离开 顾客排队 服务设施 假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间为15分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为每位顾客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。 在以下情况将出现排队现象： 平均到达率（顾客/小时）高于平均服务率（顾客/小时），就像红酸果案例中的情况一样。 顾客到达的间隔时间不一样（随机）。 服务时间不一样 （随机）。 Assume that there is no waiting, the manufacturing lead time is just the sum of all the processing times, i.e. (3/4)*3 + 1 = 3.25 hours. The actual lead time may be higher when transportation time is significant and there is waiting due to work-in-process (WIP) inventory.

你觉得应以怎样的准则排队？ 超市收银 交货期不同时 病人看病 ………

一个排序的例子 四种型号的电视机的装配工时定额 型号 部装定额工时（小时） 总装定额工时（小时） A B C D 15 8 6 12 4 10 5 7

一个排序的例子 A（15） （a）装配顺序为A→B→C→D，总装配时间为48小时 A（15） 部装 A（15） B（8） C(6) D（12）   总装   A(4)   B（10） C(5)   D(7) （a）装配顺序为A→B→C→D，总装配时间为48小时 部装 C（6） B（8） D（12） A（15）   总装   C(5)   B（10） D（7）   A(4) （b）装配顺序为C→B→D→A，总装配时间为45小时 部装 D(12) C（6） A（15） B（8）   总装   D（7） C(5)   A(4)   B(10) （c）装配顺序为D→C→A→B，总装配时间为51小时

为什么要排序？

排序的目标 满足交货期 缩短提前期 降低准备成本 降低在制品库存 充分利用资源 作业排序

排序分类 服务业的排序问题 行业 制造业的排序问题 服务者排序问题 排序问题的分类 排序对象 服务对象排序问题 单服务者排序问题 服务者数量 流水作业排序问题 制造业的排序问题 服务者排序问题 服务对象排序问题 多服务者排序问题 单服务者排序问题 非流水作业排序问题 静态作业排序问题 动态作业排序问题 排序对象 行业 服务者数量 加工路线 服务对象到达

制造业中的排序问题(Schedule Problem in Manufacturing) 1、平均流程时间最短（SOT,SPT, Shortest Operating Time Shortest Processing Time） Fi：流程(Flow Time) wi+ti wi：i工件的等待时间 ti：i工件的加工时间 平均流程 F 总流程：最大流程 Fmax=max(Fi) 优化目标：平均流程↓ t1≤t2≤……tn

制造业中的排序问题(Schedule Problem in Manufacturing) J 1 2 3 4 5 6 t i 8 9 d 24 23 32 13 J 3 6 1 4 2 5 t i 8 9 D F=13.8 Dmax=8 di: i工件规定交货时间(Due Time) Di:交货延期量(Delay Time)

制造业中的排序问题(Schedule Problem in Manufacturing) 2、使最大交货延期量最小 （EDD规则，Early Delivery Date） d1≤d2≤……dn F=15.5 Dmax=0 J 4 3 6 2 1 5 t i 8 9 F 7 10 18 22 31 d 13 23 24 32 D

制造业中的排序问题(Schedule Problem in Manufacturing) 3、混合法 1) 先按EDD排序 2) 找出di＞maxFi的，按SPT排 去掉找出的工件，剩下部分继续循环 ………. F=14.8,Dmax=0 J 4 3 6 1 2 5 t i 8 9 F 7 10 14 22 31 d 13 24 23 32 D 单台设备的使用场合：维修、单工艺，加工中心等

甘特图    

(二) n种工件在两台设备上的流水型排序问题 (Scheduling n Jobs on 2 Machines) 制造业中的排序问题(Schedule Problem in Manufacturing) (二) n种工件在两台设备上的流水型排序问题 (Scheduling n Jobs on 2 Machines) 约翰逊——贝尔曼规则(Johnson-Bellman’s Rule) J4 J1 J2 J3 J5 Fmax=40 最优解 J 1 2 3 4 5 t iA 6 8 12 7 iB 11 9

(三) n种工件在3台机床上加工的流水型排序问题及解法 制造业中的排序问题(Schedule Problem in Manufacturing) (三) n种工件在3台机床上加工的流水型排序问题及解法 转换条件：若min tiA≥max tiB 或min tiC≥max tiB 可得最优解，否则较优解 零件 机床及工时 J 1 2 3 4 A t i 15 8 6 12 B iB 5 C iC 10 7

制造业中的排序问题(Schedule Problem in Manufacturing) ∵min tiA=6≥max tiB=6 ∴可转换 排序方案为：J2 J4 J3 J1 Fmax=48 最优解 零件 机床及工时 J 1 2 3 4 G t iG 18 9 11 H iH 7 10 13

(四) n种工件在m台机床上加工的流水型排序问题及解法(Scheduling n Jobs on m Machines) 制造业中的排序问题(Schedule Problem in Manufacturing) (四) n种工件在m台机床上加工的流水型排序问题及解法(Scheduling n Jobs on m Machines) 1、约翰逊规则的扩展法 组合原则为： tiA= (h=1, 2, ……,m－1) tiB= ,m－k+1 共组合m－1次，每一次组合对应一个顺序，从m－1种顺序的加工周期中挑最小的。 å = h 1 k ik t å = h 1 k i t

制造业中的排序问题(Schedule Problem in Manufacturing) 2、关键零件法(Key Parts Model) 把总工时（ ）最大的零件作为关键零件，记为Jc, 若Max( )= , 则k零件为Jc 1) 除Jc外，凡ti1＜tim的零件，按ti1从小到大排在Jc前 ; 2) 除Jc外，凡满足ti1＞tim的零件，按tim从大到小排在Jc后。 3) 若ti1=tim，相应零件既可排在Jc前，又可排在Jc后 ,得到多个方案，从中选最优。 å = m 1 j ij t å = m 1 j ij t å = m 1 j kj t

制造业中的排序问题(Schedule Problem in Manufacturing) 零件 机床工时 J 1 2 3 4 5 6 M t i1 10 i2 i3 8 7 i4 i5 å = j ij 25 23 15 11 28 40

制造业中的排序问题(Schedule Problem in Manufacturing) 用表格法计算总流程 零件 机床 J 4 5 1 6 2 3 M 8 18 23 27 10 15 28 33 38 17 25 32 36 41 9 22 46 48 M5 11 30 35 50 51 右上角零件等待 左下角机床空闲

制造业中的排序问题(Schedule Problem in Manufacturing) 以上规则也有一些局限性 1) 生产系统(Production System)是动态的，规则不可能考虑到各种变化 2) 规则看不到上游或下游的情况（设备的忙闲等） 3) 看不到其他许多重要因素 如延期交货(Delayed Delivery)所造成的损失 因此可根据规则无法考虑的因素作调整，用专家系统(Expert System)或有交互功能的排序软件

服务业中的排序问题(Schedule Problem in Service Industry) 排序的对象是人而不是物；系统动态与随机性特点比制造业更突出；排序问题与排队模型结合在一起而产生作用 例： 医院病人 等待问题 人流、信息流分离与否 可否挑选医生 价值观 顾客 生产者 长远 市场

服务业中的排序问题(Schedule Problem in Service Industry) (一) 划分需求，进行排序 需求的分类 随机 计划（通过排序，平衡负荷(Load Balance)） 航空公司将乘客划分为工作日商务乘客和周未旅游乘客。 美国某医院对需求分析显示： 非预约病人周一看病人数最多，而其他时间来的相对较少。 非预约——随机 预约——可控——安排在每周后几天，使负荷稳定，减少等待时间。

(二) 排队管理(Waiting Line Management) 服务业中的排序问题(Schedule Problem in Service Industry) (二) 排队管理(Waiting Line Management) 1、排队系统的基本特征 需求群体 排队结构 服务结构 不再有服 务需求 与需求的时间分 布空间分布有关 到达过程 退出 排队规则 服务 离开

服务业中的排序问题(Schedule Problem in Service Industry) 2、需求群体 不同群体需求不同，每一类需求的预期等待时间(Expected Waiting Time)不同 3、排队结构 1) 多条排队(Multi-Line) 2) 单一排队(Single-Line) 3) 领号

服务业中的排序问题(Schedule Problem in Service Industry) 需求群体 同质群体 亚群体 有限的 无限的

服务业中的排序问题(Schedule Problem in Service Industry) 有限排队(Waiting Line with Limited Capacity) 若等待场所无法容纳所有需求服务的顾客，一些人会离去， 这种情况称为有限排队

服务业中的排序问题(Schedule Problem in Service Industry) 2、需求群体 不同群体需求不同，每一类需求的预期等待时间(Expected Waiting Time)不同 3、排队结构 1) 多条排队(Multi-Line) 2) 单一排队(Single-Line) 3) 领号

服务业中的排序问题(Schedule Problem in Service Industry) 排队结构 领号 单一排队 多条排队 有限的 无限的 有限或无限 允许/不允许 移动 快速通道

服务业中的排序问题(Schedule Problem in Service Industry) 优点 多条排队 a) 提供差别服务(Differentiate Service)（超市快速结帐） b) 顾客可选择 c) 有助于减少不加入队伍的现象

服务业中的排序问题(Schedule Problem in Service Industry) 单一排队 a) 先到先服务(FCFS,First Come First Serve) b) 顾客不会看到别的队伍移动得快而着急 c) 插队困难 d) 提高了服务的私密性（一米线 ）

服务业中的排序问题(Schedule Problem in Service Industry) 领号 a) 顾客可四处走动，但必须警觉是否叫到号。 b) 商店可利用“领号”系统增加顾客冲动购物，浏览、多买

服务业中的排序问题(Schedule Problem in Service Industry) 4、服务结构 单队单服务台单阶段的服务排队系统 多队多服务台单阶段的服务排队系统 单队多服务台单阶段的服务排队系统 单队单服务台多阶段的服务排队系统 单队多服务台多阶段的服务排队系统

单队单服务台单阶段的服务排队系统

多队多服务台单阶段的服务排队系统

单队多服务台单阶段的服务排队系统

单队单服务台多阶段的服务排队系统

单队多服务台多阶段的服务排队系统

服务业中的排序问题(Schedule Problem in Service Industry) 5、排队规则 1) FCFS(First Come First Serve) 常用到SPT规则，但服务时间长的不断让位于后到达者，所以先用SPT分类，然后FCFS（超市，快速通道） 2) 最高优先权法则(Highest Priority Principle) 火警、救护车 为减少等待顾客离队可能，应让顾客知道预期等待时间的信息，并使顾客得到定期更新的信息。

服务业中的排序问题(Schedule Problem in Service Industry) 6、调整顾客到达率的措施 1）利用预约系统 控制顾客到达时间 实现最高程度的服务能力利用率 减少顾客等待的时间 提高服务水平 2）采用预订系统 对特定期间的服务需求做出较准确的估计 3）采用差异定价措施

服务业中的排序问题(Schedule Problem in Service Industry) 7、调整服务能力的策略 1）进行有效的人员班次排序 2）利用临时工或兼职人员 3）招聘和培养多技能的员工 4）对组织结构、体制与服务流程进行重组（重复工作 如多封同一信件广告或流程重叠空档 造成能力浪费）（“医患关系紧张的责任”的辩论：仁济医院院长，律师）

排队理论 是二十世纪初在研究电话系统时提出的方法 排队是指顾客或工件排队等待服务或加工 For the bread-making line, baking is the bottleneck since it has the longest cycle time. The cycle time of each bread-making line is 1 hour/100 loaves. Since there are two lines, the cycle time of bread-making is 1/2 hour/100 loaves, which is shorter than the cycle time of packaging. Thus packaging is the bottleneck of the whole process and the output capacity is 133 loaves/hour (since its cycle time is 3/4 hour/100 loaves).

随机到达 我们假设，在某段时间内顾客到达是随机的，互不相关，但平均到达率不变。 顾客到达有许多来源 每个来源到达率很低 顾客到达互不相关 例如，假定平均到达率是每小时16位顾客。但每个小时的实际到达人数是不一样的。 Resource Utilization Packaging machine 100% Packaging operator 40/45 = 88.9% Mixer 1/2 = 50% Oven 1/(2*0.75) = 66.7%

为什么会出现排队现象？ 顾客 到达 顾客 离开 顾客排队 服务设施 假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间为15分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为每位顾客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。 在以下情况将出现排队现象： 平均到达率（顾客/小时）高于平均服务率（顾客/小时），就像红酸果案例中的情况一样。 顾客到达的间隔时间不一样（随机）。 服务时间不一样 （随机）。 Assume that there is no waiting, the manufacturing lead time is just the sum of all the processing times, i.e. (3/4)*3 + 1 = 3.25 hours. The actual lead time may be higher when transportation time is significant and there is waiting due to work-in-process (WIP) inventory.

衡量服务系统表现的尺度 输出率 =单位时间内系统所服务的平均顾客数。 r = 利用率 = 服务时间所占的比例 L = 系统中的平均顾客数 (包括正被服务的) W = 每位顾客在系统中平均逗留时间，即流程时间 (包括接受服务时间) Lq = 在队列中等待的平均顾客数 Wq = 每位顾客的平均等待时间，即排队时间 The same as (1) since cooling is not the bottleneck.

影响等待时间的因素 顾客：以泊松分布方式到达 服务时间： 服务台数： c l = 平均到达率 (单位时间到达的顾客数） M = 平均服务时间 s = 服务时间的方差 服务率（人/小时） ： zz The same as (1) since cooling is not the bottleneck. 服务台数： c

排队理论是设计和改进生产系统的重要工具 排队理论的主要目标是： 由系统的参数（顾客到达率、服务时间、服务台数等等）出发，估计系统的表现，特别是在时间方面的表现。 主要方法： 公式 近似公式 电脑模拟 The same as (1) since cooling is not the bottleneck.

服务台利用率是衡量表现的重要指标 服务台利用率就是每个服务台实际工作时间所占比例。 服务台利用率 = 实例： 平均到达率为每小时10位顾客； 每位顾客平均要求10分钟的服务（服务时间），这样在一个小时内，平均就有100分钟或者说 1.667个小时的工作量； 共有两个服务台，每个可利用的时间为一个小时，这样总计可利用时间为两个小时。 因此服务台利用率为1.667/2 = 83.3%. The same as (1) since cooling is not the bottleneck.

另一种计算服务台利用率的方法 服务台利用率 = 实例： 平均到达率为每小时10位顾客； 每个服务台的平均服务时间为10分钟，这样一个服务台平均一小时可以为6位顾客提供服务； 共有两个服务台； 因此服务台利用率为 10/(2*6) = 0.833 或者说83.3% The same as (1) since cooling is not the bottleneck.

三种重要的关系 “管道原理”: 在一个稳定系统中 利特尔法则： 时间的可加性：在系统中逗留的时间等于服务时间加排队时间： 平均输出 = 平均输入，或者输出率 = l 利特尔法则： 时间的可加性：在系统中逗留的时间等于服务时间加排队时间： The same as (1) since cooling is not the bottleneck.

系统内的平均顾客数 = 平均到达率  平均逗留时间 利特尔法则 根据利特尔法则： 实例1：某医疗机构的平均到达率为每个月50位患者，平均逗留时间为两个月。该医院内的平均患者数为多少？ 实例2：某银行平均每天收到支票金额50万元，支票的平均传送、处理时间为三天。假定年利率为10%，该银行每年在支票交易上的利息损失是多少？ 利特尔法则不仅适用于整个系统，而且也适用于系统的任何一部分。 系统内的平均顾客数 = 平均到达率  平均逗留时间

单个服务台; 任意服务时间分布 一个稳定系统的条件： 利用率小于 1： 计算公式： The same as (1) since cooling is not the bottleneck. s 数值增大就意味着服务时间有更多的可变性。而更多的可变性则会造成更多的拥塞和延误，这样就要等待更长的时间。

实例 1 号系统 2 M ( 分钟 ) 3.0 3.1 s 2.1 1.0 以下是两个计算机系统的有关数据： 顾客的到达率为每小时15位。也就是说 l = 15/60 = 0.25 位顾客/分钟 (注意:使用相同的时间单位！) 1 号系统 2 M ( 分钟 ) 3.0 3.1 s 2.1 1.0 With a batch size of 100 loaves and a setup time of 15 minutes, the cycle time of packaging is now 1/4 + 3/4 = 1 hour/100 loaves. The overall output capacity of the process becomes 100 loaves/hour. One way to increase the output capacity is to use a larger batch size for packaging, which is the bottleneck of the process.

实例（续） 1号计算机系统： With a batch size of 100 loaves and a setup time of 15 minutes, the cycle time of packaging is now 1/4 + 3/4 = 1 hour/100 loaves. The overall output capacity of the process becomes 100 loaves/hour. One way to increase the output capacity is to use a larger batch size for packaging, which is the bottleneck of the process.

实例（续） 2号计算机系统： With a batch size of 100 loaves and a setup time of 15 minutes, the cycle time of packaging is now 1/4 + 3/4 = 1 hour/100 loaves. The overall output capacity of the process becomes 100 loaves/hour. One way to increase the output capacity is to use a larger batch size for packaging, which is the bottleneck of the process. 慢的反而好！

单个服务台；服务时间为指数分布 服务时间为指数分布，那么， M = s =1/m 利用率： 计算公式： The same as (1) since cooling is not the bottleneck. Chase 第11版 P307 如果把到达数量增加一倍(2l)，再把服务率增加一倍 (2m), 等待时间就会减少一半 。这就是排队论的规模经济学。

平均队长与利用率的关系 平均队长（和平均等待时间）与服务台利用率之间的关系不是线性的关系。资产利用率太高会造成服务质量急速下降，因而要权衡利弊。要保证服务质量，就必须保持“过剩的”生产或服务能力。 平均队长 (a) Increasing the capacity of baking would not change the overall output capacity since baking is not the bottleneck of the process. (b) If the cycle time of packaging is increased to 1/2 hour/100 loaves, packaging would have the same capacity as bread-making. The overall output capacity of the process is now 200 loaves/hour since its cycle time is 1/2 hour/100 loaves. 利用率

实例 一个服务台：指数服务时间 到达率 = 10/小时 利用率 平均 排队长度 等待时间 0.2 0.05 0.005 小时 (0.3 分钟 ) 0.5 0.50 (3.0 0.8 3.20 0.32 (19.2 0.9 8.10 0.81 (48.6 0.95 18.05 1.805 (200.3 With a batch size of 100 loaves and a setup time of 15 minutes, the cycle time of packaging is now 1/4 + 3/4 = 1 hour/100 loaves. The overall output capacity of the process becomes 100 loaves/hour. One way to increase the output capacity is to use a larger batch size for packaging, which is the bottleneck of the process.

多个服务台;服务时间为指数分布 利用率： 计算公式较为复杂。我们可使用教材（Chase第8版）中的表 S5-4 或电子表格程序。 如果把到达数量增加一倍(2l)，再把服务人员增加一倍(2c), 等待时间就会减少一半以上。这就是排队论的规模经济学。 The same as (1) since cooling is not the bottleneck.

为何“集中使用”可以提高服务质量？ 独立的系统 在此等待 “集中使用”系统 在此等待

有关排队模型的要点 集中使用的优点 大规模制造或服务设施的规模经济学 将资源组合在一起为所有的顾客提供服务，可以在等待时间不变的条件下，减少所需要的资源总量。如果是两列独立排队，那么客户可能要等那位指定的服务人员提供服务，这位服务人员可能当时正忙得抽不开身，而另一位服务人员却闲着没事干。在集中使用的系统中就不会出现这种现象。 大规模制造或服务设施的规模经济学 在保持同样利用率的情况下减少平均等待时间 在保持同样平均等待时间的情况下提高利用率

有关排队模型的要点 假如平均服务率大于平均到达率，那末等待是由到达和服务时间的变动性造成的。 瓶颈是由两方面原因造成的：利用率太高或可变性太大。 在系统规模不变时，利用率越高，等待时间越长。但两者并非线性关系。利用率越高，等待时间增长越快。 利特尔法则：假如平均到达率不变，平均等待时间与平均等待人数会按比例增长。 利特尔法则 L=lambda*w Lq=lambda*wq

减少等待时间的办法 减少平均服务时间 减少服务时间的可变性 增加服务人员 减少平均到达人数 通过顾客预约等办法来减少到达的可变性 如果能将服务时间的可变性从很大（服务时间的均值等于标准差）减到零(服务时间为常数)，那么平均等待时间将可以减少大约一半。 增加服务人员 减少平均到达人数 通过顾客预约等办法来减少到达的可变性 集中使用服务资源！ 更好地计划和调度

掌握客户的感受:等待心理学 客户所感受到的等待可能与实际的等待有很大的差别。 研究结果表明： 服务越有价值，人们就越愿意多等一会儿。 服务开始之前的等待感觉要比服务过程中的等待要长。 心急会让人觉得等待的时间很长。 不公平的等待比公平的等待要长。 不确定的等待比已知的等待要长。 不明情况的等待要比知情的等待要长。 没事干的时候会让人觉得比有事干的时候要长。 独自等待会让人觉得比大家一起等待要长。