11章作业排序ppt课件.ppt

《11章作业排序ppt课件.ppt》由会员分享，可在线阅读，更多相关《11章作业排序ppt课件.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1111章制造作业计划与控制章制造作业计划与控制第一节第一节 排序问题的基本概念排序问题的基本概念第二节第二节 流水作业排序问题流水作业排序问题第三节第三节 单件作业排序问题单件作业排序问题第四节第四节 生产作业控制生产作业控制第一节第一节 作业计划和排序问题的基本概念作业计划和排序问题的基本概念作业计划与作业作业计划与作业排序排序是一回事么？是一回事么？n n作业计划是安排零部件（作业、活动）的出产数量、作业计划是安排零部件（作业、活动）的出产数量、作业计划是安排零部件（作业、活动）的出产数量、作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。设备及人工使

2、用、投入时间及出产时间。设备及人工使用、投入时间及出产时间。设备及人工使用、投入时间及出产时间。n n排序，给出零部件在一台或一组设备上加工的先后顺排序，给出零部件在一台或一组设备上加工的先后顺排序，给出零部件在一台或一组设备上加工的先后顺排序，给出零部件在一台或一组设备上加工的先后顺序的工作。序的工作。序的工作。序的工作。n n编制作业计划不仅包括确定工件的加工顺序，而且包编制作业计划不仅包括确定工件的加工顺序，而且包编制作业计划不仅包括确定工件的加工顺序，而且包编制作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。因括确定机器加工每个工件的开始时间和完成

3、时间。因括确定机器加工每个工件的开始时间和完成时间。因括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。此，只有作业计划才能指导每个工人的生产活动。此，只有作业计划才能指导每个工人的生产活动。此，只有作业计划才能指导每个工人的生产活动。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用根据排序规则对每一个根据排序规则对每一个到到达的工件安排作业顺序达的工件安排作业顺序工作地工作地工件排工件排队等待队等待加工加工来自上游来自上游工作地的工作地的工件工件加工完毕的加工完毕的工件流

4、向下工件流向下一工作地一工作地排序的概念经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用排序的概念n n生产作业排序就是指对于等候某个设备生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些或工作中心加工的多个任务，确定这些任务加工的先后次序。任务加工的先后次序。n n目的：目的：uu提高设备或工作中心的效率提高设备或工作中心的效率提高设备或工作中心的效率提高设备或工作中心的效率uu减少在制品占用量减少在制品占用量减少在制品占用量减少在制品占用量uu缩短生产周期缩短生产周期缩短生产周期缩短生产周期

5、uu保证按期交货保证按期交货保证按期交货保证按期交货名词术语(略)n n“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件n n“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、钻、冲、磨的路线加工，我们可以用M1,M2,M3,M4来表示。n n“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用排排排排序序序序问问问问题题题题分分分分类类类类按机器按机器按机器按机器单台机器排序问题单台机器排序问题单台机器排序问

6、题单台机器排序问题多台机器排序问题多台机器排序问题多台机器排序问题多台机器排序问题单件作业排序问题单件作业排序问题单件作业排序问题单件作业排序问题流水线作业排序问题流水线作业排序问题流水线作业排序问题流水线作业排序问题按零件到达车间的情况按零件到达车间的情况按零件到达车间的情况按零件到达车间的情况静态的排序问题静态的排序问题静态的排序问题静态的排序问题动态的排序问题动态的排序问题动态的排序问题动态的排序问题按目标函数的性质分类按目标函数的性质分类按目标函数的性质分类按目标函数的性质分类按参数按参数按参数按参数确定型排序问题确定型排序问题确定型排序问题确定型排序问题随机型排序问题随机型排序问题随

