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

1、第十一章 制造业作业计划与控制 引言 通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。 11.1 作业计划问题的基本概念 11.2 流水作业排序问题 11.3 单件作业的排序问题 11.4 生产作业控制 11 收入、费用和利润收入、费用和利润要求掌握： 最长流程时间的计算 2.约翰逊算法 3.一般流水作业排序问题的3种启发式算法4. 相同零件的3种移动方式下机器加工周期的

2、计算方法学习目的与要求 重点 最长流程时间的计算 约翰逊算法 相同零件的3种移动方式下机器加工周期的计算方法 难点 一般流水作业排序问题的启发式算法教学重点与难点生产任务的最终落实 MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。 各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。 将任务安排到工作地，牵涉到作业计划。编制作业计划要解决的问题 由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。 编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题 确定机器加工每个工件的开始时间和完成时间 例如;医院要安排病人手

3、术，为此要安排手术室，配备手术器械、手术医师和护士。第一节 排序问题的基本概念 一、名词术语 排序：确定工件在机器上的加工顺序。 作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。 派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。 赶工：实际进度已落后于计划进度时采取的行动。 “机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者” “零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件 “加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问

4、题二、假设条件和符号说明 假设条件： 1.一个工件不能同时在几台不同的机器上加工。 2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。 3.不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。 4.每道工序只在一台机器上完成。 5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。 6.每台机器同时只能加工一个工件有关符号 Ji：工件i，i=1，2，n Mj：机器j，j=1，2，n pij为Ji在Mj上的加工时间 ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最早时间 di为Ji的完工期限 Ci为Ji的完工时间 Cmax为最

5、长完工时间 Fi为Ji的流程时间，即工件在车间的实际停留时间 Fmax为最长流程时间 Li为工件的延迟时间 Lmax为最长延迟时间三、排序问题的分类 根据机器数的多少单台机器的排序问题多台机器的排序问题 对于多台机器排序问题，根据加工路线的特征，分成单件作业排序(Job - Shop)问题流水作业排序(Flow - Shop)问题 工件的加工路线不同，是单件作业排序问题的基本特征； 所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。 根据工件到达系统的情况静态排序动态排序 根据参数的性质确定型排序随机型排序4参数法 n

6、/m/A/B 其中，n为工件数 m为机器数 A车间类型。在A的位置若标以标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。当m=1，则A处为空白。 B为目标函数，通常是使其值最小 例如：n/3/P/Cmax四、作业排序方案的评价标准 1.工作流程时间 从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。 2. 加工周期 完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。 3.在制品库存（WIP） 在制品是

7、对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。 4.利用率 用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。五、优先调度规则 调度方法： 所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。 一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。常用的优先顺序规则： FCFS规则 优先选择最早进入可排序集合的工件。 EDD规则 优先选择完工期限最紧的工作。 SPT规则 优先选择加工时间最短的工

8、件。 SCR规则 优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。 MWKR规则 优先选择余下加工时间最长的工件。 LWKR规则 优先选择余下加工时间最短的工件。 MOPNR规则 优先选择余下工序数最多的工件。 RANDOM规则 随机地挑选下一个工件。一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化 例 一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情

9、况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。发动机机壳所需标准加工时间（包括机器调整）预计顾客取货时间（从现在开始算起的所需工作时间）机壳1810机壳2612机壳31520机壳4318机壳51222机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存=102/44=2.32个 平均总库存=120/44=2.73个SPT规则排序结果

10、 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和加工周期平均总库存=各工件实际取货时间之和加工周期机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数23.00.67.2平均在制品库存=115/44=2.61个 平均总库存=118/44=2.68个EDD

11、规则排序结果 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。 比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。优先调度法则 按SPT法则可使工件的平均流程时间最短，从而减少在制品量。 FCFS法则来自排队论，它对工件较公平。 EDD法则可使工件延误时间最小。 MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。第二节 流水作业排序问题 流水作业排序问题的基本特征是每

12、个工件的加工路线都一致。 加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。 对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。 排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。一、最长流程时间Fmax的计算 n/m/P/Fmax问题，n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。 最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。 例 有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时

