生产运作管理制造业作业计划与控制课件

第十一章制造业作业计划与控制引言通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。

第十一章制造业作业计划与控制引言111.1作业计划问题的基本概念11.2流水作业排序问题11.3单件作业的排序问题11.4生产作业控制

11.1作业计划问题的基本概念211收入、费用和利润要求掌握：最长流程时间的计算2.约翰逊算法3.一般流水作业排序问题的3种启发式算法4.相同零件的3种移动方式下机器加工周期的计算方法学习目的与要求11收入、费用和利润要求掌握：学习目的与要求3

重点最长流程时间的计算约翰逊算法相同零件的3种移动方式下机器加工周期的计算方法

难点一般流水作业排序问题的启发式算法教学重点与难点重点教学重点与难点4生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。将任务安排到工作地，牵涉到作业计划。生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全5编制作业计划要解决的问题由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间例如;医院要安排病人手术，为此要安排手术室，配备手术器械、手术医师和护士。编制作业计划要解决的问题由于每台机器都可能被分配了多项任务，6第一节排序问题的基本概念一、名词术语排序：确定工件在机器上的加工顺序。作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。赶工：实际进度已落后于计划进度时采取的行动。第一节排序问题的基本概念一、名词术语7“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服8二、假设条件和符号说明假设条件：1.一个工件不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。4.每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件二、假设条件和符号说明假设条件：9有关符号Ji：工件i，i=1，2，…，nMj：机器j，j=1，2，…，npij为Ji在Mj上的加工时间ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最早时间di为Ji的完工期限Ci为Ji的完工时间Cmax为最长完工时间Fi为Ji的流程时间，即工件在车间的实际停留时间Fmax为最长流程时间Li为工件的延迟时间Lmax为最长延迟时间有关符号Ji：工件i，i=1，2，…，n10三、排序问题的分类根据机器数的多少单台机器的排序问题多台机器的排序问题对于多台机器排序问题，根据加工路线的特征，分成单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。三、排序问题的分类根据机器数的多少11根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序根据工件到达系统的情况124参数法n/m/A/B其中，n为工件数m为机器数A车间类型。在A的位置若标以标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。当m=1，则A处为空白。B为目标函数，通常是使其值最小例如：n/3/P/Cmax4参数法n/m/A/B13四、作业排序方案的评价标准1.工作流程时间从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。2.加工周期完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。四、作业排序方案的评价标准1.工作流程时间143.在制品库存（WIP）在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。4.利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。3.在制品库存（WIP）15五、优先调度规则调度方法：所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。五、优先调度规则调度方法：16常用的优先顺序规则：FCFS规则优先选择最早进入可排序集合的工件。EDD规则优先选择完工期限最紧的工作。SPT规则优先选择加工时间最短的工件。SCR规则优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。MWKR规则优先选择余下加工时间最长的工件。LWKR规则优先选择余下加工时间最短的工件。MOPNR规则优先选择余下工序数最多的工件。RANDOM规则随机地挑选下一个工件。常用的优先顺序规则：FCFS规则优先选择最早进入可排序集合17一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化一般作业排序的目标18[例]一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。发动机机壳所需标准加工时间（包括机器调整）预计顾客取货时间（从现在开始算起的所需工作时间）机壳1810机壳2612机壳31520机壳4318机壳51222[例]一个加工车间负责加工发动机机壳，现在共有5个机壳等待19机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存=102/44=2.32个平均总库存=120/44=2.73个SPT规则排序结果顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和÷加工周期平均总库存=各工件实际取货时间之和÷加工周期机壳加工次序开始加工结束流程预计顾客顾客实际取货时间提前拖延20机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数23.00.67.2平均在制品库存=115/44=2.61个平均总库存=118/44=2.68个EDD规则排序结果顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。机壳加工次序开始加工结束流程预计顾客顾客实际取货时间提前拖延21优先调度法则按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件延误时间最小。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。优先调度法则按SPT法则可使工件的平均流程时间最短，从而减少22第二节流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致。加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。第二节流水作业排序问题流水作业排序问题的基本特征是每个工件23一、最长流程时间Fmax的计算n/m/P/Fmax问题，n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。一、最长流程时间Fmax的计算n/m/P/Fmax问题，n个24例有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。i123456423142456745587555424331例有一个6/4/P/Fmax问题，其加工时间如下表所示。当25ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846ipi1pi2pi3pi46152432551445444526二、两台机器排序问题两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤：（1）列出每个作业在两台机器上的加工时间。（2）选择最短的加工时间，如果有两个相同的值，则任选一个。（3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。二、两台机器排序问题两个或更多的作业必须在两台机器上以相同的27【例】求如表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474.5将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143【例】求如表所示的6/2/F/Fmax问题的最优解。i12328【例题】有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间：（1）根据Johnson算法安排工作顺序；（2）计算加工周期。任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5【例题】有5件任务都需要两步操作（先1后2）来完成，下表29任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2任务操作1所需时间（小时）操作2所需时间（小时）A3.01.30A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2iCBDEA操作1操作2A,3.0E,3.5D,3B,2C,11.03.06.09.31【例题】根据Johnson算法求以下8/2/F/Fmax问题的最优解。任务aibiA96B72C103D81EFGH21545874【例题】根据Johnson算法求以下8/2/F/Fmax321.将所有ai≤

bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。改进算法1.将所有ai≤bi的工件按ai值不减的顺序排成一个序33工件号123456ai518534bi722474工件最优顺序：256143

1345582747424

8

13

18

2631115222628aibi最优顺序下的加工周期为28工件号12334练习某公司要生产4种产品，需要两台机器1和2。其中，有3种产品需要先在机器1上加工。下表给出了两台机器上加工各产品所需的时间。（1）安排生产顺序，使得在最短时间内完成生产。（2）机器1共需工作多长时间？（3）机器2应该在机器1开始工作后多长时间开始运转？任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.10练习某公司要生产4种产品，需要两台机器1和2。其中，有335任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.109.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65机器1机器2任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小36三、一般n/m/P/Fmax问题的启发式算法启发式算法是一个基于直观或经验构造的算法，在可接受的花费(时间、占用空间等)下给出待解决组合优化问题的可行解。启发式方法因其易于实现、计算复杂度低等原因，目前应用得最为广泛。三、一般n/m/P/Fmax问题的启发式算法启发式算法是一个37（一）Palmer法1965年，D．S．Palmer提出按斜度指标排列工件的启发式算法，称之为Palmer法。工件的斜度指标可按下式计算：k=l，2，…，m式中，m为机器数；pik为工件i在Mk上的加工时间。按照各工件λi不增的顺序排列工件，可得出令人满意的顺序。（一）Palmer法1965年，D．S．Palmer提出按斜38生产运作管理制造业作业计划与控制课件39例有一个4/3/F/Fmax问题，其加工时间如下表所示，试用帕尔默法求最优顺序。i1234Pi11263Pi28429Pi34582解：对于本例，λi=－Pi1＋Pi3于是，λ1=－P11＋P13=－1＋4=3λ2=－P21＋P23=－2＋5=3λ3=－P31＋P33=－6＋8=2λ4=－P41＋P43=－3＋2=－1按λi不增的顺序排列工件，得到加工顺序(1，2，3，4)和(2，1，3，4)，恰好这两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下，Fmax=28。例有一个4/3/F/Fmax问题，其加工时间如下表所示，试40（二）关键零件法步骤如下：（1）计算每个零件的总加工时间，找出加工时间最长的零件C，将其作为关键零件。（2）对于余下的零件，若pi1≤pim，则按pi1不减的顺序排成一个序列Sa；若pi1≥pim，则按pim不增的顺序排成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。（二）关键零件法步骤如下：41i1234pi11263pi28429pi34582pi13111614例有一个4/3/F/Fmax问题，其加工时间如下表所示，试用关键零件法求最优顺序。解：总加工时间最长的为3号零件，pi1≤pi3的零件为1和2，按pi1不减的顺序排成Sa=（1，2）；pi1≥pi3的零件为4号零件，Sb=（4）,这样得到的加工顺序为（1，2，3，4）。i1234pi11263pi28429pi34582pi1342例题用关键工件法求解下表的最优排序。解：总加工时间最长的为2号零件，pi1≤pi4的零件为1和3，按pi1不减的顺序排成sa=（1，4）；pi1＞pi4的零件为4号零件，sb=（3），这样得到的顺序为（1，4，2，3）。i1234pi11954pi25763pi34635pi46237i1234pi11954pi25763pi34635pi46237pi16241719例题用关键工件法求解下表的最优排序。i1234pi11943（三）CDS法康坎贝尔-杜德克-史密斯三人提出了一个启发式算法，简称CDS法。具体做法是，对加工时间用Johnson算法求（m-1）次加工顺序，取其中最好的结果。（三）CDS法康坎贝尔-杜德克-史密斯三人提出了一个启发式算44m=2时，l=1,加工时间分别为pi1和pi2；m=3时，l=1,2,加工时间分别为：（1）l=1，pi1和pi3（2）l=2,pi1+pi2和pi2+pi3m=4时，l=1，2，3，加工时间分别为：（1）l=1,pi1和pi4（2）l=2，pi1+pi2和pi3+pi4（3）l=3，pi1+pi2+pi3和pi2+pi3+pi4m=2时，l=1,加工时间分别为pi1和pi2；45lA加工时间B加工时间1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tm……………m-1t1+t2+…+tm-1t2+…+tm-1+tmlA加工时间B加工时间1t1tm2t1+t2tm-1+tm346i1234Pi11263Pi28429Pi34582i1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi31291011i1234Pi11263Pi28429Pi34582i12347i1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi31291011当l=1时，按（Johnson）算法得到加工顺序（1，2，3，4）；当l=2时，得到加工顺序（2，3，1，4）。对于（2，3，1，4），相应的Fmax=29。所以，取顺序（1，2，3，4）。i1234l=1pi11263pi34582l=2pi1+p48用Palmer法、关键工件法和CDS法求以下4/4/P/Fmax问题的最优解，并比较三种方法的结果。i1234pi11954pi25763pi34635pi46237用Palmer法、关键工件法和CDS法求以下4/4/P/Fm49四、相同零件、不同移动方式下加工周期的计算排序问题针对的是不同零件，如果n个零件相同，则没有排序问题。但零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。三种典型的移动方式顺序移动方式(串行工程)平行移动方式（平行工程）平行顺序移动方式四、相同零件、不同移动方式下加工周期的计算排序问题针对的是不50（一）顺序移动方式加工周期时间工序1234顺序移动方式一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。（一）顺序移动方式加工周期时间工序1234顺序移动方51设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为ti（分钟/件），i=1.2…n。则该批零件的加工周期为：