7、机型排序问题随机型排序问题排序问题的分类 参数表示法:n nn/m/A/Bn/m/A/B。其中其中,n,n 零件数；零件数；m m 机器数；机器数；A A 作业类型；作业类型；n n在在A A的位置若标以的位置若标以“F”“F”，则代表流水作业排序，则代表流水作业排序问题。问题。n n若标以若标以“P”“P”，则表示流水作业排列排序问题，则表示流水作业排列排序问题,即即同顺序同顺序排序，所有零件在每台机器上的加工排序，所有零件在每台机器上的加工顺序相同。顺序相同。n n若标以若标以“G”“G”，则表示一般单件作业排序问题。，则表示一般单件作业排序问题。当当m m1 1，则，则A A处为空白处为

8、空白 B B目标函数，通常是使其值最小。目标函数，通常是使其值最小。参数表示法:n nn/m/P/Fmax所有零件在每台机器上的加工顺序相同。如在M1上都是第一道工序，M2上都是第二道工序。n nn/m/F/Fmax不同零件在每台机器上的加工顺序不同。如零件1在M1上不加工，在M2上才是第一道工序；而零件2在M1上是第一道工序。第二节 流水作业排序问题n n流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.n n只要加工路线一致：M1，M2,M3，.，Mm,不要求每个零件都经过每台机器加工n n我们要讨论的是排列排序问题。它不是流水线排序问题的最优解，但是比较好的解。一、最

9、长流程时间Fmax的计算n n最长流程时间又称作加工周期最长流程时间又称作加工周期例题：例题：6/4/p/F6/4/p/Fmaxmax问题，当按顺序问题，当按顺序S S(6,1,5,2,4,3)(6,1,5,2,4,3)加工时，求加工时，求F Fmaxmax.表1加工时间矩阵-i 1 2 3 4 5 6 Pi1 4 2 3 1 4 2 Pi2 4 5 6 7 4 5 Pi3 5 8 7 5 5 5 Pi4 4 2 4 3 3 1 n n加工周期为46 表2顺序S下的加工时间矩阵 i 6 1 5 2 4 3 i1P 22 46 410 212 113 316i2P 57 411 415 520

10、727 633 Pi3 512 517 522 830 535 742Pi4 113 421 325 232 338 446 Pi1P一、最长流程时间一、最长流程时间F Fmaxmax的计算的计算 n n加工周期为37 表表3 3顺序顺序S S下的加工时间矩阵下的加工时间矩阵 i 1 2 3 4 5 6 i1P 33 36 410 212 113 316i2P 25 511 415 318 725 631 Pi3 510 415 520 727 532 436 Pi4 111 217 323 229 335 137 Pi1P课堂作业：求课堂作业：求Fmax.二、n/2/F/Fmax问题的最优算

11、法（一）（一）JohnsonJohnson算法：算法：从加工时间矩阵中找出最短的加工时从加工时间矩阵中找出最短的加工时间。间。若最短的加工时间出现在若最短的加工时间出现在M M1 1上，则对上，则对应的零件尽可能往前排；若最短加工时间出现应的零件尽可能往前排；若最短加工时间出现在在M M2 2上，则对应零件尽可能往后排。然后，从上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个若最短加工时间有多个，则任挑一个若所有零件都已排序，停止。否则，若所有零件都已排序，停止。否则，转步骤转步骤。例题：求表例

12、题：求表11-311-3所示的所示的6/2/F/Fmax6/2/F/Fmax问题的最优解。问题的最优解。将零件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 61 4 3最优加工顺序为S=（2，5，6，1，4，3）。最优顺序下的Fmax=28表表11-3加工时间矩阵加工时间矩阵i 1 2 3 4 5 6bi 7 2 2 4 7 4 5 1 8 5 3 4ai 课堂作业：P345第1题（二）算法步骤的改进n n把Johnson算法作些改变，改变后的算法按以下步骤进行：n n将所有aibi的零件