13、，求Fmax。i1234564231424567455875554243311iP2iP3iP4iPipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846二、两台机器排序问题 两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤： （1）列出每个作业在两台机器上的加工时间。 （2）选择最短的加工时间，如果有两个相同的值，则任选一个。 （3）如果最短的加工时间来

14、自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。 （4）对于剩余的作业重复第二步和第三步，直到整个排序完成。 【例】求如表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474.5将零件2排第1位 2将零件3排第6位 2 3将零件5排第2位 2 5 3将零件6排第3位 2 5 6 3将零件4排第5位 2 5 6 4 3将零件1排第4位 2 5 6 1 4 3【例 题】有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间：（1）根据Johnson算法安排工作顺序；（2）计算

15、加工周期。任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5任务操作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操作2A,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操作21

16、16 . 26 . 132635 . 95 . 35 .120 . 35 . 55 . 20 . 90 . 3115 . 17 .132 . 1【例 题】根据Johnson算法求以下8/2/F/Fmax问题的最优解。任务aibiA96B72C103D81EFGH21545874 1. 将所有ai bi的工件按ai值不减的顺序排成一个序列A； 2. 将aibi的工件按bi值不增的顺序排成一个序列B； 3. 将A放到B之前，就构成了一个最优加工顺序。改进算法工件号 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4工件最优顺序：2 5 6 1 4 3 1 3 4 5

17、 5 8 2 7 4 7 4 2 4 8 13 18 263 11 15 22 26 28 ai bi 最优顺序下的加工周期为28练 习 某公司要生产4种产品，需要两台机器1和2。其中，有3种产品需要先在机器1上加工。下表给出了两台机器上加工各产品所需的时间。 （1）安排生产顺序，使得在最短时间内完成生产。 （2）机器1共需工作多长时间？ （3）机器2应该在机器1开始工作后多长时间开始运转？任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.10任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2

18、.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三、一般n/m/P/Fmax问题的启发式算法 启发式算法是一个基于直观或经验构造的算法，在可接受的花费(时间、占用空间等)下给出待解决组合优化问题的可行解 。 启发式方法因其易于实现、计算复杂度低等原因，目前应用得最为广泛。 （一）Palmer法 1965年，DSPalmer提出按斜度指标排列工件的启发式算法，称之为 Palmer法。 工件的斜度指标可按下式计算： k=l，2，m 式中，m为机器数；pik为工件i在Mk上的加工

