作业计划-运营与物流管理研究中心

第12章作业打算主讲：季建华教授运营治理(OperationsManagement)等待是日常生活的一局部什么时候需要排队？好玩吗？为什么会消失排队现象？假定每小时平均有4位顾客到达，效劳人员为每位顾客的平均效劳时间为15分钟。假设顾客到达的间隔时间正好是15分钟，而效劳人员为每位顾客的效劳时间也正好是15分钟，那么，就只需要一名效劳人员，顾客也根本用不着等待。在以下状况将消失排队现象：平均到达率〔顾客/小时〕高于平均效劳率〔顾客/小时〕，就像红酸果案例中的状况一样。顾客到达的间隔时间不一样〔随机〕。效劳时间不一样〔随机〕。顾客到达效劳设施顾客排队顾客离开你觉得应以怎样的准则排队？超市收银交货期不同时病人看病………一个排序的例子四种型号的电视机的装配工时定额型号部装定额工时（小时）总装定额工时（小时）ABC装B（8）C(6)D（12）

总装

A(4)

B（10）C(5)

D(7)〔a〕装配挨次为A→B→C→D，总装配时间为48小时部装C（6）B（8）

总装

C(5)

B（10）D（7）

〔b〕装配挨次为C→B→D→A，总装配时间为45小时部装C（6）B（8）

总装

D（7）C(5)

B(10)〔c〕装配挨次为D→C→A→B，总装配时间为51小时A（15）A（15）A（15）A(4)A(4)D（12）D(12)一个排序的例子为什么要排序？排序的目标满足交货期缩短提前期降低准备成本降低在制品库存充分利用资源作业排序排序分类排序问题的分类服务业的排序问题流水作业排序问题制造业的排序问题服务者排序问题服务对象排序问题多服务者排序问题单服务者排序问题非流水作业排序问题静态作业排序问题动态作业排序问题排序对象行业服务者数量加工路线服务对象到达制造业中的排序问题(ScheduleProbleminManufacturing)(一)n种工件在单台设备上加工的排序1、平均流程时间最短〔SOT,SPT, ShortestOperatingTime ShortestProcessingTime〕Fi：流程(FlowTime) wi+tiwi：i工件的等待时间ti：i工件的加工时间平均流程F总流程：最大流程 Fmax=max(Fi)优化目标：平均流程↓t1≤t2≤……tnF=13.8Dmax=8di:i工件规定交货时间(DueTime)Di:交货延期量(DelayTime)J1J2J3J4J5J6ti482593di2423863213J3J6J1J4J2J5ti234589Di000800制造业中的排序问题(ScheduleProbleminManufacturing)2、使最大交货延期量最小〔EDD规章，EarlyDeliveryDate〕d1≤d2≤……dn F=15.5Dmax=0J4J3J6J2J1J5ti523849Fi5710182231di6813232432Di000000制造业中的排序问题(ScheduleProbleminManufacturing)3、混合法1)先按EDD排序2)找出di＞maxFi的，按SPT排去掉找出的工件，剩下局部连续循环……….F=14.8,Dmax=0

单台设备的使用场合：修理、单工艺，加工中心等J4J3J6J1J2J5ti523489Fi5710142231di6813242332Di000000制造业中的排序问题(ScheduleProbleminManufacturing)甘特图

约翰逊——贝尔曼规章(Johnson-Bellman’sRule)J4 J1J2J3J5Fmax=40最优解(二)n种工件在两台设备上的流水型排序问题

(SchedulingnJobson2Machines)J1J2J3J4J5tiA681237tiB119534制造业中的排序问题(ScheduleProbleminManufacturing)转换条件：假设mintiA≥maxtiB或mintiC≥maxtiB可得最优解，否则较优解

零件机床及工时J1J2J3J4AtiA158612BtiB3156CtiC41057(三)n种工件在3台机床上加工的流水型排序问题及解法制造业中的排序问题(ScheduleProbleminManufacturing)∵mintiA=6≥maxtiB=6∴可转换

排序方案为：J2J4J3J1 Fmax=48 最优解零件机床及工时J1J2J3J4GtiG1891118HtiH7111013制造业中的排序问题(ScheduleProbleminManufacturing)(四)n种工件在m台机床上加工的流水型排序问题及解法(SchedulingnJobsonmMachines)1、约翰逊规章的扩展法组合原则为：tiA= (h=1,2,……,m－1)tiB=,m－k+1共组合m－1次，每一次组合对应一个挨次，从m－1种挨次的加工周期中挑最小的。å=h1kiktå=h1kit制造业中的排序问题(ScheduleProbleminManufacturing)2、关键零件法(KeyPartsModel)把总工时〔〕最大的零件作为关键零件，记为Jc,假设Max()=,则k零件为Jc1)除Jc外，凡ti1＜tim的零件，按ti1从小到大排在Jc前;2)除Jc外，凡满足ti1＞tim的零件，按tim从大到小排在Jc后。3)假设ti1=tim，相应零件既可排在Jc前，又可排在Jc后,得到多个方案，从中选最优。å=m1jijtå=m1jkjtå=m1jijt制造业中的排序问题(ScheduleProbleminManufacturing)

