《生产与运作管理》第八章：作业排序解析.ppt

《《生产与运作管理》第八章：作业排序解析.ppt》由会员分享，可在线阅读，更多相关《《生产与运作管理》第八章：作业排序解析.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 2生产运作管理模型生产运作管理模型输入待转化资源输入待转化资源物料物料信息信息顾客顾客输入转化资源输入转化资源设施设施 员工员工顾客顾客输入资源输入资源输出输出产品与服务产品与服务改善改善计划与计划与控制控制设计设计运作战略运作战略企业战略企业战略作业排序作业排序Production & Operations ManagementProduction & Operations Management浙江财经学院工

2、商管理学院浙江财经学院工商管理学院 3本章主要内容本章主要内容n作业排序的基本概念作业排序的基本概念n作业排序的表示方式作业排序的表示方式n流水作业排序问题流水作业排序问题n单件作业排序问题单件作业排序问题n服务排队系统设计中的心理因素服务排队系统设计中的心理因素Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 4n医院医院l门诊病人治疗门诊病人治疗l手术室手术室n大学大学l排课排课l教室教室n工厂工厂l生产生产l采购采购作业排序例子作业排序例子Product

3、ion & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 5作业计划与排序作业计划与排序n作业排序作业排序(Sequencing)是确定加工对象是确定加工对象的加工顺序的加工顺序n作业计划作业计划(Scheduling)还要确定开始加还要确定开始加工和完工的时间工和完工的时间n作业排序是作业计划的关键作业排序是作业计划的关键n在实际中，这两个词经常被等同使用在实际中，这两个词经常被等同使用Production & Operations ManagementProduction &

4、Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 6作业排序的战略目的作业排序的战略目的n有效的排序可以提高设施的利用率，这有效的排序可以提高设施的利用率，这意味着：意味着：n有效的排序可以提高交货速度，这意味有效的排序可以提高交货速度，这意味着：着：n好的排序提供好的排序提供更低的成本更低的成本更好的顾客服务更好的顾客服务更可靠的交货更可靠的交货Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 7前向排序与后向排序前

5、向排序与后向排序收到收到订单订单交货期交货期订购订购原料原料作业作业1作业作业2作业作业3作业作业4订购订购原料原料作业作业1作业作业2作业作业3作业作业4前向排序前向排序后向排序后向排序请思考下列两种情况下适用哪种排序方式？请思考下列两种情况下适用哪种排序方式？按订单生产的企业按订单生产的企业为节省库存的费用为节省库存的费用Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 8甘特图（甘特图（ Gantt Chart）n作业进度图作业进度图l表示一项工作的计划

6、开始日期、计划完成日期表示一项工作的计划开始日期、计划完成日期以及现在的进度以及现在的进度n 机器图（甘特负荷图）机器图（甘特负荷图）l描述不同工作在每一台机器上的工作次序，可描述不同工作在每一台机器上的工作次序，可被用来管理生产进度被用来管理生产进度 Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 9作业进度甘特图作业进度甘特图工作工作11/10 11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18 11/19AB

7、C开始时间开始时间结束时间结束时间计划所用时间计划所用时间实际进度实际进度表示一项工作的计划开始日期、计划完成表示一项工作的计划开始日期、计划完成日期以及现在的进度日期以及现在的进度Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 10描述不同工作在每一台机器上的工作次序描述不同工作在每一台机器上的工作次序机器甘特图机器甘特图机器机器11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18磨床磨床抛光机抛光机开始时间开始时

8、间结束时间结束时间计划所用时间计划所用时间实际进度实际进度非生产性时间非生产性时间ABCABCProduction & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 11排序问题的分类排序问题的分类主要是将不同工件安排到不同设备上，或主要是将不同工件安排到不同设备上，或安排不同的人做不同的工作安排不同的人做不同的工作劳动力作业排序劳动力作业排序生产作业排序生产作业排序主要是确定人员何时工作主要是确定人员何时工作n两种基本形式的作业排序两种基本形式的作业排序Production &

9、Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 12制造业生产作业排序分类制造业生产作业排序分类按机器数按机器数量分类量分类单台机器的单台机器的排序问题排序问题多台机器的多台机器的排序问题排序问题单件作业排序问题单件作业排序问题(Job-Shop)流水作业排序问题流水作业排序问题(Flow-Shop)按工件到达车按工件到达车间的情况不同间的情况不同静态排序问题静态排序问题动态排序问题动态排序问题工件陆续到达，要随时安排它们的加工顺序工件陆续到达，要随时安排它们的加工顺序排序时，所有工

