作业排序问题课件

生产运作管理第6章作业排序CWU-HRM人力系什么时候需要排队？为什么会出现排队现象？假定每小时平均有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)一个排序的例子6.1作业排序的基本概念

一、作业排序的定义生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。二、目的三、一般假设CWU-HRM人力系满足交货期要求

缩短生产周期使在制品库存最小

使平均流程时间最小

提高机器/工人的时间利用率

使生产和人工成本最低作业排序的目的

三、排序问题的一般假设一个工件不能同时在几台设备上加工工件数、机器数和加工时间是已知的，且加工时间与加工顺序无关每台设备同一时间只能加工一个工件（不考虑多工位组合机床）工件的工艺过程都是确定的，一种工件不能同时有多种加工工艺每台设备只能胜任一道工序，不能适应多种工序的加工（设备与工序是一对一的对应关系，不考虑一对多的关系）一个工件加工开始后，不允许中断中途插入其他工件，必须把该工件加工完成后才可以安排其他工件的加工四、排序方法排序规则FCFS（FirstComeFirstServed）EDD(EarliestDueDate)SPT(ShortestProcessingTime)SCR(SmallestCriticalRatio)最小松动时间优先规则（交货期-加工时间，STR）MWKR(MostWorkRemaining)LWKR(LeastWorkRemaining)MOPNR(MostOperationsRemaining)RANDOMCWU-HRM人力系临界比：工件剩余的交货时间和工件余下加工时间之比6.2制造业作业排序单台设备上的作业排序

一台设备面对多个工件需要加工

顺序的变化产生什么影响？

案例CWU-HRM人力系J1J2J3Jn

机器到达系统工件的集合离开系统（机器）例有6个工件需要在某台设备上加工，各工件的加工时间如表所示（工件编号是工件达到工作地的先后次序，当前日期为1）。采用不同的排序规则进行排序。CWU-HRM人力系工件编号123456加工时间7810256交货期141220101518按照FCFS作业排序123456工件编号123456加工时间7810256等待时间0715252732完成时间71525273238交货期141220101518拖延时间035171720CWU-HRM人力系按照SPTCWU-HRM人力系作业排序123456工件编号456123加工时间2567810等待时间027132028完成时间2713202838交货期101518141220拖延时间00061618按照EDDCWU-HRM人力系作业排序123456工件编号421563加工时间2875610等待时间0210172228完成时间21017222838交货期101214151820拖延时间00371018按照STRCWU-HRM人力系作业排序123456工件编号214356松动时间478101012加工时间8721056等待时间0815172732完成时间81517273238交货期121410201518拖延时间01771720按照SCRCWU-HRM人力系作业排序123456工件编号213564临界比率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对于单台设备作业排序问题按照最短加工时间优先规则安排作业，可使工作的平均完成时间最短，在制品最少；按照最短交货期优先规则安排作业，可使最长拖期时间与平均拖期时间最小化。CWU-HRM人力系流水线的作业排序

问题描述P207CWU-HRM人力系多工件两台设备的排序问题算法Johnson算法1954年最小加工时间出现在第一台设备，则尽量往前排最小加工时间出现在第二台设备，则尽量往后排CWU-HRM人力系i123456M18471310M2326925多工件多设备的排序问题启发算法关键工件法1983年提出计算每个工件的总加工时间Pi，找出加工时间最长的工件C为关键工件余下的工件，如果则按照不减的顺序排成序列S1，如果则按照不增的顺序排成序列S2，序列（S1，C，S2，）为所求排序CWU-HRM人力系例I1234Pi11263Pi28429Pi34582Pi13111614CWU-HRM人力系P218工件123456设备137842624395513221093845137935767846CWU-HRM人力系6.3服务业作业排序

排序的对象是人而不是物；系统动态与随机性特点比制造业更突出；排序问题与排队模型结合在一起而产生作用CWU-HRM人力系需求的分类随机计划（通过排序，平衡负荷(LoadBalance)）

美国某医院对需求分析显示：非预约病人周一看病人数最多，而其他时间来的相对较少。非预约——随机预约——可控——安排在每周后几天，使负荷稳定，减少等待时间。1划分需求，进行排序2排队管理(WaitingLineManagement)(1)排队系统的基本特征需求群体排队结构服务结构不再有服务需求与需求的时间分布空间分布有关到达过程退出排队规则服务离开(2)需求群体不同群体需求不同，每一类需求的预期等待时间(ExpectedWaitingTime)不同(3)排队结构多条排队(Multi-Line)单一排队(Single-Line)领号2排队管理(WaitingLineManagement)2排队管理(WaitingLineManagement)有限排队(WaitingLinewithLimitedCapacity)若等待场所无法容纳所有需求服务的顾客，一些人会离去，这种情况称为有限排队(2)需求群体不同群体需求不同，每一类需求的预期等待时间(ExpectedWaitingTime)不同(3)排队结构

多条排队(Multi-Line)

单一排队(Single-Line)领号2排队管理(WaitingLineManagement)排队结构领号单一排队多条排队有限的无限的有限或无限允许/不允许移动快速通道优点多条排队a)提供差别服务（超市快速结帐）b)顾客可选择c)有助于减少不加入队伍的现象单一排队a)先到先服务(FCFS,FirstComeFirstServed)b)顾客不会看到别的队伍移动得快而着急c)提高了服务的私密性（一米线）领号a)顾客可四处走动，但必须警觉是否叫到号。b)商店可利用“领号”系统增加顾客冲动购物，浏览、多买单队单服务台单阶段的服务排队系统多队多服务台单阶段的服务排队系统单队多服务台单阶段的服务排队系统单队单服务台多阶段的服务排队系统单队多服务台多阶段的服务排队系统3服务结构单队单服务台单阶段的服务排队系统多队多服务台单阶段的服务排队系统单队多服务台单阶段的服务排队系统单队单服务台多阶段的服务排队系统单队多服务台多阶段的服务排队系统5、排队规则FCFS(FirstComeFirstServed)常用到SPT规则，但服务时间长的不断让位于后到达者，所以先用SPT分类，然后FCFS（超市，快速通道）2)最高优先权法则(HighestPriorityPrinciple)火警、救护车举例：为减少等待顾客离队可能，应让顾客知道预期等待时间的信息，并使顾客得到定期更新的信息。1）利用预约系统

控制顾客到达时间实现最高程度的服务能力利用率减少顾客等待的时间提高服务水平2）采用预订系统

对特定期间的服务需求做出较准确的估计3）采用差异定价措施4调整顾客到达率的措施1）进行有效的人员班次排序2）利用临时工或兼职人员3）招聘和培养多技能的员工5调整服务能力的策略为何“集中使用”可以提高服务质量？独立的系统在此等待在此等待“集中使用”系统减少等待时间的办法减少平均服务时间减少服务时间的可变性增加服务人员减少平均到达人数通