19、时间。 按照各工件i不增的顺序排列工件，可得出令人满意的顺序。ikmkipmk12/)1(m, 2 , 1k 2/ ) 1(1，mkikipmk31i3miipp时，当43215 . 15 . 05 . 05 . 14miiiiipppp时，当5432121025miiiiiippppp时，当例 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用帕尔默法求最优顺序。i1234Pi11263Pi28429Pi34582解：对于本例， i =Pi1Pi3于是，1 = P11P13=14=3 2 = P21P23=25=3 3 = P31P33=68=2 4 = P41P43=32=1 按i

20、 不增的顺序排列工件，得到加工顺序(1，2，3，4)和(2，1，3，4)，恰好这两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下， F max =28。321k2/)13(1，ikmkipk（二）关键零件法 步骤如下： （1）计算每个零件的总加工时间，找出加工时间最长的零件C，将其作为关键零件。 （2）对于余下的零件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排成一个序列Sb。 （3）顺序（Sa，C，Sb）即为所求顺序。i1234pi11263pi28429pi34582pi13111614例 有一个4/3/F/Fmax问题，其加

21、工时间如下表所示，试用关键零件法求最优顺序。解：总加工时间最长的为3号零件， pi1pi3的零件为1和2，按pi1不减的顺序排成Sa=（1，2）； pi1pi3的零件为4号零件，Sb=（4）,这样得到的加工顺序为（1，2，3，4）。例 题 用关键工件法求解下表的最优排序。 解：总加工时间最长的为2号零件，pi1pi4的零件为1和3，按pi1不减的顺序排成sa=（1，4）；pi1pi4的零件为4号零件，sb=（3），这样得到的顺序为（1，4，2，3）。i1234pi11954pi25763pi34635pi46237i1234pi11954pi25763pi34635pi46237pi16241

22、719（三）CDS法 康坎贝尔-杜德克-史密斯三人提出了一个启发式算法，简称CDS法。 具体做法是，对加工时间 用Johnson算法求（m-1）次加工顺序，取其中最好的结果。，和1m21pml - 1mkik1lplkik。，和1m21pml - 1mkik1lplkikm=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+p

23、i4lA 加工时间 B 加工时间1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tmi1234Pi11263Pi28429Pi34582 2)1(pml - 1mkik1，和lplkiki1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi31291011i1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi31291011当l=1时，按（Johnson）算法得到加工顺序（1，2，3，4）；当l=2时，得到加工顺序（2，3，1，4）。对于（2，3，1，4），相

24、应的Fmax=29。所以，取顺序（1，2，3，4）。用Palmer法、关键工件法和CDS法求以下4/4/P/Fmax问题的最优解，并比较三种方法的结果。i1234pi11954pi25763pi34635pi46237四、相同零件、不同移动方式下加工周期的计算 排序问题针对的是不同零件，如果n个零件相同，则没有排序问题。但零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。 三种典型的移动方式顺序移动方式(串行工程)平行移动方式（平行工程）平行顺序移动方式（一）顺序移动方式分钟52t分钟153t加工周期时间工序 1 2 3 4顺序移动方式顺序移动方式 一批零件在上道工序全部加工完

25、毕后才整批地转移到下道工序继续加工。分钟101t分钟104t 设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 ti （分钟/件），i=1.2n。 则该批零件的加工周期为： 121.mimiTntntntnt 已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T顺=4（10+5+15+10）=160分钟（二）平行移动方式分钟101t分钟52t分钟153t工序 1 2 34时间 加工周期 每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。分钟104t零

26、件平行移动的加工周期 为：T平。为最长的单件工序时间式中，平LLitt ) 1n(tT已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平=（10+5+15+10）+（4-1）15=85分钟（三）平行顺序移动方式 既要求每道工序连续进行加工，又要求各道工序尽可能平行地加工。 时间工序1234 加工 周期（1）当titi+1时，零件按平行移动方式转移；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。分钟104t分钟101t分钟52t分钟153t具体做法 （1）当titi+1时，零件按平行移动方

27、式转移； （2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。平行顺序移动加工周期计算已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平顺=4（10+5+15+10）-（4-1）（5+5+10）=100分钟)tt (min)1n(tn1j1m1jjm1ii，平顺T 例已知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+

28、5+15+10）-（4-1）（5+5+10）=100分钟比较项目平行移动平行顺序移动 顺序移动生产周期短中长运输次数多中少设备利用差好好组织管理中复杂简单零件三种移动方式的比较 已知m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分别求在顺序移动、平行移动和平行顺序移动方式下，这批零件的加工周期。第三节 单件作业排序问题 11.3.1 指派问题 11.3.2 单件作业排序问题的描述 11.3.3 两种作业计划的构成 11.3.4 求解一般n/m/G/Fmax问题的启发式方法 1 1、指派问题的形式表述、指派问题的形式表述 给定了一系列所要完成的任务（给定了一系列所要完成的

29、任务（taskstasks）以）以及一系列完成任务的被指派者及一系列完成任务的被指派者（assigneesassignees），所需要解决的问题就是要），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务确定出哪一个人被指派进行哪一项任务 2 2、指派问题的假设、指派问题的假设被指派者的数量和任务的数量是被指派者的数量和任务的数量是相同的相同的每一个被指派者只完成每一个被指派者只完成一项任务一项任务 每一项任务只能由每一项任务只能由一一个被指派者个被指派者来完成来完成 每个被指派者和每项任务的组合有一个相关成本每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总

30、成本最小目标是要确定怎样进行指派才能使得总成本最小 11.3.1 指派问题设设n n 个人被分配去做个人被分配去做n n 件工作，每人只能完成一项任件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第务，每项任务只能由一人完成。已知第i i 个人去做第个人去做第j j 件工件工作的的效率为作的的效率为C Cijij( (i i=1.2=1.2n n; ;j j=1.2=1.2n n) )并假设并假设C Cijij 0 0。问应。问应如何分配才能使总效率（如何分配才能使总效率（ 时间或费用）最高？时间或费用）最高？).2.1,1(0).2.1( 1).2.1( 1min1111njixn

31、jxnixxcZijniijnjijninjijij 或3、指派问题模型、指派问题模型（The Model for Assignment Problem）项任务个人取完成第不分配第项任务个人取完成第分配第ji0ji1ijx典型问题典型问题 例例1 1：有一份说明书，要分别译成英、日、：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，规定每项工作只能

32、交与其中的一个人完成，每个人只能完成其中的一项工作。每个人只能完成其中的一项工作。 问：如何分配，能使所需的总时间最少？问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 建立模型设设 xij=10若第若第i项工作交与第项工作交与第j个人完成个人完成若第若第i项工作不交与第项工作不交与第j个人完成个人完成 4141minijijijxcf译英文：译英文：x11+ x12 + x13 + x14 =1译日文：译日文：x21+ x22 + x23 + x24 =1译德文：译德文：x31+ x32

33、 + 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)甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 4、指派问题的匈牙利解法、指派问题的匈牙利解法 9118713161491514410413152 2410