已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T顺=4×（10+5+15+10）=160分钟设零件批量为n（件），工序数目为m，一批零件不计算工序52（二）平行移动方式工序1234时间加工周期每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。（二）平行移动方式工序1234时间加工周期53零件平行移动的加工周期为：已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平=（10+5+15+10）+（4-1）×15=85分钟零件平行移动的加工周期为：已知n=4，t1=10分54（三）平行顺序移动方式既要求每道工序连续进行加工，又要求各道工序尽可能平行地加工。时间工序1234加工周期（1）当ti<ti+1时，零件按平行移动方式转移；（2）当ti≥ti+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）×ti+1作为零件在（i+1）工序的开始时间。（三）平行顺序移动方式既要求每道工序连续进行加工，又要求各道55具体做法（1）当ti<ti+1时，零件按平行移动方式转移；（2）当ti≥ti+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）×ti+1作为零件在（i+1）工序的开始时间。具体做法（1）当ti<ti+1时，零件按平行移动方式转移；56平行顺序移动加工周期计算已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平顺=4×（10+5+15+10）-（4-1）×（5+5+10）=100分钟平行顺序移动加工周期计算已知n=4，t1=10分钟，t2=557[例]已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟。求三种移动方式下的加工周期。解：T顺=4×（10+5+15+10）=160分钟T平=（10+5+15+10）+（4-1）×15=85分钟T平顺=4×（10+5+15+10）-（4-1）×（5+5+10）=100分钟[例]已知n=4，t1=10分钟，t2=5分钟，t3=15分58比较项目平行移动平行顺序移动顺序移动生产周期短中长运输次数多中少设备利用差好好组织管理中复杂简单零件三种移动方式的比较比较项目平行移动平行顺序移动顺序移动生产周期短中长运输次数多59已知m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分别求在顺序移动、平行移动和平行顺序移动方式下，这批零件的加工周期。已知m=5,n=4,t1=10,t2=4,t3=8,t4=160第三节单件作业排序问题11.3.1指派问题11.3.2单件作业排序问题的描述11.3.3两种作业计划的构成11.3.4求解一般n/m/G/Fmax问题的启发式方法第三节单件作业排序问题11.3.1指派问题611、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务