10、件都已到达，可一次性进行排序排序时，所有工件都已到达，可一次性进行排序Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 13n个作业的单台机器排序问题个作业的单台机器排序问题(n/1)n对于某一工作地，在给定的一段时间内，对于某一工作地，在给定的一段时间内，顺次决定下一个被加工的工件顺次决定下一个被加工的工件n可能要考虑交付日期、在制品数量、全部可能要考虑交付日期、在制品数量、全部完工时间等因素完工时间等因素 对象对象1对象对象2对象对象3对象对象n工作地工作

11、地Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 14常用的优先顺序规则常用的优先顺序规则先到先服务先到先服务优先选择完工期限最紧的工件优先选择完工期限最紧的工件优先选择加工时间最短的工件优先选择加工时间最短的工件优先选择临界比最小的工件。临界比为优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间工作允许停留时间和工件余下加工时间之比之比优先选择余下加工时间最长的工件优先选择余下加工时间最长的工件优先选择余下加工时间最短的工件优先选择余下加

12、工时间最短的工件优先选择余下工序数最多的工件优先选择余下工序数最多的工件随机地挑选下一个工件随机地挑选下一个工件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规则规则 规则规则解释

13、解释Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 15最先到的工作先处理最先到的工作先处理n大多数作业排序标准能达到平均水平大多数作业排序标准能达到平均水平n对顾客来说是公平的对顾客来说是公平的l对服务组织更重要对服务组织更重要如如: : 餐厅餐厅先到先服务先到先服务FCFS, (First Come, First Served Rule)Production & Operations ManagementProduction & Operations M

14、anagement浙江财经学院工商管理学院浙江财经学院工商管理学院 16n优先处理完工时间最早的工作优先处理完工时间最早的工作n被一些企业广泛的应用被一些企业广泛的应用l如果完工时间很重要如果完工时间很重要lMRPMRP系统系统完工时间完工时间n使最大延迟最小，提高客户满意水平使最大延迟最小，提高客户满意水平在许多排程标准上表现并不是太好在许多排程标准上表现并不是太好最早交货时间最早交货时间EDD（Earliest Due Date Rule）Production & Operations ManagementProduction & Operations Management浙江财经学院工商

15、管理学院浙江财经学院工商管理学院 17最短作业时间最短作业时间SPT（Shortest Processing Time Rule）n优先处理完工时间最短的工作优先处理完工时间最短的工作n可以使工作流最小化，或系统中要完成的工作数可以使工作流最小化，或系统中要完成的工作数量最小化量最小化在单台机器或单个工作中心（在单台机器或单个工作中心（n/1）情况下）情况下使用平均延迟、平均等待时间和平均完成时间上使用平均延迟、平均等待时间和平均完成时间上都能产生最优解。都能产生最优解。最大的缺陷是工作时间长的工作将被不断地最大的缺陷是工作时间长的工作将被不断地推迟。推迟。Production & Opera

16、tions ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 18最小临界值最小临界值(关键比率规划关键比率规划)SCR（Smallest Critical Ratio）n先处理临界值最小的工作先处理临界值最小的工作可以缩短平均延迟时间，有效地跟踪记可以缩短平均延迟时间，有效地跟踪记载工作进展和位置载工作进展和位置CR剩余时间剩余时间剩余工作时间剩余工作时间 完工期完工期 - 今日之日期今日之日期剩余工作时间剩余工作时间=Production & Operations ManagementProductio

17、n & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 19最长余下时间最长余下时间MWKR (Most Work Remaining)n优先选择余下加工时间最长的工作优先选择余下加工时间最长的工作Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 20最短余下时间最短余下时间LWRK (Least work Remaining)n优先选择余下工作时间最短的工作优先选择余下工作时间最短的工作Production & O

18、perations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 21最多余下作业最多余下作业MOPNR (Most Operations Remaining)n优先选择余下处理工序最多的工作优先选择余下处理工序最多的工作Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 22随机规则随机规则（RANDOM）n随机挑选下一个工作随机挑选下一个工作Production &

19、Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 23作业排序方案的评价指标作业排序方案的评价指标n工件流程时间工件流程时间l从工件可以开始加工从工件可以开始加工(不一定是实际的开始时间不一定是实际的开始时间)至完工的时间至完工的时间n全部完工时间全部完工时间l完成一组工作所需的全部时间完成一组工作所需的全部时间 n延迟延迟l可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间完工的工件数占总工件数的百分比来表