34、47501110062111302497第第1 1步：变换指派问题的系数矩阵（步：变换指派问题的系数矩阵（c cijij），使各行），使各行各列中都出现各列中都出现0 0元素元素(1) (1) 从（从（c cijij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。再从所得新系数矩阵无零元素的列中减去该列的最小元素。42 00102350960607130在变化后的效率矩阵中找尽可能多的独立在变化后的效率矩阵中找尽可能多的独立0 0元素，若元素，若能找出能找出n n个独立个独立0 0元素，就以这元素，就以这n n

35、个独立个独立0 0元素对应解元素对应解矩阵矩阵( (x xijij) )中的元素为中的元素为1 1，其余为，其余为0 0，这就得到最优解。，这就得到最优解。第第2 2步：进行试指派，即确定独立零元素步：进行试指派，即确定独立零元素（1 1）从有唯一的零元素的行或）从有唯一的零元素的行或列开始确定独立零元素，并用列开始确定独立零元素，并用 表示，并划掉其所在行或列的表示，并划掉其所在行或列的其他零。直到尽可能多的零元其他零。直到尽可能多的零元素都被圈出和划掉为止。素都被圈出和划掉为止。0 0（2 2）若）若独立零元素独立零元素的数目的数目m m等等于矩阵的阶数于矩阵的阶数n n，那么这指派，那么

36、这指派问题的最优解已得到。若问题的最优解已得到。若m m n n, , 则转入下一步。则转入下一步。0100000100101000ijx 9118713161491514410413152 00102350960607130例例2 2 有有甲、乙、丙、丁甲、乙、丙、丁四个工人，要分别派他们完四个工人，要分别派他们完成四项不同的任务，分别记作成四项不同的任务，分别记作A A、B B、C C、D D。他们完成各项。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间任务所需时间如下表所示，问如何分派任务，可使总时间最少？最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31