13、按ai值不减的顺序排成一个序列A。n n将所有aibi的零件按bi值不增的顺序排成一个序列B。n n将A放到B之前，就构成了最优加工顺序n n序列序列A A为为(2(2，5 5，6 6，1)1)，序列，序列B B为为(4(4，3)3)，构，构成最优顺序为成最优顺序为(2(2，5 5，6 6，1 1，4 4，3)3)，与，与JohnsonJohnson算法结果一致。算法结果一致。表11-4 改进算法改进算法 i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 i 1 3ai 5 8bi 2 1 2 5 3 7 6 4 4 7 2 44 5 4 ai aibib

14、i，bi bi值不增值不增 aibiaibi，ai ai值不减值不减 n nJohnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序n n对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。n n对于一般的流水车间排列排序问题，可以用分支定界法。三、求一般n/m/P/Fmax问题近优解(Near optimal solution)的启发式算法 1、Palmer法：按斜度指标排列工件的启发式算法按斜度指标排列工件的启发式算法 n n工件的斜度指标按下式

15、计算：m m为机器数；为机器数；P Pikik 为工件为工件i i在在M Mk k 上的加工时间，上的加工时间，k k是机是机器编号，按照各工件器编号，按照各工件i i不增的顺序排列工件不增的顺序排列工件,可得可得出满意顺序出满意顺序k=1，2，3.m例：有一个4/3/P/Fmax 问题，其加工时间如下表所示，用Palmer法求解。表11-5 加工时间矩阵 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 =(1-2)Pi1+(2-2)Pi2+(3-2)Pi3=-P i1 +P i3 解解K=11=-P 11+P 13=-1+4=3 2=-P21+P2

16、3=-2+5=3 3=-P31+P33=-6+8=2 4=-P 41+P43=-3+2=-1 按i不增的顺序排列，得到加工顺序（1，2，3，4）和（2，1，3，4），两者均为最优顺序，Fmax=28。i=-P i1 +P i3 作业：作业：P345第第2题用题用Palmer法求解法求解2、关键工件法（1 1）计计算算每每个个工工件件的的总总加加工工时时间间，找找出出加加工工时时间间最最长长的工件的工件C C，将其作为关键工件；，将其作为关键工件；（2 2）对对于于余余下下的的工工件件若若P Pi1i1PPimim，则则按按P Pi1i1不不减减的的顺顺序序排排成成一一个个序序列列S Sa a，

17、若若P Pi1i1P Pimim，则则按按P Pimim不不增增的的顺顺序序排排列列成成一个序列一个序列S Sb b。（3 3）顺序（）顺序（S Sa a，C C，S Sb b）即为所求顺序。）即为所求顺序。n n关键工件法求近优解举例 表11-5 加工时间矩阵 i 1 2 3 4 5 Pi1 1 2 6 3 4 Pi2 8 4 2 9 3 Pi3 4 5 8 2 3 表11-6用关键零件法求解 i2Pi3pi i 1 2 3 4 5 Pi1 1 2 6 3 4 P 8 4 2 9 3 4 5 8 2 3 13 11 16 14 10 1、找出最长时间2、Pi1PimPi1Pim，则按，则按P

18、i1Pi1不减不减3 3、若、若Pi1Pi1PimPim，则按，则按PimPim不增不增4 4、组成（、组成（Sa Sa，C C，SbSb）1，235，4作业：P345第3题用关键工件法求解3、CDS法n n Campbell-Dudek-Smith Campbell-Dudek-Smith 三人提出了一个启三人提出了一个启发式算法发式算法,简称简称CDSCDS法。他们把法。他们把JohnsonJohnson算法用于算法用于一般的一般的n/m/P/Fn/m/P/Fmaxmax问题，得到问题，得到(1)1)个加工顺序个加工顺序，取其中优者。，取其中优者。具体做法具体做法,对加工时间对加工时间和和