零件机床工时J1J2J3J4J5J6M1ti15541210M2ti25553610M3ti3833474M4ti4282156M5ti55212810å=51jijt252315112840制造业中的排序问题(ScheduleProbleminManufacturing)用表格法计算总流程右上角零件等待左下角机床空闲

零件机床J4J5J1J6J2J3M1138182327M241015283338M381725323641M492227384648M5113035485051125622222281153335331制造业中的排序问题(ScheduleProbleminManufacturing)以上规章也有一些局限性1)生产系统(ProductionSystem)是动态的，规章不行能考虑到各种变化2)规章看不到上游或下游的状况〔设备的忙闲等〕3)看不到其他很多重要因素如延期交货(DelayedDelivery)所造成的损失因此可依据规章无法考虑的因素作调整，用专家系统(ExpertSystem)或有交互功能的排序软件制造业中的排序问题(ScheduleProbleminManufacturing)效劳业中的排序问题(ScheduleProbleminServiceIndustry)医院病人等待问题人流、信息流分离与否可否挑选医生价值观顾客生产者长远市场

排序的对象是人而不是物；系统动态与随机性特点比制造业更突出；排序问题与排队模型结合在一起而产生作用例：(一)划分需求，进展排序需求的分类随机打算〔通过排序，平衡负荷(LoadBalance)〕 航空公司将乘客划分为工作日商务乘客和周未旅游乘客。美国某医院对需求分析显示：非预约病人周一看病人数最多，而其他时间来的相对较少。非预约——随机预约——可控——安排在每周后几天，使负荷稳定，削减等待时间。效劳业中的排序问题(ScheduleProbleminServiceIndustry)(二)排队治理(WaitingLineManagement)1、排队系统的根本特征需求群体排队结构服务结构不再有服务需求与需求的时间分布空间分布有关到达过程退出排队规则服务离开效劳业中的排序问题(ScheduleProbleminServiceIndustry)2、需求群体不同群体需求不同，每一类需求的预期等待时间(ExpectedWaitingTime)不同3、排队构造1)多条排队(Multi-Line)2)单一排队(Single-Line)3)领号效劳业中的排序问题(ScheduleProbleminServiceIndustry)需求群体同质群体亚群体有限的无限的有限的无限的效劳业中的排序问题(ScheduleProbleminServiceIndustry)有限排队(WaitingLinewithLimitedCapacity)假设等待场所无法容纳全部需求效劳的顾客，一些人会离去，这种状况称为有限排队效劳业中的排序问题(ScheduleProbleminServiceIndustry)2、需求群体不同群体需求不同，每一类需求的预期等待时间(ExpectedWaitingTime)不同3、排队构造1)多条排队(Multi-Line)2)单一排队(Single-Line)3)领号效劳业中的排序问题(ScheduleProbleminServiceIndustry)排队结构领号单一排队多条排队有限的无限的有限或无限允许/不允许移动快速通道效劳业中的排序问题(ScheduleProbleminServiceIndustry)优点多条排队a)供给差异效劳(DifferentiateService)〔超市快速结帐〕b)顾客可选择c)有助于削减不参加队伍的现象效劳业中的排序问题(ScheduleProbleminServiceIndustry)单一排队a)先到先效劳(FCFS,FirstComeFirstServe)b)顾客不会看到别的队伍移动得快而焦急c)插队困难d)提高了效劳的私密性〔一米线〕效劳业中的排序问题(ScheduleProbleminServiceIndustry)领号a)顾客可四处走动，但必需警觉是否叫到号。b)商店可利用“领号”系统增加顾客冲动购物，扫瞄、多买效劳业中的排序问题(ScheduleProbleminServiceIndustry)效劳业中的排序问题(ScheduleProbleminServiceIndustry)4、效劳构造单队单服务台单阶段的服务排队系统多队多服务台单阶段的服务排队系统单队多服务台单阶段的服务排队系统单队单服务台多阶段的服务排队系统单队多服务台多阶段的服务排队系统单队单效劳台单阶段的效劳排队系统多队多效劳台单阶段的效劳排队系统单队多效劳台单阶段的效劳排队系统单队单效劳台多阶段的效劳排队系统单队多效劳台多阶段的效劳排队系统5、排队规章1)FCFS(FirstComeFirstServe)常用到SPT规章，但效劳时间长的不断让位于后到达者，所以先用SPT分类，然后FCFS〔超市，快速通道〕2)最高优先权法则(HighestPriorityPrinciple)火警、抢救车为削减等待顾客离队可能，应让顾客知道预期等待时间的信息，并使顾客得到定期更新的信息。效劳业中的排序问题(ScheduleProbleminServiceIndustry)6、调整顾客到达率的措施1〕利用预约系统掌握顾客到达时间实现最高程度的效劳力量利用率削减顾客等待的时间提高效劳水平2〕承受预订系统对特定期间的效劳需求做出较准确的估量3〕承受差异定价措施效劳业中的排序问题(ScheduleProbleminServiceIndustry)7、调整效劳力量的策略1〕进展有效的人员班次排序2〕利用临时工或兼职人员3〕聘请和培育多技能的员工4〕对组织构造、体制与效劳流程进展重组〔重复工作如多封同一信件广告或流程重叠空档造成力量铺张〕〔“医患关系紧急的责任”的辩论：仁济医院院长，律师〕效劳业中的排序问题(ScheduleProbleminServiceIndustry)排队理论是二十世纪初在争论系统时提出的方法排队是指顾客或工件排队等待效劳或加工随机到达我们假设，在某段时间内顾客到达是随机的，互不相关，但平均到达率不变。顾客到达有很多来源每个来源到达率很低顾客到达互不相关例如，假定平均到达率是每小时16位顾客。但每个小时的实际到达人数是不一样的。为什么会消失排队现象？假定每小时平均有4位顾客到达，效劳人员为每位顾客的平均效劳时间为15分钟。假设顾客到达的间隔时间正好是15分钟，而效劳人员为每位顾客的效劳时间也正好是15分钟，那么，就只需要一名效劳人员，顾客也根本用不着等待。在以下状况将消失排队现象：平均到达率〔顾客/小时〕高于平均效劳率〔顾客/小时〕，就像红酸果案例中的状况一样。顾客到达的间隔时间不一样〔随机〕。效劳时间不一样〔随机〕。顾客到达效劳设施顾客排队顾客离开衡量效劳系统表现的尺度输出率=单位时间内系统所效劳的平均顾客数。r=利用率=效劳时间所占的比例L=系统中的平均顾客数(包括正被效劳的)W=每位顾客在系统中平均逗留时间，即流程时间(包括承受效劳时间)Lq=在队列中等待的平均顾客数Wq=每位顾客的平均等待时间，即排队时间影响等待时间的因素顾客：以泊松分布方式到达l=平均到达率(单位时间到达的顾客数〕效劳时间：M=平均效劳时间s=效劳时间的方差效劳率〔人/小时〕：效劳台数：czz排队理论是设计和改进生产系统的重要工具排队理论的主要目标是：由系统的参数〔顾客到达率、效劳时间、效劳台数等等〕动身，估量系统的表现，特殊是在时间方面的表现。主要方法：公式近似公式电脑模拟效劳台利用率就是每个效劳台实际工作时间所占比例。效劳台利用率=

效劳台利用率是衡量表现的重要指标实例：平均到达率为每小时10位顾客；每位顾客平均要求10分钟的效劳〔效劳时间〕，这样在一个小时内，平均就有100分钟或者说1.667个小时的工作量；共有两个效劳台，每个可利用的时间为一个小时，这样总计可利用时间为两个小时。因此效劳台利用率为1.667/2=83.3%.

另一种计算效劳台利用率的方法效劳台利用率=实例：平均到达率为每小时10位顾客；每个效劳台的平均效劳时间为10分钟，这样一个效劳台平均一小时可以为6位顾客供给效劳；共有两个效劳台；因此效劳台利用率为10/(2*6)=0.833或者说83.3%

三种重要的关系“管道原理”:在一个稳定系统中

平均输出=平均输入，或者输出率=l利特尔法则：时间的可加性：在系统中逗留的时间等于效劳时间加排队时间：利特尔法则依据利特尔法则：

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

平均逗留时间单个效劳台;任意效劳时间分布一个稳定系统的条件：利用率小于1：计算公式：s数值增大就意味着效劳时间有更多的可变性。而更多的可变性则会造成更多的拥塞和延误，这样就要等待更长的时间。实例以下是两个计算机系统的有关数据：顾客的到达率为每小时15位。也就是说l=15/60=0.25位顾客/分钟(留意:使用一样的时间单位！)1号系统2号系统M(分钟)3.03.1s(分钟)2.11.0实例〔续〕1号计算机系统：2号计算机系统：慢的反而好！实例〔续〕单个效劳台；效劳时间为指数分布效劳时间为指数分布，那么，M=s=1/m利用率：计算公式：假设把到达数量增加一倍(2l)，再把效劳率增加一倍(2m),等待时间就会削减一半。这就是排队论的规模经济学。平均队长与利用率的关系平均队长〔和平均等待时间〕与效劳台利用率之间的关系不是线性的关系。资产利用率太高会造成效劳质量急速下降，因而要权衡利弊。要保证效劳质量，就必需保持“过剩的”生产或效劳力量。平均队长利用率实例一个效劳台：指数效劳时间到达率=10/小时利用率平均排队长度平均等待时间0.20.050.005小时(0.3分钟)0.50.500.05小时(3.0分钟)0.83.200.32小时

(19.2分钟)0.98.100.81小时(48.6分钟)0.9518.05