每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小11.3.1指派问题1、指派问题的形式表述2、指派问题的假设11.3.1指派问62设n个人被分配去做n件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i个人去做第j件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？3、指派问题模型（TheModelforAssignmentProblem）设n个人被分配去做n件工作，每人只能完成一项任务，每项任63典型问题例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。

典型问题例1：有一份说明书，要分别译成英、日、德、俄四种文64问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139问：如何分配，能使所需的总时间最少？甲乙65建立模型设xij=10若第i项工作交与第j个人完成若第i项工作不交与第j个人完成译英文：x11+x12+x13+x14=1译日文：x21+x22+x23+x24=1译德文：x31+x32+x33+x34=1译俄文：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1丁：x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139建立模型设xij=10若第i项工作交与第j个人完成若第i项664、指派问题的匈牙利解法4、指派问题的匈牙利解法672497第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。422497第1步：变换指派问题的系数矩阵（cij），使各行各列68

在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。第2步：进行试指派，即确定独立零元素（1）从有唯一的零元素的行或列开始确定独立零元素，并用表示，并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划掉为止。0（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入下一步。

在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独69生产运作管理制造业作业计划与控制课件70例2有甲、乙、丙、丁四个工人，要分别派他们完成四项不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982例2有甲、乙、丙、丁四个工人，要分别派他们完成四项不同的71第1步，变换系数矩阵：-5第2步，确定独立零元素找到3个独立零元素，但m=3<n=4求解过程如下第3步，作最少的直线覆盖所有零元素：(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有零元素的最少直线数(1)对没有独立零元素的行打√号；√(2)对已打√号的行中所有含划掉零元素的列打√号；√(3)再对打有√号的列中含独立零元素的行打√号；(4)重复(2)，(3)直到得不出新的打√号的行、列为止；√第1步，变换系数矩阵：-5第2步，确定独立零元素找到372第4步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行（或列）都减去这最小元素；在出现负数的列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第2步。

第4步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在73-5√√√-5√√√7411.3.2问题的描述加工描述矩阵D为D=1,1,11,2,31,3,22,1,32,2,12,3,2对于一般单件作业排序问题，每个工件都有其独特的加工路线，工件没有一定的流向。要描述一道工序，需要用三个参数：3个参数：i，j和k。i表示工件代号，j表示工序号，k表示完成工序i的第j道工序的机器代号。（i，j，k）表示工件i的第j道工序在机器k上进行。11.3.2问题的描述加工描述矩阵D为D=1,1,17511.3.3两种作业计划的构成各工序都按最早可能完工时间安排的作业计划称为能动作业计划。各工序都按最早可能开始时间安排的作业计划称为无延迟作业计划。无延迟作业计划是没有任何延迟出现的能动作业计划。11.3.3两种作业计划的构成各工序都按最早可能完工时间安76符号说明每安排一道工序称为一“步”{St}:t步之前已排序工序构成的部分作业计划；{Ot}:t步可排序工序的集合；Tk为{Ot}中工序Ok的最早可能开始时间；T’k为{Ot}中工序Ok的最早可能完成时间。符号说明77（一）能动作业计划的构成步骤（1）设t=1,{S1}为空集，{O1}为各工件第一道工序的集合。（2）求T*=min{T’k},并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从{Ot}中选出满足以下两个条件的工序Oj：需要M*加工，且Tj<T*。（4）将选定的工序Oj放入{St},从{Ot}中消去Oj,并将Oj的紧后工序放入{Ot}，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。（一）能动作业计划的构成步骤（1）设t=1,{S1}为空集，78例有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345试构成一个能动作业计划。例有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时79能动作业计划的构成2,3,2M2131382,3,261,3,2M28812771,3,22,3,252,2,1M1787731,3,22,2,141,2,3M3777331,2,32,2,132,1,3M3363201,2,32,1,321,1,1M1223001,1,12,1,31OjM*T*T`kTk{Ot}t能动作业计划的构成2,3,2M2131382,3,261,380能动作业计划的甘特图2,3,21,1,12,2,11,3,22,1,31,2,33778132370时间机器M1M2M3能动作业计划的甘特图2,3,21,1,12,81（二）无延迟作业计划构成步骤（1）设t=1,{S1}为空集，{O1}为各工件第一道工序的集合。（2）求T*=min{Tk},并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从{Ot}中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T*。（4）将选定的工序Oj放入{St},从{Ot}中消去Oj,并将Oj的紧后工序放入{Ot}，使t=t+1。（5）若还有未安排的工序，转步骤（2）；否则，停止。（二）无延迟作业计划构成步骤（1）设t=1,{S1}为空集，82无延迟作业计划的构成1,3,2M21213121,3,262,3,2M2M277812771,3,22,3,252,2,1M1387731,3,22,2,141,2,3M3M13377331,2,32,2,132,1,3M3063201,2,32,1,321,1,1M1M30023001,1,12,1,31OjM*T*T`kTk{Ot}t无延迟作业计划的构成1,3,2M21213121,3,26M83无延迟作业计划的甘特图2,3,21,1,12,2,12,1,31,2,337712132370时间机器M1M2M31,3,2无延迟作业计划的甘特图2,3,21,1,1284能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般85练习1.南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交易所提供全部客户服务的合同。取得合同的主要要求是快速交货。爱得说，如果南希厂可以在24小时内将爱得收到的5辆车全部整修并且重新喷漆，合同就归该厂。下面是这5辆车在整修和喷漆车间各自需要的时间。假定车子在重新喷漆前要经过重新整修的步骤，南希厂可以满足时间要求并且得到合同吗？汽车整修时间（小时）重新喷漆时间（小时）A63B04C52D86E21练习1.南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交862.有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：试构成一个能动作业计划和无延迟作业计划。D=1,1,11,2,31,3,22,1,32,2,22,3,1T=3522432.有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时874，1，2M20604，1，20403，1，11182，2，11251，2，230604，1，20403，1，11182，2，11，1，1M10501，1，120604，1，20403，1，12，1，3M30802，1，30501，1，11OjM*T*T’kTk{Ot}t4，1，2M20604，1，20403，1，11182，2，881694，3，11393，2，41292，2，11，2，2M261361，2，264，2，4M46864，2，41393，2，41292，2，161361，2，25864，2，43，1，1M15953，1，11182，2，11361，2，24OjM*T*T’kTk{Ot}t1694，3，11393，2，41292，2，11，2，2M894，3，1M11219124，3，118133，3，317132，3，419131，3，3919124，3，13，2，4M491393，2，416122，3，419131，3，3891694，3，191393，2，42，2，1M191292，2，119131，3，37OjM*T*T’kTk{Ot}t4，3，1M11219124，3，118133，3，31719022194，4，31819183，4，21827182，4，31，3，3M31824181，3，31222194，4，33，3，3M31318133，3，326172，4，31319131，3，31122194，4，31318133，3，32，3，4M41317132，3，41319131，3，310OjM*T*T’kTk{Ot}t22194，4，31819183，4，21827182，4，912，4，3M32736272，4，34，4，3M32427244，4，32433242，4，32427244，4，32433242，4，31，4，4M42426241，4，41427244，4，33，4，2M21819183，4，233242，4，326241，4，413OjM*T*T’kTk{Ot}t15162，4，3M32736272，4，34，4，3M3242729211.3.3求解一般n/m/G/Fmax问题的启发式方法三类启发式算法：优先调度法则随机抽样法概率调度法11.3.3求解一般n/m/G/Fmax问题的启发式方法三931.优先调度法则SPT（Shortestprocessingtime）法则优先选择加工时间最短的工序可使工件的平均流程时间最短，从而减少在制品量FCFS（Firstcomefirstserved）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平EDD（Earliestduedate）法则优先选择完工期限紧的工件可使工件最大延误时间最小MWKR（Mostworkremaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近1.优先调度法则SPT（Shortestprocessin941.优先调度法则（续）LWKR（Leastworkremaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成MOPNR（Mostoperationsremaining）法则优先选择余下工序数最多的工件与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的SCR（Smallestcriticalratio）法则优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）保证工件延误最少RANDOM法则随机地挑一个工件1.优先调度法则（续）LWKR（Leastworkrem95生产运作管理制造业作业计划与控制课件962.随机抽样法随机抽样法•实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划•这种方法不一定能得到最优作业计划，但可以得到较满意的作业计划效果与样本大小有关。样本越大，获取较好解的可能性越大从无延迟作业计划母体中抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好2.随机抽样法随机抽样法973.概率调度法给不同的工序按某一优先调度法则分配不同的挑选概率，可以得到多个作业计划供比较。例如，在构成无延迟作业计划的第（3）步•有3道工序，A、B和C可挑选•3道工序所需的时间分别为3，4和7•将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率比如A、B和C的挑选概率分别为6/14、5/14和3/14既保证了SPT法则起作用，又可产生多个作业计划供挑选3.概率调度法给不同的工序按某一优先调度法则分配不同的挑选98生产作业控制是指在生产过程中，按既定的政策、目标、计划和标准，通过监督和检查生产活动的进展情况、实际成效，及时发现偏差，找出原因，采取措施，以保证目标、计划的实现。生产运作控制的受控客体是生产运作过程，其预定目标是主生产计划与生产作业计划的目标值。§11.4生产作业控制生产作业控制是指在生产过程中，按既定的政策、目标、计划和99一、生产活动与作业计划产生偏差的原因（1）加工时间估计不准确（2）随机因素的影响（3）加工路线的多样性（4）企业环境的动态性§11.4生产作业控制一、生产活动与作业计划产生偏差的原因§11.4生产作业控制100二、生产作业控制的程序制定生产作业监控体系监控实际生产过程评估偏差情况采取纠偏措施§11.4生产作业控制二、生产作业控制的程序§11.4生产作业控制101三、生产作业控制的主要工具实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：调度单日报、月报例外报告、异常报告输入/输出（I/O）报告三、生产作业控制的主要工具实际生产中，有不少工具可以用来进102日常调度单它告诉主管哪些工件要被加工，这些工件的优先级以及加工时间。开始日期工件号描述运行时间201203205205207208151311514315145157121534015312轴铆钉锭子锭子测量杆轴11.420.64.38.66.54.6日常调度单它告诉主管哪些工件要被加工，这些工件的优先级以及加103各种状态和异常报告1、预计延期报告2、废品报告3、返工报告4、作业总结报告部件号计划日期新日期延期原因措施1712513044176534/104/114/114/155/15/14夹具损坏送去镀金，镀金工罢工新孔未成直线工具室返还4/15新批量开始生产工程部重新安装钻模各种状态和异常报告1、预计延期报告部件号计划日期新日期延期原104漏斗模型德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（FunnelModel）。漏斗模型德国汉诺威大学的Bechte和Wiendall等人于105漏斗模型漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。

漏斗模型106注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔。注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达107控制规则在一段较长的时间内(如数周)内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率(平均生产率)等于平均在制品库存/平均通过时间。实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：若希望保持在制品库存量稳定，就要使单位时间内的平均输入等于平均输出。若希望改变在制品库存量，可暂时增加或减少输入。若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。控制规则在一段较长的时间内(如数周)内，若工况稳定，输入输出108第十一章制造业作业计划与控制引言通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。

第十一章制造业作业计划与控制引言10911.1作业计划问题的基本概念11.2流水作业排序问题11.3单件作业的排序问题11.4生产作业控制

11.1作业计划问题的基本概念11011收入、费用和利润要求掌握：最长流程时间的计算2.约翰逊算法3.一般流水作业排序问题的3种启发式算法4.相同零件的3种移动方式下机器加工周期的计算方法学习目的与要求11收入、费用和利润要求掌握：学习目的与要求111

重点最长流程时间的计算约翰逊算法相同零件的3种移动方式下机器加工周期的计算方法

难点一般流水作业排序问题的启发式算法教学重点与难点重点教学重点与难点112生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。将任务安排到工作地，牵涉到作业计划。生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全113编制作业计划要解决的问题由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间例如;医院要安排病人手术，为此要安排手术室，配备手术器械、手术医师和护士。编制作业计划要解决的问题由于每台机器都可能被分配了多项任务，114第一节排序问题的基本概念一、名词术语排序：确定工件在机器上的加工顺序。作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。赶工：实际进度已落后于计划进度时采取的行动。第一节排序问题的基本概念一、名词术语115“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服116二、假设条件和符号说明假设条件：1.一个工件不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。4.每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件二、假设条件和符号说明假设条件：117有关符号Ji：工件i，i=1，2，…，nMj：机器j，j=1，2，…，npij为Ji在Mj上的加工时间ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最早时间di为Ji的完工期限Ci为Ji的完工时间Cmax为最长完工时间Fi为Ji的流程时间，即工件在车间的实际停留时间Fmax为最长流程时间Li为工件的延迟时间Lmax为最长延迟时间有关符号Ji：工件i，i=1，2，…，n118三、排序问题的分类根据机器数的多少单台机器的排序问题多台机器的排序问题对于多台机器排序问题，根据加工路线的特征，分成单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。三、排序问题的分类根据机器数的多少119根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序根据工件到达系统的情况1204参数法n/m/A/B其中，n为工件数m为机器数A车间类型。在A的位置若标以标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。当m=1，则A处为空白。B为目标函数，通常是使其值最小例如：n/3/P/Cmax4参数法n/m/A/B121四、作业排序方案的评价标准1.工作流程时间从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。2.加工周期完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。四、作业排序方案的评价标准1.工作流程时间1223.在制品库存（WIP）在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。4.利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。3.在制品库存（WIP）123五、优先调度规则调度方法：所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。五、优先调度规则调度方法：124常用的优先顺序规则：FCFS规则优先选择最早进入可排序集合的工件。EDD规则优先选择完工期限最紧的工作。SPT规则优先选择加工时间最短的工件。SCR规则优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。MWKR规则优先选择余下加工时间最长的工件。LWKR规则优先选择余下加工时间最短的工件。MOPNR规则优先选择余下工序数最多的工件。RANDOM规则随机地挑选下一个工件。常用的优先顺序规则：FCFS规则优先选择最早进入可排序集合125一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化一般作业排序的目标126[例]一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。发动机机壳所需标准加工时间（包括机器调整）预计顾客取货时间（从现在开始算起的所需工作时间）机壳1810机壳2612机壳31520机壳4318机壳51222[例]一个加工车间负责加工发动机机壳，现在共有5个机壳等待127机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存=102/44=2.32个平均总库存=120/44=2.73个SPT规则排序结果顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和÷加工周期平均总库存=各工件实际取货时间之和÷加工周期机壳加工次序开始加工结束流程预计顾客顾客实际取货时间提前拖延128机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数23.00.67.2平均在制品库存=115/44=2.61个平均总库存=118/44=2.68个EDD规则排序结果顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。机壳加工次序开始加工结束流程预计顾客顾客实际取货时间提前拖延129优先调度法则按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件延误时间最小。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。优先调度法则按SPT法则可使工件的平均流程时间最短，从而减少130第二节流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致。加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。第二节流水作业排序问题流水作业排序问题的基本特征是每个工件131一、最长流程时间Fmax的计算n/m/P/Fmax问题，n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。一、最长流程时间Fmax的计算n/m/P/Fmax问题，n个132例有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。i123456423142456745587555424331例有一个6/4/P/Fmax问题，其加工时间如下表所示。当133ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846ipi1pi2pi3pi461524325514454445134二、两台机器排序问题两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤：（1）列出每个作业在两台机器上的加工时间。（2）选择最短的加工时间，如果有两个相同的值，则任选一个。（3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。二、两台机器排序问题两个或更多的作业必须在两台机器上以相同的135【例】求如表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474.5将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143【例】求如表所示的6/2/F/Fmax问题的最优解。i123136【例题】有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间：（1）根据Johnson算法安排工作顺序；（2）计算加工周期。任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5【例题】有5件任务都需要两步操作（先1后2）来完成，下表137任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2任务操作1所需时间（小时）操作2所需时间（小时）A3.01.138A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2iCBDEA操作1操作2A,3.0E,3.5D,3B,2C,11.03.06.09.139【例题】根据Johnson算法求以下8/2/F/Fmax问题的最优解。任务aibiA96B72C103D81EFGH21545874【例题】根据Johnson算法求以下8/2/F/Fmax1401.将所有ai≤

bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。改进算法1.将所有ai≤bi的工件按ai值不减的顺序排成一个序141工件号123456ai51