19、L=1,2,.,m-1L=1,2,.,m-1用用JohnsonJohnson算法求算法求(1)1)次加工顺序次加工顺序,取最优取最优.L表示多少个加工工序.表示前面L个工序的时间和，表示后面L个工序的时间和。CDS法可以总结为：法可以总结为：L=1时，求第时，求第1道和最后一道工序的加工时间矩阵道和最后一道工序的加工时间矩阵L=2时，求前时，求前2道和后道和后2道工序的加工时间和的矩阵道工序的加工时间和的矩阵L=3时，求前时，求前3道和后道和后3道工序的加工时间和的矩阵道工序的加工时间和的矩阵L=4时，求前时，求前4道和后道和后4道工序的加工时间和的矩阵道工序的加工时间和的矩阵L=m-1，求前

20、，求前m-1道和后道和后m-1道工序的加工时间和道工序的加工时间和的矩阵的矩阵如：用CDS求机器数M为3时的加工顺序。首先，计算L=1时的加工时间，和即Pi1和Pi3再计算L=2时的加工时间，和当当L L1 1时，按时，按JohnsonJohnson算法得到加工顺序算法得到加工顺序(1(1，2 2，3 3，4)4)，相应的相应的F Fmaxmax2828。当当L L2 2时，得到加工顺序时，得到加工顺序(2(2，3 3，1 1，4)4)。对于顺序。对于顺序(2(2，3 3，1 1，4)4)，相应的，相应的F Fmaxmax2929。所以，取顺序所以，取顺序(1(1，2 2，3 3，4)4)。我

21、们已经知道，这就是最。我们已经知道，这就是最优顺序。优顺序。表表11-7用用CDS法求解法求解i 1 2 3 4 Pi1 1 2 6 3 L=1Pi3 4 5 8 2 Pi1+Pi2 9 6 8 12 L=2Pi2+Pi3 12 9 10 11 四、四、相同相同零件、不同移动方式下加工零件、不同移动方式下加工周期的计算周期的计算零件在加工过程中可以采用三种典型的移零件在加工过程中可以采用三种典型的移动方式：动方式：顺序移动顺序移动 平行移动平行移动 平行顺序移动平行顺序移动n n例：一批制品，批量例：一批制品，批量例：一批制品，批量例：一批制品，批量n=4 4 4 4件，须经四道工序加工，件，

22、须经四道工序加工，件，须经四道工序加工，件，须经四道工序加工，各工序时间分别为：各工序时间分别为：各工序时间分别为：各工序时间分别为：t t t t1 1 1 1=10,t=10,t=10,t=10,t2 2 2 2=5,t=5,t=5,t=5,t3 3 3 3=15,t=15,t=15,t=15,t4 4 4 4=10=10=10=10。n加工批量；加工批量；m工序数目；工序数目；ti工件在第工件在第i工序的单工序的单件工时；件工时；四、相同零件、不同移动方式下加工周期的计算一批零件在上道工序全部加工完毕后,才整批转移到下道工序加工。n加工批量；加工批量；m工序数目；工序数目；ti工件在第工

23、件在第i工序的单件工时；工序的单件工时；工序工序M1M2M3M4T顺序顺序t2t1t3t4时间时间1、顺序移动方式:顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。工序工序T平行平行时间时间M1M2M3M42、平行移动方式t1t2t3t4平行移动方式下的加工周期计算平行移动方式下的加工周期计算平行移动方式下的加工周期计算平行移动方式下的加工周期计算要求每道工序连续进行，但又要求各道工序尽可能平行

24、地加工。工序工序M1M2M3M4T平顺平顺t2t1t3t4时间时间3、平行顺序移动方式、平行顺序移动方式工序工序M1M2M3M4T平顺平顺t2t1t3t4时间时间第第1种情况：种情况：ti ti+1 考虑平行性，实现交叉作业考虑平行性，实现交叉作业按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，第第2个工序的第个工序的第1个工件加工完成后立刻转移到第个工件加工完成后立刻转移到第3个工序进行加工。个工序进行加工。3、平行顺序移动方式、平行顺序移动方式工序工序M1M2M3M4T平顺平顺t2t1t3时间时间t

