作业排序问题课件.ppt

《作业排序问题课件.ppt》由会员分享，可在线阅读，更多相关《作业排序问题课件.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、生产运作管理第第6 6章章 作业排序作业排序CWU-HRM人力系人力系什么时候需什么时候需要排队？要排队？为什么会出现排队现象？v假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间为15分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为每位顾客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。v在以下情况将出现排队现象：p平均到达率（顾客/小时）高于平均服务率（顾客/小时）p顾客到达的间隔时间不一样（随机）p服务时间不一样（随机）顾客顾客到达到达 服务设施服务设施顾客顾客排队排队顾客顾客离开离开你觉得应以怎样的准则排队？你觉得应以怎样的准则排队？v

2、超市收银v病人看病v银行办业务v一个排序的例子一个排序的例子四种型号的电视机的装配工时定额四种型号的电视机的装配工时定额型号型号型号型号部装定额工时部装定额工时部装定额工时部装定额工时（小时）（小时）（小时）（小时）总装定额工时总装定额工时总装定额工时总装定额工时（小时）（小时）（小时）（小时）A A A AB B B BC C C CD D D D151515158 8 8 86 6 6 6121212124 4 4 4101010105 5 5 57 7 7 7部部装装B（8）C(6)D（12）总总装装A(4)B（10）C(5)D(7)（a a）装配顺序为装配顺序为A AB BC CD D

3、，总装配时间为总装配时间为4848小时小时部部装装C（6）B（8）总总装装C(5)B（10）D（7）（b b）装配顺序为装配顺序为C CB BD DA A，总装配时间为总装配时间为4545小时小时部部装装C（6）B（8）总总装装D（7）C(5)B(10)（c c）装配顺序为装配顺序为D DC CA AB B，总装配时间为总装配时间为5151小时小时A（15）A（15）A（15）A(4)A(4)D（12）D(12)一个排序的例子一个排序的例子6.1 6.1 作业排序的基本概念作业排序的基本概念 一、作业排序的定义 生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后

4、次序。二、目的三、一般假设CWU-HRM人力系人力系1.满足交货期要求 2.缩短生产周期3.使在制品库存最小4.使平均流程时间最小 5.提高机器/工人的时间利用率 6.使生产和人工成本最低作业排序的目的作业排序的目的 三、排序问题的一般假设三、排序问题的一般假设p一个工件不能同时在几台设备上加工p工件数、机器数和加工时间是已知的，且加工时间与加工顺序无关p每台设备同一时间只能加工一个工件（不考虑多工位组合机床）p工件的工艺过程都是确定的，一种工件不能同时有多种加工工艺p每台设备只能胜任一道工序，不能适应多种工序的加工（设备与工序是一对一的对应关系，不考虑一对多的关系）p一个工件加工开始后，不允

5、许中断中途插入其他工件，必须把该工件加工完成后才可以安排其他工件的加工四、排序方法四、排序方法v排序规则pFCFS（First Come First Served）pEDD(Earliest Due Date)pSPT(Shortest Processing Time)pSCR(Smallest Critical Ratio)p最小松动时间优先规则（交货期-加工时间，STR）pMWKR(Most Work Remaining)pLWKR(Least Work Remaining)pMOPNR(Most Operations Remaining)pRANDOMCWU-HRM人力系人力系临界比：工

6、件剩余的交货时间和工件余下加工时间之比6.2 6.2 制造业作业排序制造业作业排序1.单台设备上的作业排序 一台设备面对多个工件需要加工 顺序的变化产生什么影响？案例CWU-HRM人力系人力系J1 J2 J3 Jn 机器到达系统工件的集合离开系统（机器）例例v有6个工件需要在某台设备上加工，各工件的加工时间如表所示（工件编号是工件达到工作地的先后次序，当前日期为1）。采用不同的排序规则进行排序。CWU-HRM人力系人力系工件编号工件编号1 12 23 34 45 56 6加工时间7810256交货期141220101518按照按照FCFSFCFS作业排序作业排序1 12 23 34 45 56

7、 6工件编号1 12 23 34 45 56 6加工时间7810256等待时间0715252732完成时间71525273238交货期141220101518拖延时间035171720CWU-HRM人力系人力系按照按照SPTSPTCWU-HRM人力系人力系作业排序作业排序1 12 23 34 45 56 6工件编号4 45 56 61 12 23 3加工时间2567810等待时间027132028完成时间2713202838交货期101518141220拖延时间00061618按照按照EDDEDDCWU-HRM人力系人力系作业排序作业排序1 12 23 34 45 56 6工件编号4 42 2

8、1 15 56 63 3加工时间2875610等待时间0210172228完成时间21017222838交货期101214151820拖延时间00371018按照按照STRSTRCWU-HRM人力系人力系作业排序作业排序1 12 23 34 45 56 6工件编号2 21 14 43 35 56 6松动时间478101012加工时间8721056等待时间0815172732完成时间81517273238交货期121410201518拖延时间01771720按照按照SCRSCRCWU-HRM人力系人力系作业排序作业排序1 12 23 34 45 56 6工件编号2 21 13 35 56 64

9、4临界比率1.3751.861.92.82.834.5加工时间8710564等待时间0815253036完成时间81525303638交货期121420151810拖延时间012151828各排序规则的结果比较各排序规则的结果比较CWU-HRM人力系人力系排序方法排序方法总延期工件数总延期工件数平均拖延时间平均拖延时间平均流程时间平均流程时间先来先加工510.3324最短加工时间36.6718最短交货期46.3319.5最小松动时间58.6722.83临界比率最小511.1725.33对于单台设备作业排序问题对于单台设备作业排序问题v按照最短加工时间优先规则安排作业，可使工作的平均完成时间最短

