《生产与运作管理》八作业排序解析课件.ppt

1,生产与运作管理,浙江财经学院工商管理学院,浙江财经学院工商管理学院 2,生产运作管理模型,输入待转化资源物料信息顾客,输入转化资源设施 员工,顾客,输入资源,输出产品与服务,改善,计划与控制,设计,运作战略,企业战略,作业排序,浙江财经学院工商管理学院 3,本章主要内容,作业排序的基本概念作业排序的表示方式流水作业排序问题单件作业排序问题服务排队系统设计中的心理因素,浙江财经学院工商管理学院 4,医院门诊病人治疗手术室大学排课教室工厂生产采购,作业排序例子,浙江财经学院工商管理学院 5,作业计划与排序,作业排序(Sequencing)是确定加工对象的加工顺序作业计划(Scheduling)还要确定开始加工和完工的时间作业排序是作业计划的关键在实际中，这两个词经常被等同使用,浙江财经学院工商管理学院 6,作业排序的战略目的,有效的排序可以提高设施的利用率，这意味着：有效的排序可以提高交货速度，这意味着：好的排序提供,更低的成本,更好的顾客服务,更可靠的交货,浙江财经学院工商管理学院 7,前向排序与后向排序,收到订单,交货期,前向排序,后向排序,请思考下列两种情况下适用哪种排序方式？按订单生产的企业为节省库存的费用,浙江财经学院工商管理学院 8,甘特图（ Gantt Chart）,作业进度图表示一项工作的计划开始日期、计划完成日期以及现在的进度 机器图（甘特负荷图）描述不同工作在每一台机器上的工作次序，可被用来管理生产进度,浙江财经学院工商管理学院 9,作业进度甘特图,开始时间,结束时间,计划所用时间,实际进度,表示一项工作的计划开始日期、计划完成日期以及现在的进度,浙江财经学院工商管理学院 10,描述不同工作在每一台机器上的工作次序,机器甘特图,开始时间,结束时间,计划所用时间,实际进度,非生产性时间,A,B,C,A,B,C,浙江财经学院工商管理学院 11,排序问题的分类,主要是将不同工件安排到不同设备上，或安排不同的人做不同的工作,劳动力作业排序,生产作业排序,主要是确定人员何时工作,两种基本形式的作业排序,浙江财经学院工商管理学院 12,制造业生产作业排序分类,按机器数量分类,单台机器的排序问题,多台机器的排序问题,单件作业排序问题(Job-Shop),流水作业排序问题(Flow-Shop),按工件到达车间的情况不同,静态排序问题,动态排序问题,工件陆续到达，要随时安排它们的加工顺序,排序时，所有工件都已到达，可一次性进行排序,浙江财经学院工商管理学院 13,n个作业的单台机器排序问题(n/1),对于某一工作地，在给定的一段时间内，顺次决定下一个被加工的工件可能要考虑交付日期、在制品数量、全部完工时间等因素,对象1,对象2,对象3,对象n,工作地,浙江财经学院工商管理学院 14,常用的优先顺序规则,先到先服务优先选择完工期限最紧的工件优先选择加工时间最短的工件优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比优先选择余下加工时间最长的工件优先选择余下加工时间最短的工件优先选择余下工序数最多的工件随机地挑选下一个工件,FCFS (First Come First Served)规则EDD (Earliest Due Date)规则SPT (Shortest Processing Time)规则SCR (Smallest Critical Ratio)规则MWKR (Most Work Remaining)规则LWRK (Least work Remaining)规则MOPNR (Most Operations Remaining)规则 RANDOM规则,规则,解释,浙江财经学院工商管理学院 15,最先到的工作先处理大多数作业排序标准能达到平均水平对顾客来说是公平的对服务组织更重要如: 餐厅,先到先服务FCFS, (First Come, First Served Rule),浙江财经学院工商管理学院 16,优先处理完工时间最早的工作被一些企业广泛的应用如果完工时间很重要MRP系统完工时间使最大延迟最小，提高客户满意水平在许多排程标准上表现并不是太好,最早交货时间EDD（Earliest Due Date Rule）,浙江财经学院工商管理学院 17,最短作业时间SPT（Shortest Processing Time Rule）,优先处理完工时间最短的工作可以使工作流最小化，或系统中要完成的工作数量最小化在单台机器或单个工作中心（n/1）情况下使用平均延迟、平均等待时间和平均完成时间上都能产生最优解。最大的缺陷是工作时间长的工作将被不断地推迟。,浙江财经学院工商管理学院 18,最小临界值(关键比率规划)SCR（Smallest Critical Ratio）,临界值：距离完工期剩余时间与剩余工作时间之比值,先处理临界值最小的工作可以缩短平均延迟时间，有效地跟踪记载工作进展和位置,CR,剩余时间,剩余工作时间,完工期,-,今日之日期,剩余工作时间,=,=,浙江财经学院工商管理学院 19,最长余下时间MWKR (Most Work Remaining),优先选择余下加工时间最长的工作,浙江财经学院工商管理学院 20,最短余下时间LWRK (Least work Remaining),优先选择余下工作时间最短的工作,浙江财经学院工商管理学院 21,最多余下作业MOPNR (Most Operations Remaining),优先选择余下处理工序最多的工作,浙江财经学院工商管理学院 22,随机规则（RANDOM）,随机挑选下一个工作,浙江财经学院工商管理学院 23,作业排序方案的评价指标,工件流程时间从工件可以开始加工(不一定是实际的开始时间)至完工的时间全部完工时间完成一组工作所需的全部时间 延迟可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间完工的工件数占总工件数的百分比来表示在制品库存(WIP)度量标准可以用工件个数、其货币价值或可供应的周数来表示总库存计划入库量和现有库存量的总和为总库存量利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示,浙江财经学院工商管理学院 24,作业排序方案的评价指标（续）,浙江财经学院工商管理学院 25,作业排序目标,满足交货日期提前期最短准备时间最短或者成本最小在制品库存最小机器或劳动力利用率最大这一条有争议，因为仅仅考虑保持机器或者劳动力处于繁忙状态可能不是在工序中进行管理的最有效的方法,浙江财经学院工商管理学院 26,n/1排序问题例,李生是A复印公司的主管，复印公司为其所在市区的某法律公司提供复印服务，在这周开始，5个客户提供了他们的订单。详细的排序数据如下：,所有的订单都要使用唯一的彩色复印机，李生必须决定5个订单的加工顺序，评价标准是流程时间最短。,浙江财经学院工商管理学院 27,FCFS,浙江财经学院工商管理学院 28,SPT,E,1,2,0+1=1,0,C,2,7,1+2=3,0,A,3,5,3+3=6,6-5=1,B,4,6,6+4=10,10-6=4,D,6,9,10+6=16,16-9=7,1+3+6+10+16=36(天),36/5=7.2(天),1+4+7=12 (天),12/5=2.4(天),浙江财经学院工商管理学院 29,EDD,E,1,2,0+1=1,0,A,3,5,1+3=4,0,B,4,6,4+4=8,8-6=2,C,2,7,8+2=10,10-7=3,D,6,9,10+6=16,16-9=7,1+4+8+10+16=39(天),39/5=7.8(天),2+3+7=12 (天),12/5=2.4(天),浙江财经学院工商管理学院 30,优先调度规则对比,从上面可看出，SPT规则比其他规则较好，事实上也是这样，用数学方法可以证明在n/1情况下使用其他衡量标准，如平均等待时间和平均完成时间，SPT都能产生最优解。这种简单的规则如此有用，以至于被称为“整个排序科学中最重要的概念”,浙江财经学院工商管理学院 31,对在制品库存的理解,n/1排序第一件工件开始生产前所有工件已经达到，处于等待状态,浙江财经学院工商管理学院 32,对总库存的理解,n/1排序第一件工件开始生产前所有工件已经达到，处于等待状态,浙江财经学院工商管理学院 33,优先规则及其事例（学生练习）,例：一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间分别使用SPT和EDD规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存,浙江财经学院工商管理学院 34,发动机机壳的加工与取货信息,一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间。,请给出分别使用SPT和EDD规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存,浙江财经学院工商管理学院 35,SPT规则排序结果,机壳4,机壳2,机壳1,机壳5,机壳3,浙江财经学院工商管理学院 36,SPT规则排序结果,浙江财经学院工商管理学院 37,EDD规则排序结果,机壳1,机壳2,机壳4,机壳3,机壳5,浙江财经学院工商管理学院 38,EDD规则排序结果,浙江财经学院工商管理学院 39,流水作业排序问题,流水作业排序问题的基本特征是每个工件的加工路线都一致讨论所有工件在各台机器上的加工顺序都相同的情况,浙江财经学院工商管理学院 40,最长流程时间,最长流程时间又称加工周期是第一个工件在一台机器开始加工时算起，到最后一个工件在最后一台机器上完工时为至所经过的时间假定所有工件到达时间为零，则最长流程时间=排在末位加工工件在车间的停留时间流水作业排序一个目标函数：最长流程时间最短,浙江财经学院工商管理学院 41,最长流程时间,设n个工件的加工顺序为S=(S1,S2,Sn),表示工件Si在机器Mk上的完工时间,表示工件Si在机器Mk上的加工时间,浙江财经学院工商管理学院 42,加工顺序矩阵,浙江财经学院工商管理学院 43,加工顺序矩阵图示解释,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46,机器1,机器2,机器3,机器4,时间,浙江财经学院工商管理学院 44,n个作业两台机器排序问题(n/2),两个或者更多以上的作业必须在两台机器上以共同的工序进行加工评价标准：从第一个作业开始到最后一个作业结束的总流程时间最短，即全部完工时间最短Johnson方法（约翰逊方法）,浙江财经学院工商管理学院 45,N项作业按相同顺序经过2台机器加工，使全部完工时间最小N项作业的双机排序（N/2）,锯,钻,工作 A,工作 B,工作 C,工作 (N = 3),Johnson方法（约翰逊方法）,浙江财经学院工商管理学院 46,Johnson方法 - N项作业的双机排序,(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕,浙江财经学院工商管理学院 47,列出作业及加工时间,全部安排完毕?,Yes,1,2,Yes,No,No,Johnson法的步骤,选择加工时间最短的作业,哪台机器？,先完成这一作业,最后完成这一作业,删除这一作业,还有剩余作业吗？,结束,强制结束,浙江财经学院工商管理学院 48,Johnson法 例子,(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕,浙江财经学院工商管理学院 49,Johnson法 例子,步骤 1,步骤 2,步骤 3,步骤 4,步骤 5,(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕,Y3,Y1,Y2,Y4,Y5,Y3,Y3,Y3,Y3,Y2,Y2,Y2,Y5,Y5,Y1,浙江财经学院工商管理学院 50,Johnson法例子的甘特图,Y2(4),Y1(12),Y4(15),Y5(10),Y3(5),空闲，等待新任务,Y2(5),Y1(22),Y4(16),Y5(8),Y3(3),空闲,空闲,Y4,Y3,Y2,Y5,Y1,浙江财经学院工商管理学院 51,提问,如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，应该如何排序？如果一项作业在两台机器上的作业时间相同，应该如何排序？,浙江财经学院工商管理学院 52,Johnson法的补充说明,如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，则第一台机器的这一作业安排在前面完成，而第二台机器的这项作业安排在后面完成如果一项作业在两台机器上的作业时间相同，这个项目可以被安排在两个作业时间的任一一个,浙江财经学院工商管理学院 53,Johnson法的优化（P303）,第一台机器上的加工时间记为ai，第二台机器上的加工时间bi将所有工件ai bi按ai值不减的顺序排成一个序列A将所有工件ai bi按bi值不增的顺序排成一个序列B将A放在B之前，就构成了最优加工顺序,浙江财经学院工商管理学院 54,Johnson法的优化,ai bi按ai值不减的序列A：(4,12,15) ,(Y2,Y1,Y4),4,12,15,3,8,Y4,Y3,Y2,Y5,Y1,ai bi按bi值不增的序列B：(8,3),(Y5,Y3),浙江财经学院工商管理学院 55,n个作业n台机器排序问题(n/n),当作业数和机器数相同时，能够同时开始所有作业作业排序问题不是哪个作业先开始，而是哪个作业指派到哪台机器上的安排使得总排序最佳,浙江财经学院工商管理学院 56,n/n作业问题的分配方法Assignment Method,分配方法是一种特殊的可将任务或工作分配给相应的资源的线性规划模型，是线性规划运输问题的一个特例。适用于有n个需求和n个供给的情况,成本或时间达到最少,目标,特征,一件工作(或一个人)仅分配给一台机器(或一个项目),浙江财经学院工商管理学院 57,n/n作业问题的分配方法,每个分配问题用一张表，表中数字是与特定的分配相关的成本或时间。通过在增加或减少一适当的数字以找到各种分配的最小机会成本。,浙江财经学院工商管理学院 58,分配方法的步骤,1.将每行数字减去该行中最小数字，将每列减去该列中最小数字。,2.画数量最小的水平线和垂直线以盖住表中的所有的零。若直线数等于表的行或列数，那么我们就找到了最优分配(见步骤4)；否则进入步骤3。,3.从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上。再回到步骤2往下操作直到出现可能的最佳分配。,4.最佳分配总在表中零位置出现。,浙江财经学院工商管理学院 59,分配方法示例,将工作分配到机器上去,浙江财经学院工商管理学院 60,分配方法示例,步骤1a：从各行数字中减去其中数字最小的数字,6,5,8,0,0,2,3,2,5,0,8,7,浙江财经学院工商管理学院 61,分配方法示例,步骤1b：从各列数字中减去其中数字最小的数字,0,5,0,2,2,6,0,3,0,3,0,0,浙江财经学院工商管理学院 62,分配方法示例,步骤2：画最小数目的直线盖住所有的0,直线数=2行(列)数3，故非最优答案,浙江财经学院工商管理学院 63,分配方法示例,步骤3：从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上,3,4,0,1,5,回到步骤2，画线盖0,由于直线数=3=行(列)数，故为最优答案,浙江财经学院工商管理学院 64,分配方法示例,最佳分配总是在表中零位置出现将R-34分配给C，S-66分配给B T-50分配给A最小成本=6+10+9=25元,问题：S-66能否分配给A？,浙江财经学院工商管理学院 65,n/m作业排序问题,本课程不讲，有兴趣的同学自己看书,浙江财经学院工商管理学院 66,相同零件、不同移动方式下的加工周期,n个零件相同，在加工过程中采取不同的移动方式，会导致一批零件的加工周期不同有三种典型的移动方式顺序移动方式平行移动方式平行顺序移动方式,浙江财经学院工商管理学院 67,不同移动方式下加工周期的计算,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 68,不同移动方式下加工周期的计算,平行移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 69,不同移动方式下加工周期的计算,平行顺序移动,M1,M2,M3,M4,T平顺,特点：,浙江财经学院工商管理学院 70,平行顺序移动加工周期的推演0,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 71,平行顺序移动加工周期的推演1,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 72,平行顺序移动加工周期的推演2,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 73,平行顺序移动加工周期的推演3,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 74,平行顺序移动加工周期的推演4,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 75,平行顺序移动加工周期的推演5,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 76,平行顺序移动加工周期的推演6,顺序移动,M1,M2,M3,M4,T顺,特点：,浙江财经学院工商管理学院 77,服务的作业排序规则,预约系统 美容服务预订系统 饭店先到先服务 熟食店、食堂紧急优先 医院急救,浙江财经学院工商管理学院 78,服务系统的作业排序特点,客户的参与服务无法储存,浙江财经学院工商管理学院 79,排队系统,排队管理的权衡,等待时间,长,短,成本,服务成本,等待成本,总成本,浙江财经学院工商管理学院 80,等待时间,感知等待时间实际等待时间,感知等待时间,顾客满意度,怎么还不来车,一会儿就轮到我了,浙江财经学院工商管理学院 81,影响顾客满意度,不公平的等待和公平的等待食堂中插队不舒适的等待和舒适的等待站着与坐者等待没有解释的等待和解释的等待过程前的等待和过程中的等待麦当劳：排队点菜与等待食物忙碌中等待与空闲中等待看报纸、听音乐焦急等待与耐心等待手术室外面,浙江财经学院工商管理学院 82,影响顾客满意度,独立等待和群体等待高价值服务等待和低价值服务等待时间对于顾客的重要程度进入服务系统前顾客的心态,浙江财经学院工商管理学院 83,投入-产出控制（Input/Output control，I/O）,在制品,投入控制,产出控制,浙江财经学院工商管理学院 84,无限生产排成,浙江财经学院工商管理学院 85,有限生产排成,浙江财经学院工商管理学院 86,高级生产排程（Advanced Production Schedule，APS）,浙江财经学院工商管理学院 87,应对瓶颈工序的策略,