25、4第第2种情况：种情况：ti ti+1 考虑设备加工的连续性考虑设备加工的连续性第第1个工序的所有工件加工完成的时刻为基准，向前推（个工序的所有工件加工完成的时刻为基准，向前推（n-1）个）个t2时间，作为时间，作为第第2个工序的开始时间。即从红线开始向前推个工序的开始时间。即从红线开始向前推3个作为第个作为第2个工序的开始时间。个工序的开始时间。3、平行顺序移动方式、平行顺序移动方式xT=nt1+t2+x+t4X=nt3-(n-1)t2n nT=n(t1+t2+t3+t4)-(n-1)(t2+t2+t4)Min(tj,tj+1)前后相邻两工序中前后相邻两工序中单件工时之较小者单件工时之较小者

26、T=4(10+5+15+10)-(4-1)(5+5+10)=100分钟工序工序M1M2M3M4M5T平顺平顺t2t1t3时间时间t4加加工工周周期期的的计计算算Min(tj,tj+1)前后相邻两前后相邻两工序中单件工时之工序中单件工时之较小者较小者3、平行顺序移动方式、平行顺序移动方式零件三种移动方式的比较比较项目比较项目顺序移动顺序移动平行移动平行移动平行顺序移平行顺序移动动生产周期生产周期运输次数运输次数设备利用设备利用组织管理组织管理长长少少好好简单简单短短多多差差中中中中中中好好复杂复杂选择策略选择策略小而轻；单件小而轻；单件小批；加工时小批；加工时间短；调整时间短；调整时间长；工艺专

27、间长；工艺专业化业化大而重；大量大大而重；大量大批；加工时间长；批；加工时间长；调整时间短；对调整时间短；对象专业化象专业化小而轻；大小而轻；大量大批；加量大批；加工时间长；工时间长；调整时间短；调整时间短；对象专业化对象专业化第三节第三节 单件作业计划问题单件作业计划问题 是十分复杂的一种作业计划问题，内容和方法描述 n个零件在m台机器上进行作业，使加工时间最短的单件作业排序结果表示实质是任务分配问题：匈牙利算法经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用从加工时间（费用）矩阵中寻找每一行的最小元素从加工时

28、间（费用）矩阵中寻找每一行的最小元素从加工时间（费用）矩阵中寻找每一行的最小元素从加工时间（费用）矩阵中寻找每一行的最小元素将每一行元素减去该行最小元素将每一行元素减去该行最小元素将每一行元素减去该行最小元素将每一行元素减去该行最小元素从加工时间（费用）矩阵中寻找每一列的最小元素从加工时间（费用）矩阵中寻找每一列的最小元素从加工时间（费用）矩阵中寻找每一列的最小元素从加工时间（费用）矩阵中寻找每一列的最小元素将每一列元素减去该列最小元素将每一列元素减去该列最小元素将每一列元素减去该列最小元素将每一列元素减去该列最小元素划出能覆盖尽可能多的零元素的直线划出能覆盖尽可能多的零元素的直线划出能覆盖尽

29、可能多的零元素的直线划出能覆盖尽可能多的零元素的直线线条数等于矩阵的行数？线条数等于矩阵的行数？线条数等于矩阵的行数？线条数等于矩阵的行数？从仅有一个零的行或列开始，找出零元素对从仅有一个零的行或列开始，找出零元素对从仅有一个零的行或列开始，找出零元素对从仅有一个零的行或列开始，找出零元素对应的分配方案，每行和每列仅能确定一个元应的分配方案，每行和每列仅能确定一个元应的分配方案，每行和每列仅能确定一个元应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素素，最后使每行和每列都有一个零元素素，最后使每行和每列都有一个零元素素，最后使每行和每列都有一个零元素是是是是零元素对应的