37、104丁丁5982第第1 1步，变换系数矩阵：步，变换系数矩阵：2142 289541013895421176)( ijc 0673390245100954 0173340240100454-5第第2 2步，确定独立零元素步，确定独立零元素 找到找到 3 个独立零元素，个独立零元素， 但但 m = 3 n = 4求解过程如下求解过程如下 第第3 3步，作最少的直线覆盖所有零元素：步，作最少的直线覆盖所有零元素： (5)(5)对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就号的列画纵线，这就得到覆盖所有零元素的最少直线数得到覆盖所有零元素的最少直线数(1)(1)对没有独立零

38、元素的行打对没有独立零元素的行打号；号；(2)(2)对已打对已打号的行中所有含划掉零元素的列打号的行中所有含划掉零元素的列打号；号；(3)(3)再对打有再对打有号的列中含独立零元素的行打号的列中含独立零元素的行打号；号；(4)(4)重复重复(2)(2)，(3)(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；第第4 4步：在没有被直线覆盖的所有元素中找出最小元素，步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行然后将所在行（或列）（或列）都减去这最小元素；都减去这最小元素； 017334024010045410623402401013430062440250100

39、343在出现负数的列在出现负数的列（或行）（或行）都加上这最小元素（以保证都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第原问题仍相同。转回第2 2步。步。 2142 289541013895421176)( ijc 0673390245100954 0173340240100454-5106234024010134300624402501003430100001000011000ijx11.3.2 问题的描述加工描述矩阵D为D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2 对于一般

40、单件作业排序问题，每个工件都有其独特的加工路线，工件没有一定的流向。要描述一道工序，需要用三个参数：3个参数：i，j和k。i表示工件代号，j表示工序号，k表示完成工序i的第j道工序的机器代号。（i，j，k）表示工件i的第j道工序在机器k上进行。11.3.3 两种作业计划的构成 各工序都按最早可能完工时间安排的作业计划称为能动作业计划。 各工序都按最早可能开始时间安排的作业计划称为无延迟作业计划。 无延迟作业计划是没有任何延迟出现的能动作业计划。 符号说明每安排一道工序称为一“步”St:t步之前已排序工序构成的部分作业计划；Ot:t步可排序工序的集合；Tk为Ot中工序Ok的最早可能开始时间；Tk

41、为Ot中工序Ok的最早可能完成时间。（一）能动作业计划的构成步骤 （1）设t=1,S1为空集，O1为各工件第一道工序的集合。 （2）求T* = minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。 （3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj T* 。 （4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot ，使t=t+1. （5）若还有未安排的工序，转步骤（2）；否则，停止。 例 有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4

42、 13 4 5试构成一个能动作业计划。能动作业计划的构成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*TkTkOtt能动作业计划的甘特图2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70时间时间机器 M1M2M3（二）无延迟作业计划构成步骤 （1）设t=1,S1为空集，O1为各工件第一道工序的集合。 （2）求T*

43、= minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。 （3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T* 。 （4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot ，使t=t+1。 （5）若还有未安排的工序，转步骤（2）；否则，停止。无延迟作业计划的构成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,

44、1,31OjM*T*TkTkOtt无延迟作业计划的甘特图2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 13 2 3 70时间时间机器 M1M2M31,3,2 能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。 一般能动作业计划和无延迟作业计划都有多个。 一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。练 习 1.南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交易所提供全部客户服务的合同。取得合同的主要要求是快速交货。爱得说，如果南希厂可以在

45、24小时内将爱得收到的5辆车全部整修并且重新喷漆，合同就归该厂。下面是这5辆车在整修和喷漆车间各自需要的时间。假定车子在重新喷漆前要经过重新整修的步骤，南希厂可以满足时间要求并且得到合同吗？汽车整修时间（小时）重新喷漆时间（小时）A63B04C52D86E21 2.有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为： 试构成一个能动作业计划和无延迟作业计划。D=1,1,1 1,2,3 1,3,22,1,3 2,2,2 2,3,1T=3 5 22 4 34，1，2M20604，1，20403，1，11182，2，11251，2，230604，1，20403，1，11182，2

46、，11，1，1M10501，1，120604，1，20403，1，12，1，3M30802，1，30501，1，11OjM*T*T kTkOtt1694，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 kTkOtt4，3，1M11219124，3，118133，3，317132，3，419131，3，3919124，3，13，2，4M491393，2，416122，3，419131，3，38916

47、94，3，191393，2，42，2，1M191292，2，119131，3，37OjM*T*T kTkOtt22194，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 kTkOtt2，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 kTkOtt151611.3.3 求解一般n/m/G/Fmax问题的启发式方法三类启发式算法：n 优先调度法则n 随机抽样法n 概率调度法1.优先调度法则 SPT（Shortest processing time）法则 优先选择加工时间最短的工序 可使工件的平均流程时间最短，从而减少在制品量 FCFS（First come first served）法则 优先选择最早进入可排工序集