20、示完工的工件数占总工件数的百分比来表示n在制品库存在制品库存(WIP)l度量标准可以用工件个数、其货币价值或可供应的周数来表示度量标准可以用工件个数、其货币价值或可供应的周数来表示n总库存总库存l计划入库量和现有库存量的总和为总库存量计划入库量和现有库存量的总和为总库存量n利用率利用率l用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 24工

21、作数量流程时间平均完工时间流程时间处理时间时间利用率 处理时间流程时间在制品）系统中的平均工作数 (工作数量延迟时间平均延迟 作业排序方案的评价指标（续）作业排序方案的评价指标（续）Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 25作业排序目标作业排序目标n满足交货日期满足交货日期n提前期最短提前期最短n准备时间最短或者成本最小准备时间最短或者成本最小n在制品库存最小在制品库存最小n机器或劳动力利用率最大机器或劳动力利用率最大l这一条有争议，因为仅仅考虑保

22、持机器或者劳动力处于这一条有争议，因为仅仅考虑保持机器或者劳动力处于繁忙状态可能不是在工序中进行管理的最有效的方法繁忙状态可能不是在工序中进行管理的最有效的方法Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 26n/1排序问题例排序问题例n李生是李生是A复印公司的主管，复印公司为其所在市区的某复印公司的主管，复印公司为其所在市区的某法律公司提供复印服务，在这周开始，法律公司提供复印服务，在这周开始，5个客户提供了个客户提供了他们的订单。详细的排序数据如下：他

23、们的订单。详细的排序数据如下：作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12所有的订单都要使用唯一的彩色复印机，李生必须决所有的订单都要使用唯一的彩色复印机，李生必须决定定5个订单的加工顺序，评价标准是流程时间最短。个订单的加工顺序，评价标准是流程时间最短。Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 27FCFS作业顺序作业顺序加工时间加工时间交货日期交货日期

24、流程时间流程时间延迟延迟A350+3=30B463+4=7761C277+2=9972D699+6=151596E1215+1=1616214总流程时间总流程时间=3+7+9+15+16=50(天）天）平均流程时间平均流程时间=50/5=10(天）天）总延迟总延迟=0+1+2+6+14=23，平均延迟，平均延迟=23/5=4.6(天）天）Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 28SPT作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间

25、延迟延迟总流程时间总流程时间=平均流程时间平均流程时间=总延迟总延迟=，平均延迟，平均延迟=作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12E120+1=10C271+2=30A353+3=66-5=1B466+4=1010-6=4D6910+6=1616-9=71+3+6+10+16=36(天天)36/5=7.2(天天)1+4+7=12 (天天)12/5=2.4(天天)Production & Operations ManagementProduction & Operations Manageme

26、nt浙江财经学院工商管理学院浙江财经学院工商管理学院 29EDD作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟总流程时间总流程时间=平均流程时间平均流程时间=总延迟总延迟=，平均延迟，平均延迟=作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12E120+1=10A351+3=40B464+4=88-6=2C278+2=1010-7=3D6910+6=1616-9=71+4+8+10+16=39(天天)39/5=7.8(天天)2+3+7=12 (天天)12/5=2.4(天天)Pr

27、oduction & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 30优先调度规则对比优先调度规则对比规划规划总完成时间总完成时间(天天)平均完成时间平均完成时间(天天)平均延迟平均延迟(天天)FCFS50104.6SPT367.22.4EDD397.82.4n从上面可看出，从上面可看出，SPT规则比其他规则较好，规则比其他规则较好，n事实上也是这样，用数学方法可以证明在事实上也是这样，用数学方法可以证明在n/1情况下情况下使用其他衡量标准，如平均等待时间和平均完成时间使用其他衡

28、量标准，如平均等待时间和平均完成时间，SPT都能产生最优解。都能产生最优解。n这种简单的规则如此有用，以至于被称为这种简单的规则如此有用，以至于被称为“整个排序整个排序科学中最重要的概念科学中最重要的概念”Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 31对在制品库存的理解对在制品库存的理解nn/1排序排序n第一件工件开始生产前所有工件已经达到，处于等待状态第一件工件开始生产前所有工件已经达到，处于等待状态机壳加机壳加工次序工次序开始工作开始工作 加工时间

29、加工时间 结束工作结束工作 流程时间流程时间在制品库存贡献在制品库存贡献E01111/16 0.0625A13444/160.25B44888/160.5C82101010/160.625D106161616/161总数总数392.4375平均在制品库存平均在制品库存39/162.4375Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 32对总库存的理解对总库存的理解nn/1排序排序n第一件工件开始生产前所有工件已经达到，处于等待状态第一件工件开始生产前所有

30、工件已经达到，处于等待状态机壳加机壳加工次序工次序加工时间加工时间 结束时间结束时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前延迟提前延迟E11221A34551B48682C2107103D6169167总数总数3941212平均总库存平均总库存41/162.5625Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 33优先规则及其事例（学生练习）优先规则及其事例（学生练习）n例：一个加工车间负责加工发动机机壳，现在共例：一个加工车

31、间负责加工发动机机壳，现在共有有5个机壳等待加工。只有一名技工在岗做此项个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时来，顾客也已经明确提出了他们所希望的完工时间间n分别使用分别使用SPT和和EDD规则进行排序，并计算这规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库两个方案的平均提前时间、延迟时间、在制品库存和总库存存和总库存Production & Operations ManagementProduction & Operations Management

32、浙江财经学院工商管理学院浙江财经学院工商管理学院 34发动机机壳的加工与取货信息发动机机壳的加工与取货信息发动机机壳发动机机壳所需标准加工时间所需标准加工时间(h)(包括机器调整包括机器调整)预计顾客取货时间预计顾客取货时间(h)(从现在开始算起的所需从现在开始算起的所需时间时间)机壳机壳1机壳机壳2机壳机壳3机壳机壳4机壳机壳586153121012201822一个加工车间负责加工发动机机壳，现在共有一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被

33、估算出来，顾客也已经明确提出了他们所希望的完工时间。出来，顾客也已经明确提出了他们所希望的完工时间。请给出分别使用请给出分别使用SPT和和EDD规则进行排序，并计算这两个方案规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存的平均提前时间、延迟时间、在制品库存和总库存Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 35SPT规则排序结果规则排序结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流

34、程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数总数总数平均数平均数平均在制品库存平均在制品库存 平均总库存平均总库存机壳机壳4机壳机壳2机壳机壳1机壳机壳5机壳机壳3Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 36SPT规则排序结果规则排序结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间

35、取货时间提前提前小时数小时数拖延拖延小时数小时数机壳机壳40333181815机壳机壳2369912123机壳机壳198171710177机壳机壳51712292922297机壳机壳329154444204424总数总数1021201838平均数平均数20.43.67.6平均在制品库存平均在制品库存102/442.32个个 平均总库存平均总库存120/44=2.73个个Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 37EDD规则排序结果规则排序结果机壳加机

36、壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数总数总数平均数平均数平均在制品库存平均在制品库存 平均总库存平均总库存机壳机壳1机壳机壳2机壳机壳4机壳机壳3机壳机壳5Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 38EDD规则排序结果规则排序结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结

37、束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数机壳机壳1088810102机壳机壳286141412142机壳机壳4143171718181机壳机壳317153232203212机壳机壳532124444224422总数总数115118336平均数平均数230.67.2平均在制品库存平均在制品库存115/44=2.61 平均总库存平均总库存118/44=2.68Production & Operations ManagementProduction & Operations Management浙江财经学院工商管

38、理学院浙江财经学院工商管理学院 39流水作业排序问题流水作业排序问题n流水作业排序问题的基本特征是每个工流水作业排序问题的基本特征是每个工件的加工路线都一致件的加工路线都一致n讨论讨论所有工件在各台机器上的加工顺序所有工件在各台机器上的加工顺序都相同的情况都相同的情况Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 40最长流程时间最长流程时间n最长流程时间又称加工周期最长流程时间又称加工周期n是第一个工件在一台机器开始加工时算起，到是第一个工件在一台机器开始

39、加工时算起，到最后一个工件在最后一台机器上完工时为至所最后一个工件在最后一台机器上完工时为至所经过的时间经过的时间n假定所有工件到达时间为零，则假定所有工件到达时间为零，则最长流程时间最长流程时间=排在末位加工工件在车间的停排在末位加工工件在车间的停留时间留时间n流水作业排序一个目标函数：最长流程时间最流水作业排序一个目标函数：最长流程时间最短短Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 41最长流程时间最长流程时间n设设n个工件的加工顺序为个工件的加工

40、顺序为S=(S1,S2,Sn)iksC1111iiissspCCksskskksiiiipCCC)()1(1,max表示工件表示工件Si在机器在机器Mk上的完工时间上的完工时间ksip表示工件表示工件Si在机器在机器Mk上的加工时间上的加工时间Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 42加工顺序矩阵加工顺序矩阵i615243Pi1244213Pi2544576Pi3555857Pi4143234Production & Operations Mana

41、gementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 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时间时间Production & Operations ManagementProduction & Operations Man

42、agement浙江财经学院工商管理学院浙江财经学院工商管理学院 44n个作业两台机器排序问题个作业两台机器排序问题(n/2)n两个或者更多以上的作业必须在两台机器两个或者更多以上的作业必须在两台机器上以共同的工序进行加工上以共同的工序进行加工n评价标准：从第一个作业开始到最后一个评价标准：从第一个作业开始到最后一个作业结束的总流程时间最短，即全部完工作业结束的总流程时间最短，即全部完工时间最短时间最短Johnson方法（约翰逊方方法（约翰逊方法）法）Production & Operations ManagementProduction & Operations Management浙江财经学

43、院工商管理学院浙江财经学院工商管理学院 45nN项作业按相同顺序经过项作业按相同顺序经过2台机器加工，使全台机器加工，使全部完工时间最小部完工时间最小nN项作业的双机排序（项作业的双机排序（N/2）锯锯钻钻工作工作 A工作工作 B工作工作 C工作工作 (N = 3)Johnson方法（约翰逊方法）方法（约翰逊方法）Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 46Johnson方法方法 - N项作业的双机排序项作业的双机排序(1)列出每个作业在两台机器上的

44、加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(2)和和(3)，直到所有，直到所有作业排序完毕作业排序完毕Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商

45、管理学院 47列出作业及加工时间列出作业及加工时间全部安排全部安排完毕完毕?Yes12YesNoNoJohnson法的步骤法的步骤选择加工时间选择加工时间最短的作业最短的作业哪台机器？哪台机器？先完成这一作业先完成这一作业最后完成这一作业最后完成这一作业删除这一作业删除这一作业还有剩余还有剩余作业吗？作业吗？结束结束强制结束强制结束Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 48Johnson法法 例子例子作业作业工作工作1工作工作2Y11222Y245

46、Y353Y41516Y5108(1)列出每个作业在两台机器上的加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(2)和和(3)，直到所有作业排序完毕，直到所有作业排序完毕Production & Operations ManagementProduction & Operations

47、 Management浙江财经学院工商管理学院浙江财经学院工商管理学院 49Johnson法法 例子例子步骤步骤 1步骤步骤 2步骤步骤 3步骤步骤 4步骤步骤 5(1)列出每个作业在两台机器上的加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(2)和和(3)，直到所有作业排序完毕，

48、直到所有作业排序完毕作业作业工作工作1工作工作2Y11222Y245Y353Y41516Y5108Y3Y1Y2Y4Y5Y3Y3Y3Y3Y2Y2Y2Y5Y5Y1Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 50Johnson法例子的甘特图法例子的甘特图工序1工序1工序2工序245450 05 510101515202025253030353540405050555560606565Y2(4)Y1(12)Y4(15)Y5(10)Y3(5)空闲，等待新任务空闲，

49、等待新任务Y2(5)Y1(22)Y4(16)Y5(8)Y3(3)空闲空闲空闲空闲Y4Y3Y2Y5Y1Production & Operations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 51提问提问n如果第一台机器的某作业的所用时间同第如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，应该如二台机器的另一作业的时间相同，应该如何排序？何排序？n如果一项作业在两台机器上的作业时间相如果一项作业在两台机器上的作业时间相同，应该如何排序？同，应该如何排序？Production & Op

50、erations ManagementProduction & Operations Management浙江财经学院工商管理学院浙江财经学院工商管理学院 52Johnson法的补充说明法的补充说明n如果第一台机器的某作业的所用时间同第二台机如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，则第一台机器的这一器的另一作业的时间相同，则第一台机器的这一作业安排在前面完成，而第二台机器的这项作业作业安排在前面完成，而第二台机器的这项作业安排在后面完成安排在后面完成n如果一项作业在两台机器上的作业时间相同，这如果一项作业在两台机器上的作业时间相同，这个项目可以被安排在两个作业时间的任