30、就是最优分配方案零元素对应的就是最优分配方案零元素对应的就是最优分配方案零元素对应的就是最优分配方案矩阵中未被线条穿过的矩阵中未被线条穿过的矩阵中未被线条穿过的矩阵中未被线条穿过的元素中减去这些元素中元素中减去这些元素中元素中减去这些元素中元素中减去这些元素中的最小值，并将这个最的最小值，并将这个最的最小值，并将这个最的最小值，并将这个最小值加到直线交叉的元小值加到直线交叉的元小值加到直线交叉的元小值加到直线交叉的元素上，其余元素不变素上，其余元素不变素上，其余元素不变素上，其余元素不变否否否否一、任务分配：匈牙利算法流程一、任务分配：匈牙利算法流程 经营者提供商品或者服务有欺诈行为的，应当按

31、照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例：如如右右表表，请请用用匈匈牙牙利利法求出任务分配法求出任务分配 解：解：例题 1、每行所有元素减去该行最小元素。2、每列所有元素减去该列最小元素。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3、划出能覆盖尽可能多的0元素的直线，如果线条数等于矩阵列数，则找到最优解。否则继续。4、没被线条穿过的元素减去这些元素中的最小数。并将这个最小数加到直线交叉的元素上。然后重复3、45、从仅有一个0元素的行或列开始，最后使每行和每

32、列都有一个0元素。0元素对应的就是最优分配方案。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用结果矩阵表示：零件结果矩阵表示：零件1 1由机器由机器3 3加工（加工（J1M3J1M3）零件零件2 2由机器由机器2 2加工加工(J2M2)(J2M2)零件零件3 3由机器由机器4 4加工加工(J3M4)(J3M4)零件零件4 4由机器由机器1 1加工加工(J4M1)(J4M1)结果 二、单件作业排序问题的描述用（i，j，k）表示工件i 的第j道工序在机器k上进行。i表示工件代号j表示工序号k表示完成任务的机器代号。

33、如加工描述矩阵D。三、优先派工法则n n按按优优先先调调度度法法则则挑挑选选工工序序比比随随意意挑挑选选一一道道工工序序的的方方法法更更能能符符合合计计划划编编制制者者的的要要求求，同同时时又又不不必必列列出出所所有有可可能能的的作作业业计划，从而计算量小。计划，从而计算量小。n n迄迄今今，人人们们已已提提出出了了100100多多个个优优先先调调度度法法则则，其其中中主主要要的的有下有下4 4个：个：n nFCFS(First FCFS(First Come Come First First Served)Served)法法则则优优先先选选择择最最早早进入可排工序集合的工件。进入可排工序集合

34、的工件。n nSPT(Shortest SPT(Shortest Processing Processing Time)Time)法法则则优优先先选选择择加加工工时间最短的工序。时间最短的工序。n nEDD(Earliest EDD(Earliest Due Due Date)Date)法法则则优优先先选选择择完完工工期期限限紧紧的的工件。工件。n nLPT(Longest LPT(Longest Processsing Processsing Time)Time)法法则则优优先先选选择择加加工工时间最长的工件。时间最长的工件。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其

35、受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用四、一般n/m/G/Fmax问题的算法1、符号说明uuSSt ttt步步之之前前已已排排序序工工序序构构成成的的部部分分作作业计划；业计划；uu O Ot t 第第t t步可以排序的工序的集合；步可以排序的工序的集合；uuT Tk k O Ot t 中中工工序序O Ok k的的最最早早可可能能开开工工时时间；间；uuT Tk k O Ot t 中中工工序序O Ok k的的最最早早可可能能完完工工时时间。间。作业计划构成分类 能动作业计划：各工序按最早可能完工时间安排的作业计划。无延迟作业计划：各工序按最早可能开工时间安排的作业计划