10、，在制品最少；v按照最短交货期优先规则安排作业，可使最长拖期时间与平均拖期时间最小化。CWU-HRM人力系人力系2.流水线的作业排序 问题描述P207CWU-HRM人力系人力系v多工件两台设备的排序问题算法pJohnson算法 1954年p最小加工时间出现在第一台设备，则尽量往前排p最小加工时间出现在第二台设备，则尽量往后排CWU-HRM人力系人力系ii1 12 23 34 45 56 6M18471310M2326925v多工件多设备的排序问题启发算法p关键工件法p1983年提出1.计算每个工件的总加工时间Pi，找出加工时间最长的工件C为关键工件2.余下的工件，如果 则按照 不减的顺序排成序

11、列S1，如果 则按照 不增的顺序排成序列S2，3.序列（S1，C，S2，）为所求排序CWU-HRM人力系人力系例例I I1 12 23 34 4Pi11263Pi28429Pi34582Pi13111614CWU-HRM人力系人力系P218P218工件工件1 12 23 34 45 56 6设备1 37842624395513221093845137935767846CWU-HRM人力系人力系6.36.3 服务业作业排序服务业作业排序u 排序的对象是人而不是物；系统动态与随机性特点比制造业更突出；排序问题与排队模型结合在一起而产生作用CWU-HRM人力系人力系v需求的分类 随机 计划（通过排序

12、，平衡负荷(Load Balance)）v美国某医院对需求分析显示：非预约病人周一看病人数最多，而其他时间来的相对较少。非预约随机 预约可控安排在每周后几天，使负荷稳定，减少等待时间。1 划分需求，进行排序2 排队管理(Waiting Line Management)(1)排队系统的基本特征需求群体需求群体排队结构排队结构服务结构服务结构不再有服不再有服务需求务需求与需求的时间分与需求的时间分布空间分布有关布空间分布有关到达过程到达过程退出退出排队规则排队规则服务服务离开离开(2)需求群体 不同群体需求不同，每一类需求的预期等待时间(Expected Waiting Time)不同(3)排队结

13、构 多条排队(Multi-Line)单一排队(Single-Line)领号2 排队管理(Waiting Line Management)2 排队管理(Waiting Line Management)v有限排队(Waiting Line with Limited Capacity)p若等待场所无法容纳所有需求服务的顾客，一些人会离去，这种情况称为有限排队(2)需求群体 不同群体需求不同，每一类需求的预期等待时间(Expected Waiting Time)不同(3)排队结构 多条排队(Multi-Line)单一排队(Single-Line)领号2 排队管理(Waiting Line Manage

14、ment)排队结构排队结构排队结构排队结构领领领领号号号号单一排队单一排队单一排队单一排队多条排队多条排队多条排队多条排队有限的有限的有限的有限的无限的无限的无限的无限的有限或无限有限或无限有限或无限有限或无限允许允许允许允许/不允许不允许不允许不允许移动移动移动移动快速通道快速通道快速通道快速通道优点v多条排队a)提供差别服务（超市快速结帐）b)顾客可选择c)有助于减少不加入队伍的现象v单一排队a)先到先服务(FCFS,First Come First Served)b)顾客不会看到别的队伍移动得快而着急c)提高了服务的私密性（一米线）v领号a)顾客可四处走动，但必须警觉是否叫到号。b)商店

15、可利用“领号”系统增加顾客冲动购物，浏览、多买1.1.单队单服务台单阶段的服务排队系统单队单服务台单阶段的服务排队系统2.2.多队多服务台单阶段的服务排队系统多队多服务台单阶段的服务排队系统3.3.单队多服务台单阶段的服务排队系统单队多服务台单阶段的服务排队系统4.4.单队单服务台多阶段的服务排队系统单队单服务台多阶段的服务排队系统5.5.单队多服务台多阶段的服务排队系统单队多服务台多阶段的服务排队系统3 3 服务结构服务结构单队单服务台单阶段的服务排队系统多队多服务台单阶段的服务排队系统单队多服务台单阶段的服务排队系统单队单服务台多阶段的服务排队系统单队多服务台多阶段的服务排队系统5 5、排

16、队规则、排队规则1)FCFS(First Come First Served)v常用到SPT规则，但服务时间长的不断让位于后到达者，所以先用SPT分类，然后FCFS（超市，快速通道）2)最高优先权法则(Highest Priority Principle)v火警、救护车举例：为减少等待顾客离队可能，应让顾客知道预期等待时间的信息，并使顾客得到定期更新的信息。1）利用预约系统 控制顾客到达时间 实现最高程度的服务能力利用率 减少顾客等待的时间 提高服务水平2）采用预订系统 对特定期间的服务需求做出较准确的估计3）采用差异定价措施4 调整顾客到达率的措施1）进行有效的人员班次排序2）利用临时工或兼

17、职人员3）招聘和培养多技能的员工5 调整服务能力的策略为何“集中使用”可以提高服务质量？v独立的系统在此等待在此等待在此等待在此等待l“集中使用”系统减少等待时间的办法v减少平均服务时间v减少服务时间的可变性v增加服务人员v减少平均到达人数v通过顾客预约等办法来减少到达的可变性v集中使用服务资源v更好地计划和调度掌握客户的感受:等待心理学 客户所感受到的等待可能与实际的等待有很大的差别。研究结果表明：v服务越有价值，人们就越愿意多等一会儿。v服务开始之前的等待感觉要比服务过程中的等待要长。v心急会让人觉得等待的时间很长。v不公平的等待比公平的等待要长。v不确定的等待比已知的等待要长。v不明情况的等待要比知情的等待要长。v没事干的时候会让人觉得比有事干的时候要长。v独自等待会让人觉得比大家一起等待要长。CWU-HRM