生产与运作管理作业排序解析学习教案.pptx

会计学1生产与运作管理作业排序生产与运作管理作业排序(pi x)解析解析第一页，共87页。生产运作管理生产运作管理(gunl)模型模型输入待转化资源输入待转化资源物料物料(w lio)信息信息顾客顾客输入转化资源输入转化资源(zyun)设施设施 员工员工顾顾客客输入资源输入资源输出输出产品与服务产品与服务改改善善计计划划与与控控制制设计设计运作战运作战略略企业企业战略战略作业排序作业排序第1页/共87页第二页，共87页。本章本章(bn zhn)主要内容主要内容n n作业排序的基本概念n n作业排序的表示方式n n流水作业排序问题n n单件作业排序问题n n服务(fw)排队系统设计中的心理因素第2页/共87页第三页，共87页。n n医院n n门诊病人治疗n n手术室n n大学n n排课n n教室n n工厂n n生产(shngchn)n n采购作业作业(zuy)排序例子排序例子第3页/共87页第四页，共87页。作业作业(zuy)计划与排序计划与排序n n作业排序(Sequencing)是确定加工对象的加工顺序n n作业计划(Scheduling)还要确定开始加工和完工的时间n n作业排序是作业计划的关键n n在实际中，这两个词经常(jngchng)被等同使用第4页/共87页第五页，共87页。作业作业(zuy)排序的战略排序的战略目的目的n n有效的排序可以(ky)提高设施的利用率，这意味着：n n有效的排序可以(ky)提高交货速度，这意味着：n n好的排序提供更低的成本更低的成本(chngbn)更好的顾客服务更好的顾客服务更可靠的交货更可靠的交货第5页/共87页第六页，共87页。前向排序前向排序(pi x)与后向排序与后向排序(pi x)收到收到订单订单(dn dn)交货期交货期订购订购原料原料作业作业1作业作业2作业作业3作业作业4订购订购原料原料作业作业1作业作业2作业作业3作业作业4前向排序前向排序(pi x)后向排序后向排序请思考下列两种情况下适用哪种排序方式？请思考下列两种情况下适用哪种排序方式？按订单生产的企业按订单生产的企业为节省库存的费用为节省库存的费用第6页/共87页第七页，共87页。甘特图（甘特图（Gantt Chart）n n作业进度图n n表示一项工作的计划开始日期(rq)、计划完成日期(rq)以及现在的进度n n 机器图（甘特负荷图）n n描述不同工作在每一台机器上的工作次序，可被用来管理生产进度 第7页/共87页第八页，共87页。作业作业(zuy)进度甘特图进度甘特图工作工作11/10 11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18 11/19ABC开始开始(kish)时间时间结束结束(jish)时间时间计划所用时间计划所用时间实际进度实际进度表示一项工作的计划开始日期、计划完成日期以及现在的进度表示一项工作的计划开始日期、计划完成日期以及现在的进度第8页/共87页第九页，共87页。描述描述(mio sh)(mio sh)不同工作在每一台机器上的工作次序不同工作在每一台机器上的工作次序机器机器(j q)甘特图甘特图机器机器11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18磨床磨床抛光机抛光机开始开始(kish)时间时间结束时间结束时间计划所用时间计划所用时间实际进度实际进度非生产性时间非生产性时间ABCABC第9页/共87页第十页，共87页。排序问题排序问题排序问题排序问题(wnt)(wnt)的分类的分类的分类的分类主要主要(zhyo)(zhyo)是将不同工件安排到不同设是将不同工件安排到不同设备上，或安排不同的人做不同的工作备上，或安排不同的人做不同的工作劳动力作业劳动力作业(zuy)排排序序生产作业排序生产作业排序主要是确定人员何时工作主要是确定人员何时工作n两种基本形式的作业排序两种基本形式的作业排序第10页/共87页第十一页，共87页。制造业生产作业制造业生产作业制造业生产作业制造业生产作业(zuy)(zuy)排序分类排序分类排序分类排序分类按机器数按机器数量量(shling)分类分类单台机器的排单台机器的排序序(pi x)问问题题多台机器的排多台机器的排序问题序问题单件作业排序问题单件作业排序问题(Job-Shop)流水作业排序问题流水作业排序问题(Flow-Shop)按工件到达车间按工件到达车间的情况不同的情况不同静态排序问题静态排序问题动态排序问题动态排序问题工件陆续到达，要随时安排它们的加工顺序工件陆续到达，要随时安排它们的加工顺序排序时，所有工件都已到达，可一次性进行排序排序时，所有工件都已到达，可一次性进行排序第11页/共87页第十二页，共87页。n n个作业的单台机器个作业的单台机器个作业的单台机器个作业的单台机器(j q)(j q)排序问题排序问题排序问题排序问题(n/1)(n/1)n n对于某一工作地，在给定的一段时间内，顺次决定下一个被加工的工件n n可能要考虑交付(jiof)日期、在制品数量、全部完工时间等因素 对象对象(duxing)1对象对象2对象对象3对象对象n工作地工作地第12页/共87页第十三页，共87页。常用常用常用常用(chn(chn yn yn)的优先顺序规则的优先顺序规则的优先顺序规则的优先顺序规则先到先服务先到先服务优先选择完工期限最紧的工件优先选择完工期限最紧的工件优先选择加工时间最短的工件优先选择加工时间最短的工件优先选择临界比最小的工件。临界比为工作优先选择临界比最小的工件。临界比为工作(gngzu)(gngzu)允许停留时间和工件余下加工时允许停留时间和工件余下加工时间之比间之比优先选择余下加工时间最长的工件优先选择余下加工时间最长的工件优先选择余下加工时间最短的工件优先选择余下加工时间最短的工件优先选择余下工序数最多的工件优先选择余下工序数最多的工件随机地挑选下一个工件随机地挑选下一个工件FCFS(First Come First Served)规则规则(guz)EDD(Earliest Due Date)规则规则(guz)SPT(Shortest Processing Time)规则规则(guz)SCR(Smallest Critical Ratio)规则规则(guz)MWKR(Most Work Remaining)规则规则(guz)LWRK(Least work Remaining)规则规则(guz)MOPNR(Most Operations Remaining)规则规则(guz)RANDOM规则规则(guz)规则规则解释解释第13页/共87页第十四页，共87页。最先到的工作先处理最先到的工作先处理大多数作业排序标准能达到平均水平大多数作业排序标准能达到平均水平对顾客来说是公平的对顾客来说是公平的对服务对服务(fw)(fw)组织更重要组织更重要如如:餐厅餐厅先到先服务先到先服务先到先服务先到先服务(fw)(fw)FCFS,(First Come,First Served Rule)FCFS,(First Come,First Served Rule)第14页/共87页第十五页，共87页。n n优先处理完工时间最早的工作n n被一些企业广泛的应用n n如果完工时间很重要n nMRP系统n n完工时间n n使最大延迟(ynch)最小，提高客户满意水平n n在许多排程标准上表现并不是太好最早交货最早交货最早交货最早交货(jio hu)(jio hu)时间时间时间时间EDDEDD（Earliest Due Date RuleEarliest Due Date Rule）第15页/共87页第十六页，共87页。最短作业最短作业最短作业最短作业(zuy)(zuy)时间时间时间时间SPTSPT（Shortest Processing Time RuleShortest Processing Time Rule）n n优先处理完工时间最短的工作优先处理完工时间最短的工作n n可以使工作流最小化，或系统可以使工作流最小化，或系统(xt(xt ng)ng)中要完成的工中要完成的工作数量最小化作数量最小化n n在单台机器或单个工作中心（在单台机器或单个工作中心（n/1n/1）情况下使）情况下使用平均延迟、平均等待时间和平均完成时间上都能产用平均延迟、平均等待时间和平均完成时间上都能产生最优解。生最优解。n n最大的缺陷是工作时间长的工作将被不断地推最大的缺陷是工作时间长的工作将被不断地推迟。迟。第16页/共87页第十七页，共87页。最小临界值最小临界值最小临界值最小临界值(关键比率关键比率关键比率关键比率(bl)(bl)规划规划规划规划)SCRSCR（Smallest Critical RatioSmallest Critical Ratio）临界值：距离完工期剩余临界值：距离完工期剩余临界值：距离完工期剩余临界值：距离完工期剩余(shngy)(shngy)时间与剩余时间与剩余时间与剩余时间与剩余(shngy)(shngy)工作时间之比值工作时间之比值工作时间之比值工作时间之比值n n先处理临界值最小的工作先处理临界值最小的工作n n可以可以(ky(ky)缩短平均延迟时间，有效地跟踪记载缩短平均延迟时间，有效地跟踪记载工作进展和位置工作进展和位置CR剩余时间剩余时间剩余工作时间剩余工作时间 完工期完工期-今日之日期今日之日期剩余工作时间剩余工作时间=第17页/共87页第十八页，共87页。最长余下最长余下最长余下最长余下(yxi)(yxi)时间时间时间时间MWKR(Most Work Remaining)MWKR(Most Work Remaining)n n优先选择余下优先选择余下(yxi)(yxi)加工时间最长的工作加工时间最长的工作第18页/共87页第十九页，共87页。最短余下最短余下最短余下最短余下(yxi)(yxi)时间时间时间时间LWRK(Least work Remaining)LWRK(Least work Remaining)n n优先选择余下工作优先选择余下工作(gngzu)(gngzu)时间最短的工作时间最短的工作(gngzu)(gngzu)第19页/共87页第二十页，共87页。最多余最多余最多余最多余(duy)(duy)下作业下作业下作业下作业MOPNR(Most Operations Remaining)MOPNR(Most Operations Remaining)n n优先选择余下处理优先选择余下处理(ch(ch l l)工序最多的工作工序最多的工作第20页/共87页第二十一页，共87页。随机随机随机随机(su j)(su j)规则（规则（规则（规则（RANDOMRANDOM）n n随机随机(su j)(su j)挑选下一个工作挑选下一个工作第21页/共87页第二十二页，共87页。作业作业作业作业(zuy)(zuy)排序方案的评价指标排序方案的评价指标排序方案的评价指标排序方案的评价指标n n工件流程时间工件流程时间n n从工件可以开始加工从工件可以开始加工(不一定不一定(ydng)(ydng)是实际的开始时间是实际的开始时间)至完工的时间至完工的时间n n全部完工时间全部完工时间n n完成一组工作所需的全部时间完成一组工作所需的全部时间 n n延迟延迟n n可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间完工的工件数占总工件数的百分比来表示完工的工件数占总工件数的百分比来表示n n在制品库存在制品库存(WIP)(WIP)n n度量标准可以用工件个数、其货币价值或可供应的周数来表示度量标准可以用工件个数、其货币价值或可供应的周数来表示n n总库存总库存n n计划入库量和现有库存量的总和为总库存量计划入库量和现有库存量的总和为总库存量n n利用率利用率n n用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示第22页/共87页第二十三页，共87页。作业排序作业排序作业排序作业排序(pi x)(pi x)方案的评价指标（续）方案的评价指标（续）方案的评价指标（续）方案的评价指标（续）第23页/共87页第二十四页，共87页。作业作业(zuy)排序目标排序目标n n满足交货日期满足交货日期n n提前期最短提前期最短n n准备时间最短或者成本最小准备时间最短或者成本最小n n在制品库存最小在制品库存最小n n机器或劳动力利用率最大机器或劳动力利用率最大n n这一条有争议这一条有争议(zhngy)(zhngy)，因为仅仅考虑保持机器或者，因为仅仅考虑保持机器或者劳动力处于繁忙状态可能不是在工序中进行管理的最劳动力处于繁忙状态可能不是在工序中进行管理的最有效的方法有效的方法第24页/共87页第二十五页，共87页。n/1n/1排序排序排序排序(pi x)(pi x)问题例问题例问题例问题例n n李生是李生是A A复印公司的主管，复印公司为其所在市区的某法复印公司的主管，复印公司为其所在市区的某法律公司提供复印服务，在这周开始律公司提供复印服务，在这周开始(kish(kish)，5 5个客户提个客户提供了他们的订单。详细的排序数据如下：供了他们的订单。详细的排序数据如下：作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12所有的订单都要使用唯一所有的订单都要使用唯一(wi y)的彩色复印机，李生必须决定的彩色复印机，李生必须决定5个订单的加工顺序，评价标准是流程时间最短。个订单的加工顺序，评价标准是流程时间最短。第25页/共87页第二十六页，共87页。FCFSFCFS作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟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(天）天）第26页/共87页第二十七页，共87页。SPTSPT作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟总流程时间总流程时间=平均流程时间平均流程时间=总延迟总延迟=，平均延迟，平均延迟=作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）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(天天)第27页/共87页第二十八页，共87页。EDDEDD作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟总流程时间总流程时间=平均流程时间平均流程时间=总延迟总延迟=，平均延迟，平均延迟=作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）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(天天)第28页/共87页第二十九页，共87页。优先优先优先优先(yuxin)(yuxin)调度规则对比调度规则对比调度规则对比调度规则对比规划规划总完成时间总完成时间(天天)平均完成时间平均完成时间(天天)平均延迟平均延迟(天天)FCFS50104.6SPT367.22.4EDD397.82.4n从上面可看出，从上面可看出，SPT规则比其他规则较好，规则比其他规则较好，n事实上也是这样事实上也是这样(zhyng)，用数学方法可以证明在，用数学方法可以证明在n/1情况下使用其他衡量标准，如平均等待时间和平均情况下使用其他衡量标准，如平均等待时间和平均完成时间，完成时间，SPT都能产生最优解。都能产生最优解。n这种简单的规则如此有用，以至于被称为这种简单的规则如此有用，以至于被称为“整个排序科整个排序科学中最重要的概念学中最重要的概念”第29页/共87页第三十页，共87页。对在制品库存对在制品库存(kcn)的理解的理解n nn/1n/1排序排序n n第一件工件开始生产前所有工件已经达到第一件工件开始生产前所有工件已经达到(d do)(d do)，处于等待状态，处于等待状态机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间在制品库存贡献在制品库存贡献E01111/16 0.0625A13444/160.25B44888/160.5C82101010/160.625D106161616/161总数总数392.4375平均在制品库存平均在制品库存39/162.4375第30页/共87页第三十一页，共87页。对总库存对总库存(kcn)的理解的理解n nn/1n/1排序排序n n第一件工件开始生产前所有工件已经达到第一件工件开始生产前所有工件已经达到(d do)(d do)，处于等待状态，处于等待状态机壳加机壳加工次序工次序加工时间加工时间 结束时间结束时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前延迟提前延迟E11221A34551B48682C2107103D6169167总数总数3941212平均总库存平均总库存41/162.5625第31页/共87页第三十二页，共87页。优先优先优先优先(yuxin)(yuxin)规则及其事例（学生练习）规则及其事例（学生练习）规则及其事例（学生练习）规则及其事例（学生练习）n n例：一个加工车间负责加工发动机机壳，现在共有例：一个加工车间负责加工发动机机壳，现在共有5 5个机壳等待加工。只个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间来，顾客也已经明确提出了他们所希望的完工时间n n分别使用分别使用SPTSPT和和EDDEDD规则进行排序，并计算这两个方案的平均提前时间、规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品延迟时间、在制品(zhp(zhp n)n)库存和总库存库存和总库存第32页/共87页第三十三页，共87页。发动机机壳的加工发动机机壳的加工(ji gng)与与取货信息取货信息发动机机壳发动机机壳所需标准加工时间所需标准加工时间(h)(包括机器调整包括机器调整)预计顾客取货时间预计顾客取货时间(h)(从现在开始算起的所需从现在开始算起的所需时间时间)机壳机壳1机壳机壳2机壳机壳3机壳机壳4机壳机壳586153121012201822一个加工一个加工(ji gng)车间负责加工车间负责加工(ji gng)发动机机壳，现在共有发动机机壳，现在共有5个机壳等个机壳等待加工待加工(ji gng)。只有一名技工在岗做此项工作。现各个机壳的标准加工。只有一名技工在岗做此项工作。现各个机壳的标准加工(ji gng)时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间。间。请给出分别使用请给出分别使用SPT和和EDD规则进行排序，并计算这两个方案的规则进行排序，并计算这两个方案的平均平均(pngjn)提前时间、延迟时间、在制品库存和总库存提前时间、延迟时间、在制品库存和总库存第33页/共87页第三十四页，共87页。SPT规则排序规则排序(pi x)结果结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数总数总数平均数平均数平均在制品库存平均在制品库存 平均总库存平均总库存机壳机壳4机壳机壳2机壳机壳1机壳机壳5机壳机壳3第34页/共87页第三十五页，共87页。SPT规则排序规则排序(pi x)结果结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数机壳机壳40333181815机壳机壳2369912123机壳机壳198171710177机壳机壳51712292922297机壳机壳329154444204424总数总数1021201838平均数平均数20.43.67.6平均在制品库存平均在制品库存102/442.32个个 平均总库存平均总库存120/44=2.73个个第35页/共87页第三十六页，共87页。EDD规则排序规则排序(pi x)结果结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数总数总数平均数平均数平均在制品库存平均在制品库存 平均总库存平均总库存机壳机壳1机壳机壳2机壳机壳4机壳机壳3机壳机壳5第36页/共87页第三十七页，共87页。EDD规则排序规则排序(pi x)结果结果机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数机壳机壳1088810102机壳机壳286141412142机壳机壳4143171718181机壳机壳317153232203212机壳机壳532124444224422总数总数115118336平均数平均数230.67.2平均在制品库存平均在制品库存115/44=2.61 平均总库存平均总库存118/44=2.68第37页/共87页第三十八页，共87页。流水作业流水作业流水作业流水作业(lishu(lishu zu y)zu y)排序问题排序问题排序问题排序问题n n流水作业流水作业(lishu(lishu zu y)zu y)排序问题的基本特征排序问题的基本特征是每个工件的加工路线都一致是每个工件的加工路线都一致n n讨论所有工件在各台机器上的加工顺序都相同讨论所有工件在各台机器上的加工顺序都相同的情况的情况第38页/共87页第三十九页，共87页。最长流程最长流程最长流程最长流程(lichng)(lichng)时间时间时间时间n n最长流程最长流程(lichng)(lichng)时间又称加工周期时间又称加工周期n n是第一个工件在一台机器开始加工时算起，到最后一是第一个工件在一台机器开始加工时算起，到最后一个工件在最后一台机器上完工时为至所经过的时间个工件在最后一台机器上完工时为至所经过的时间n n假定所有工件到达时间为零，则假定所有工件到达时间为零，则n n最长流程最长流程(lichng)(lichng)时间时间=排在末位加工工件排在末位加工工件在车间的停留时间在车间的停留时间n n流水作业排序一个目标函数：最长流程流水作业排序一个目标函数：最长流程(lichng)(lichng)时时间最短间最短第39页/共87页第四十页，共87页。最长流程最长流程最长流程最长流程(lichng)(lichng)时间时间时间时间n n设设n n个工件的加工个工件的加工(ji gng)(ji gng)顺序为顺序为S=(S1,S2,Sn)S=(S1,S2,Sn)表示工件表示工件Si在机器在机器(j q)Mk上的完工时间上的完工时间表示工件表示工件Si在机器在机器Mk上的加工时间上的加工时间第40页/共87页第四十一页，共87页。加工加工(ji gng)顺序矩阵顺序矩阵i615243Pi1244213Pi2544576Pi3555857Pi4143234第41页/共87页第四十二页，共87页。加工顺序矩阵加工顺序矩阵(j zhn)图示解释图示解释 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机器机器(j q)1机器机器(j q)2机器机器3机器机器4时间时间第42页/共87页第四十三页，共87页。n个作业个作业(zuy)两台机器排序问两台机器排序问题题(n/2)n n两个或者更多以上(yshng)的作业必须在两台机器上以共同的工序进行加工n n评价标准：从第一个作业开始到最后一个作业结束的总流程时间最短，即全部完工时间最短Johnson方法（约翰逊方法）第43页/共87页第四十四页，共87页。n nNN项作业按相同顺序项作业按相同顺序(shnx)(shnx)经过经过2 2台机器加工，台机器加工，使全部完工时间最小使全部完工时间最小n nNN项作业的双机排序（项作业的双机排序（N/2N/2）锯锯钻钻工作工作(gngzu)A工作工作(gngzu)B工作工作 C工作工作(N=3)Johnson方法（约翰逊方法）方法（约翰逊方法）第44页/共87页第四十五页，共87页。Johnson方法方法-N项作业项作业(zuy)的双机排序的双机排序(1)(1)列出每个作业在两台列出每个作业在两台(li(li n n ti)ti)机器上的加工时间机器上的加工时间(2)(2)选择最短的加工时间。如果最短的加工时间来自第选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成器，那么这个作业就放在最后完成(3)(3)删除已排序作业删除已排序作业(4)(4)对剩余作业重复步骤对剩余作业重复步骤(2)(2)和和(3)(3)，直到所有作业排序完，直到所有作业排序完毕毕第45页/共87页第四十六页，共87页。列出作业及加工列出作业及加工(ji gng)时时间间全部安排全部安排(npi)完毕完毕?Yes12YesNoNoJohnson法的步骤法的步骤(bzhu)选择加工时间选择加工时间最短的作业最短的作业哪台机器？哪台机器？先完成这一作业先完成这一作业最后完成这一作业最后完成这一作业删除这一作业删除这一作业还有剩余还有剩余作业吗？作业吗？结束结束强制结束强制结束第46页/共87页第四十七页，共87页。Johnson法法 例子例子(l zi)作业作业工作工作1工作工作2Y11222Y245Y353Y41516Y5108(1)列出每个作业在两台机器上的加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(bzhu)(2)和和(3)，直到所有作业排序完毕，直到所有作业排序完毕第47页/共87页第四十八页，共87页。Johnson法法 例子例子(l zi)步骤步骤(bzhu)1步骤步骤(bzhu)2步骤步骤 3步骤步骤 4步骤步骤 5(1)列出每个作业在两台机器上的加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成后完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(2)和和(3)，直到所有作业排序完毕，直到所有作业排序完毕作业作业工作工作1工作工作2Y11222Y245Y353Y41516Y5108Y3Y1Y2Y4Y5Y3Y3Y3Y3Y2Y2Y2Y5Y5Y1第48页/共87页第四十九页，共87页。Johnson法例子法例子(l zi)的甘特图的甘特图Y2(4)Y1(12)Y4(15)Y5(10)Y3(5)空闲空闲(kngxin)，等待新任，等待新任务务Y2(5)Y1(22)Y4(16)Y5(8)Y3(3)空闲空闲(kngxin)空闲空闲Y4Y3Y2Y5Y1第49页/共87页第五十页，共87页。提问提问(twn)n n如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，应该如何(rh)排序？n n如果一项作业在两台机器上的作业时间相同，应该如何(rh)排序？第50页/共87页第五十一页，共87页。Johnson法的补充法的补充(bchng)说明说明n n如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同相同(xin(xin tn tn)，则第一台机器的这一作业安排在前面完成，而第，则第一台机器的这一作业安排在前面完成，而第二台机器的这项作业安排在后面完成二台机器的这项作业安排在后面完成n n如果一项作业在两台机器上的作业时间相同如果一项作业在两台机器上的作业时间相同(xin(xin tn tn)，这个项目，这个项目可以被安排在两个作业时间的任一一个可以被安排在两个作业时间的任一一个第51页/共87页第五十二页，共87页。JohnsonJohnson法的优化（法的优化（法的优化（法的优化（P303P303）n n第一台机器上的加工时间第一台机器上的加工时间(shjin)(shjin)记为记为ai ai，第二台机器上的加工时间，第二台机器上的加工时间(shjin)bi(shjin)bin n将所有工件将所有工件ai biai bi按按ai ai值不减的顺序排成一个序列值不减的顺序排成一个序列A An n将所有工件将所有工件ai ai bi bi按按bi bi值不增的顺序排成一个序列值不增的顺序排成一个序列B Bn n将将A A放在放在B B之前，就构成了最优加工顺序之前，就构成了最优加工顺序第52页/共87页第五十三页，共87页。Johnson法的优化法的优化n n ai bi ai bi按按ai ai值不减值不减(b ji(b ji n)n)的序列的序列A A：(4,12,15),(Y2,Y1,Y4)(4,12,15),(Y2,Y1,Y4)作业作业工作工作1工作工作2Y11222Y245Y353Y41516Y51084121538Y4Y3Y2Y5Y1nai bi按按bi值不增的序列值不增的序列(xli)B：(8,3),(Y5,Y3)第53页/共87页第五十四页，共87页。n个作业个作业n台机器台机器(j q)排序问题排序问题(n/n)n n当作业数和机器(j q)数相同时，能够同时开始所有作业n n作业排序问题不是哪个作业先开始，而是哪个作业指派到哪台机器(j q)上的安排使得总排序最佳第54页/共87页第五十五页，共87页。n/nn/n作业问题作业问题作业问题作业问题(wnt)(wnt)的分配方法的分配方法的分配方法的分配方法Assignment MethodAssignment Method分配方法是一种特殊的可将任务或工作分配方法是一种特殊的可将任务或工作(gngzu)分配给相应的资源的线性规划模型，分配给相应的资源的线性规划模型，是线性规划运输问题的一个特例。是线性规划运输问题的一个特例。适用于有适用于有n个需求和个需求和n个供给的情况个供给的情况成本成本(chngbn)或时或时间达到最少间达到最少目标目标特征特征一件工作一件工作(或一个人或一个人)仅分配给一台机器仅分配给一台机器(或一个项目或一个项目)第55页/共87页第五十六页，共87页。n/nn/n作业问题的分配作业问题的分配作业问题的分配作业问题的分配(fnpi)(fnpi)方法方法方法方法每个分配问题用一张表，表中数字是每个分配问题用一张表，表中数字是与特定的分配相关的成本或时间。与特定的分配相关的成本或时间。通过在增加或减少一适当的数字以找通过在增加或减少一适当的数字以找到各种到各种(zhn)分配的最小机会成本。分配的最小机会成本。第56页/共87页第五十七页，共87页。分配方法分配方法分配方法分配方法(fngf(fngf)的步骤的步骤的步骤的步骤1.将每行数字将每行数字(shz)减去该行中最小数字减去该行中最小数字(shz)，将每列减去该列中最小数字将每列减去该列中最小数字(shz)。2.画数量最小的水平线和垂直线以盖住表中的所有的零。画数量最小的水平线和垂直线以盖住表中的所有的零。若直线数等于表的行或列数，那么我们若直线数等于表的行或列数，那么我们(w men)就找就找到了最优分配到了最优分配(见步骤见步骤4)；否则进入步骤；否则进入步骤3。3.从未被直线盖住的所有数中减去最小的数，并将此从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上。再回到步最小数加到所有两两相交之处的数上。再回到步骤骤2往下操作直到出现可能的最佳分配。往下操作直到出现可能的最佳分配。4.最佳分配总在表中零位置出现。最佳分配总在表中零位置出现。第57页/共87页第五十八页，共87页。分配方法分配方法分配方法分配方法(fngf(fngf)示例示例示例示例 机器机器工作工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元将工作分配到机器将工作分配到机器(j q)上去上去第58页/共87页第五十九页，共87页。分配分配分配分配(fnpi)(fnpi)方法示例方法示例方法示例方法示例机器机器工作工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元步骤步骤1a1a：从各行数字：从各行数字(shz)(shz)中减去其中数字中减去其中数字(shz)(shz)最小的数字最小的数字(shz)(shz)机器机器工作工作ABCR-34S-66T-50658002325087第59页/共87页第六十页，共87页。分配方法分配方法分配方法分配方法(fngf(fngf)示例示例示例示例机器机器工作工作ABCR-34580S-66023T-50250步骤步骤1b1b：从各列数字：从各列数字(shz)(shz)中减去其中数字中减去其中数字(shz)(shz)最小的数字最小的数字(shz)(shz)机器机器工作工作ABCR-34S-66T-50050226030300第60页/共87页第六十一页，共87页。分配分配分配分配(fnpi)(fnpi)方法示例方法示例方法示例方法示例机器机器工作工作ABCR-34560S-66003T-50230步骤步骤(bzhu)2(bzhu)2：画最小数目的直线盖住所有的：画最小数目的直线盖住所有的0 0直线直线(zhxin)(zhxin)数数=2=2行行(列列)数数3 3，故非最优答案，故非最优答案第61页/共87页第六十二页，共87页。分配方法分配方法分配方法分配方法(fngf(fngf)示例示例示例示例机器机器工作工作ABCR-34560S-66003T-50230步骤步骤(bzhu)3：从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上：从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上 机器机器工作工作ABCR-340S-6600T-50034015回到步骤回到步骤(bzhu)2(bzhu)2，画线盖，画线盖0 0由于