36、。2、能动作业计划的构成步骤:设设t t1 1，SS1 1 为空集，为空集，OO1 1 为各工件第一道工为各工件第一道工序的集合。序的集合。求求T T*minTminTk k，并求出，并求出T T*出现的机器出现的机器M M*。如。如果果M M*有多台，则任选一台。有多台，则任选一台。TTk k最早完成时间最早完成时间.从从OOt t 中挑出满足以下两个条件的工序中挑出满足以下两个条件的工序O Oj j：需：需要机器要机器M M*加工，且加工，且T Tk kT T*。Tk Tk最早开工时间最早开工时间.将确定的工序将确定的工序O Oj j放入放入SSt t，从，从 O Ot t 中消去中消去O

37、 Oj j，并将并将O Oj j的紧后工序放入的紧后工序放入 O Ot t ，使，使t tt t1 1。若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，停；否则，停止。止。例题：有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：试构成一个能动作业计划。2,3,2M2131382,3,261,3,2M28812771,3,22,3,252,2,1M1787731,3,22,2,141,2,3M3M1777331,2,32,2,132,1,3M3363201,2,32,1,321,1,1M1223 0 0 1,1,12.1.31QjM*T*TkTkQtt解：解：T

38、k最早开工时间；最早开工时间；Tk=最早完成时间；最早完成时间；T*=最早完工时间中的最小者最早完工时间中的最小者 1,1,1 1,2,3 1,3,2 D 2,1,3 2,2,1 2,3,2 2 4 1 T3 4 5最优作业计划为：最优作业计划为：1,1,1 2,1,3 1,2,3 2,2,1 1,3,2 2,3,2机器M1M2M30时间1,1,12,2,1 2 3 72,3,21,3,27 8 13 2,1,31,2,3 3 73、无延迟作业计划的构成步骤:n n 设设t t1 1，SS1 1 为空集，为空集，OO1 1 为各工件为各工件第一道工序的集合。第一道工序的集合。n n求求T T*

39、minTminTk k，并求出，并求出T T*出现的机器出现的机器M M*。如果如果M M*有多台，则任选一台。有多台，则任选一台。T Tk k最早开始时间最早开始时间.n n从从OtOt中挑出满足以下两个条件的工序中挑出满足以下两个条件的工序O Oj j：需要机器：需要机器M M*加工，且加工，且T Tk kT T*。n n将确定的工序将确定的工序O Oj j放入放入SSt t，从，从 O Ot t 中消中消去去O Oj j，并将，并将O Oj j的紧后工序放入的紧后工序放入 O Ot t ，使，使t tt t1 1。n n若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，；否则，

40、停止。停止。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,1M1M30023 0 0 1,1,12.1.31QjM*T*TkTkQtt解：解：Tk最早开工时间；最早开工时间；Tk=最早完成时间；最早完成时间；T*=最早开工时间中的最小者最早开工时间中的最小者最优作业计划为：最优作业计划为：1,1,1 2,1,3 1,2,3 2,2,1 2,3,2 1,3,22,3,21,3,27 12 13 机器M

41、1M2M30时间1,1,12,2,1 2 3 72,1,31,2,3 3 7三类启发式算法n n1 1、MWKR(Most MWKR(Most Work Work Remaining)Remaining)法法则则优优先先选选择余下加工时间最长的工件。择余下加工时间最长的工件。n n2 2、LWKR(Least LWKR(Least Work Work Remaining)Remaining)法法则则优优先先选择余下加工时间最短的工件。选择余下加工时间最短的工件。n n3 3、MOPNR(Most MOPNR(Most Operations Operations Remaining)Remain

42、ing)法法则则优先选择余下工序数最多的工件。优先选择余下工序数最多的工件。n n4 4、SCR(Smallest SCR(Smallest Critical Critical Ratio)Ratio)法法则则 优优先先选选择择临临界界比比最最小小的的工工件件。临临界界比比为为工工件件允允许许停留时间与工件余下加工时间之比。停留时间与工件余下加工时间之比。n n5 5、RANDOMRANDOM法则随机地挑一个工件法则随机地挑一个工件 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n n判断题第2小题除外；n n选择题第1、2、4题。n n计算第2题。