《作业排序【优制材料】》由会员分享，可在线阅读，更多相关《作业排序【优制材料】（53页珍藏版）》请在金锄头文库上搜索。
1、第二节 流水作业排序问题n n流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.n n只要加工路线一致：M1， M2, M3，.，Mm,不要求每个零件都经过每台机器加工一、最长流程时间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 123456Pi1 423142Pi2456745Pi3587555Pi4424331 n n加工周期为46
2、表2顺序S下的加工时间矩阵i615243 i1P2246410212113316i2P57411415520727633Pi3512517522830535742Pi4113421325232338446Pi1P一、最长流程时间一、最长流程时间F Fmaxmax的计算的计算 n n加工周期为37 表表3 3顺序顺序S S下的加工时间矩阵下的加工时间矩阵i123456i1P3336410212113316i2P25511415318725631Pi3510415520727532436 Pi4111217323229335137Pi1P课堂作业：求课堂作业：求Fmax.二、n/2/F/Fmax问
3、题的最优算法（一）（一）JohnsonJohnson算法：算法：从加工时间矩阵中找出最短的加工时从加工时间矩阵中找出最短的加工时间。间。若最短的加工时间出现在若最短的加工时间出现在M M1 1上，则对上，则对应的零件尽可能往前排；若最短加工时间出现应的零件尽可能往前排；若最短加工时间出现在在M M2 2上，则对应零件尽可能往后排。然后，从上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个若最短加工时间有多个，则任挑一个若所有零件都已排序，停止。否则，若所有零件都已排序，停止。否则，转步骤转步骤。例
4、题：求表例题：求表11-311-3所示的所示的6/2/F/Fmax6/2/F/Fmax问题的最优解。问题的最优解。 将零件2排第1位 2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位25614 3最优加工顺序为S=（2，5，6，1，4，3）。最优顺序下的Fmax=28表表11-3加工时间矩阵加工时间矩阵i123456bi722 474518534ai课堂作业：Johnson法则，最优排序！以及计算Fmax（二）算法步骤的改进n n把Johnson算法作些改变，改变后的算法按以下步骤进行：n n将所有aibi的零件按ai值不减的顺序排
5、成一个序列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改进算法改进算法i1 2 3 4 5 6 ai 5 1 8 5 3 4bi 7 2 2 4 7 4i 1 3ai 5 8bi212 537 644 7 2 4454ai aibibi， bibi值不增值不增aibiai
6、bi， 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工件的斜度指标按下式计算：m m为机器数；为机器数；P
7、 Pikik 为工件为工件i i在在M Mk k 上的加工时间，上的加工时间，k k是机是机器编号，按照各工件器编号，按照各工件i i不增的顺序排列工件不增的顺序排列工件, ,可得可得出满意顺序出满意顺序k=1，2，3.m例：有一个4/3/P/Fmax问题，其加工时间如下表所示，用Palmer法求解。 表11 -5加工时间矩阵i1234 Pi1 1263 Pi28429 Pi34582 =(1-2)Pi1+(2-2)Pi2+(3-2)Pi3=- P i1 + P i3 解解K=11=-P11+P13=-1+4=32=-P21+P23=-2+5=33=-P31+P33=-6+8=24=-P41+
8、P43=-3+2=-1按i不增的顺序排列，得到加工顺序（1，2，3，4）和（2，1，3，4），两者均为最优顺序，Fmax=28。i=- P i1 + P i3 作业：用作业：用Palmer法求解法求解2、关键工件法（1 1）计计算算每每个个工工件件的的总总加加工工时时间间，找找出出加加工工时时间间最最长长的工件的工件C C，将其作为关键工件；，将其作为关键工件；（2 2）对对于于余余下下的的工工件件若若P Pi1i1PPimim，则则按按P Pi1i1不不减减的的顺顺序序排排成成一一个个序序列列S Sa a，若若P Pi1i1P Pimim，则则按按P Pimim不不增增的的顺顺序序排排列列成
9、成一个序列一个序列S Sb b。（3 3）顺序（）顺序（ S Sa a，C C，S Sb b）即为所求顺序。）即为所求顺序。 n n关键工件法求近优解举例 表11 -5加工时间矩阵i1234 Pi1 1263 Pi28429 Pi34582 表11-6用关键零件法求解i2Pi3pi i1 2 3 4Pi1 1 2 6 3P8 4 2 94 5 8 213111614 1、找出最长时间2、Pi1PimPi1Pim，则按，则按Pi1Pi1不减不减3 3、若、若Pi1Pi1 PimPim，则按，则按PimPim不增不增4 4、组成（、组成（ SaSa，C C，SbSb）1，234作业：用关键工件法求
10、解3 3、CDSCDS法法n n Campbell-Dudek-Smith Campbell-Dudek-Smith 三人提出了一个启三人提出了一个启发式算法发式算法, ,简称简称CDSCDS法。他们把法。他们把JohnsonJohnson算法用于算法用于一般的一般的n/m/P/Fn/m/P/Fmaxmax问题，得到问题，得到( (1)1)个加工顺序个加工顺序，取其中优者。，取其中优者。具体做法具体做法, ,对加工时间对加工时间和和L=1,2,.,m-1L=1,2,.,m-1用用JohnsonJohnson算法求算法求( (1)1)次加工顺序次加工顺序, ,取最优取最优. .L表示多少个加工工
11、序.表示前面L个工序的时间和，表示后面L个工序的时间和。CDS法可以总结为：法可以总结为： L=1时，求第时，求第1道和最后一道工序的加工时间矩阵道和最后一道工序的加工时间矩阵L=2时，求前时，求前2道和后道和后2道工序的加工时间和的矩阵道工序的加工时间和的矩阵L=3时，求前时，求前3道和后道和后3道工序的加工时间和的矩阵道工序的加工时间和的矩阵L=4时，求前时，求前4道和后道和后4道工序的加工时间和的矩阵道工序的加工时间和的矩阵L=m-1，求前，求前m-1道和后道和后m-1道工序的加工时间和道工序的加工时间和的矩阵的矩阵如：用CDS求机器数M为3时的加工顺序。首先，计算L=1时的加工时间，和
12、即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)。我们已经知道，这就是最。我们已经知道，这就是最优顺序。优顺序。 表表11-7用用CDS法求解法求解i1234Pi11263L=1Pi34582Pi1
13、+Pi296812L=2Pi2+Pi31291011作业：用CDS法求解四、四、相同相同零件、不同移动方式下加工零件、不同移动方式下加工周期的计算周期的计算零件在加工过程中可以采用三种典型的移零件在加工过程中可以采用三种典型的移动方式：动方式： 顺序移动顺序移动 平行移动平行移动 平行顺序移动平行顺序移动n n例：一批制品，批量例：一批制品，批量例：一批制品，批量例：一批制品，批量n =4 4 4 4件，须经四道工序加工，件，须经四道工序加工，件，须经四道工序加工，件，须经四道工序加工，各工序时间分别为：各工序时间分别为：各工序时间分别为：各工序时间分别为：t t t t1 1 1 1=10,
14、 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工件在第工件在第i工序的单件工时；工序的单件工时；工序工序M1M2M3M4T顺序顺序t2t1t3t4时间时间1、顺序移动方式:顺序移动方式下的加工周期计算顺
15、序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算顺序移动方式下的加工周期计算每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。工序工序T平行平行时间时间M1M2M3M42、平行移动方式t1t2t3t4平行移动方式下的加工周期计算平行移动方式下的加工周期计算平行移动方式下的加工周期计算平行移动方式下的加工周期计算要求每道工序连续进行，但又要求各道工序尽可能平行地加工。工序工序M1M2M3M4T平顺平顺t2t1t3t4时间时间3、平行顺序移动方式、平行顺序移动方式工序工序M1M2M3M4T平顺平顺t2t1
16、t3t4时间时间第第1种情况：种情况：ti ti+1 考虑平行性，实现交叉作业考虑平行性，实现交叉作业按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，第第2个工序的第个工序的第1个工件加工完成后立刻转移到第个工件加工完成后立刻转移到第3个工序进行加工。个工序进行加工。3、平行顺序移动方式、平行顺序移动方式工序工序M1M2M3M4T平顺平顺t2t1t3时间时间t4第第2种情况：种情况：ti ti+1 考虑设备加工的连续性考虑设备加工的连续性第第1个工序的所有工件加工完成的时刻为基准，向前推（个工序的所有工
17、件加工完成的时刻为基准，向前推（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)前后相邻两工序中前后相邻两工序中单件工时之较小者单件工时之较小者T=4(10+5+15+10)-(4-1)(5+5+10)=100分钟工序工序M1M2M3M4M5T平顺平顺t2t1t3时间时间t4加加工工周周期
18、期的的计计算算Min(tj,tj+1)前后相邻两前后相邻两工序中单件工时之工序中单件工时之较小者较小者3、平行顺序移动方式、平行顺序移动方式第三节第三节 单件作业排序问题单件作业排序问题 1、问题描述用（i，j，k）表示工件i的第j道工序在机器k上进行。其中i表示工件代号，j表示工序号，k表示完成任务的机器代号。如加工描述矩阵D。二、一般n/m/G/Fmax问题的算法1、符号说明uuSSt ttt步步之之前前已已排排序序工工序序构构成成的的部部分分作作业计划；业计划；uu O Ot t 第第t t步可以排序的工序的集合；步可以排序的工序的集合；uuT Tk k O Ot t 中中工工序序O O
19、k k的的最最早早可可能能开开工工时时间；间；uuT Tk k O Ot t 中中工工序序O Ok k的的最最早早可可能能完完工工时时间。间。 作业计划构成分类 能动作业计划：各工序按最早可能完工时间安排的作业计划。无延迟作业计划：各工序按最早可能开工时间安排的作业计划。2、能动作业计划的构成步骤: 设设t t1 1，SS1 1 为空集，为空集，OO1 1 为各工件第一道工为各工件第一道工序的集合。序的集合。求求T T* *minTminTk k ，并求出，并求出T T* *出现的机器出现的机器M M* *。如。如果果M M* *有多台，则任选一台。有多台，则任选一台。TTk k最早完成时间最
20、早完成时间. .从从OOt t 中挑出满足以下两个条件的工序中挑出满足以下两个条件的工序O Oj j：需：需要机器要机器M M* *加工，且加工，且T Tk kT T* *。 TkTk最早开工时间最早开工时间. .将确定的工序将确定的工序O Oj j放入放入SSt t ，从，从 O Ot t 中消去中消去O Oj j，并将并将O Oj j的紧后工序放入的紧后工序放入 O Ot t ，使，使t tt t1 1。若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，停；否则，停止。止。例题：有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：试构成一个能动作业计划。2,3
21、,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,1M1223001,1,12.1.31QjM*T*TkTkQtt解：解：Tk最早开工时间；最早开工时间；Tk=最早完成时间；最早完成时间；T*=最早完工时间中的最小者最早完工时间中的最小者 1,1,11,2,31,3,2 D 2,1,32,2,12,3,2241T345最优作业计划为：最优作业计划为：1,1,1 2,1,3 1,2,3 2,2,1 1,3,2 2,3,2
22、机器M1M2M30时间1,1,12,2,12372,3,21,3,278132,1,31,2,3373、无延迟作业计划的构成步骤:n n 设设t t1 1，SS1 1 为空集，为空集，OO1 1 为各工件为各工件第一道工序的集合。第一道工序的集合。n n求求T T* *minTminTk k ，并求出，并求出T T* *出现的机器出现的机器M M* *。如果如果M M* *有多台，则任选一台。有多台，则任选一台。T Tk k最早开始时间最早开始时间. .n n从从OtOt中挑出满足以下两个条件的工序中挑出满足以下两个条件的工序O Oj j：需要机器：需要机器M M* *加工，且加工，且T Tk
23、 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若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，；否则，停止。停止。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.31Q
24、jM*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,271213机器M1M2M30时间1,1,12,2,12372,1,31,2,337三类启发式算法1、优先派工法则n n按按优优先先调调度度法法则则挑挑选选工工序序比比随随意意挑挑选选一一道道工工序序的的方方法法更更能能符符合合计计划划编编制制者者的的要要求求，同同时时又又不不必列出所有可能的作业计划，从而计算量小。必列出所有可能
25、的作业计划，从而计算量小。 n n迄迄今今，人人们们已已提提出出了了100100多多个个优优先先调调度度法法则则，其中主要的有下其中主要的有下8 8个：个：n n SPT(Shortest SPT(Shortest Processing Processing Time)Time)法法则优先选择加工时间最短的工序。则优先选择加工时间最短的工序。n n FCFS(First FCFS(First Come Come First First Served)Served)法法则优先选择最早进入可排工序集合的工件。则优先选择最早进入可排工序集合的工件。优先派工法则(续)n nEDD(Earliest E
26、DD(Earliest Due Due Date)Date)法法则则优优先先选择完工期限紧的工件。选择完工期限紧的工件。n n MWKR(Most MWKR(Most Work Work Remaining)Remaining)法法则则优先选择余下加工时间最长的工件。优先选择余下加工时间最长的工件。n nLWKR(Least LWKR(Least Work Work Remaining)Remaining)法法则则优先选择余下加工时间最短的工件。优先选择余下加工时间最短的工件。n nMOPNR(Most MOPNR(Most Operations Operations Remaining)Re
27、maining)法则优先选择余下工序数最多的工件。法则优先选择余下工序数最多的工件。n nSCR(Smallest SCR(Smallest Critical Critical Ratio)Ratio)法法则则优优先先选选择择临临界界比比最最小小的的工工件件。临临界界比比为为工工件件允允许停留时间与工件余下加工时间之比。许停留时间与工件余下加工时间之比。n nRANDOMRANDOM法则随机地挑一个工件法则随机地挑一个工件 2 2、随机抽样法、随机抽样法n n用用穷穷举举法法或或分分支支定定界界法法求求一一般般单单件件车车间间排排序序问问题题的的最最优优解解时时，实实际际上上比比较较了了全全部
28、部能能动动作作业业计计划划；采采用用优优先先调调度度法法则则求求近近优优解解时时，只只选选择择了了一种作业计划。一种作业计划。n n随机抽样法介于这两个极端之间。随机抽样法介于这两个极端之间。n n它从全部无延迟作业计划之中抽样，得出多个它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。作业计划，从中选优。n n应用随机抽样法时，实际上是对同一个问题多应用随机抽样法时，实际上是对同一个问题多次运用随机法则来决定要挑选的工序，从而得次运用随机法则来决定要挑选的工序，从而得到多个作业计划。到多个作业计划。 3、概率调度法n n随机抽样法是从随机抽样法是从k k个可供选择的工序以等概率个可
29、供选择的工序以等概率方式挑选，每个工序被挑选的概率为方式挑选，每个工序被挑选的概率为1 1k k，这，这种方法没有考虑不同工序的特点，有一定盲目种方法没有考虑不同工序的特点，有一定盲目性。性。 n n例如，在构在无延迟作业计划的第例如，在构在无延迟作业计划的第步有步有3 3道道工序，工序，A A、B B和和C C可挑选，这可挑选，这3 3道工序所需的时间道工序所需的时间分别为分别为3 3，4 4和和7 7。如果按。如果按RANDOMRANDOM法则，每道工法则，每道工序挑选上的概率都是序挑选上的概率都是1 13 3；如果按；如果按SPTSPT法则，法则，则只能挑选工序则只能挑选工序A A。现按
30、目标函数的要求，选。现按目标函数的要求，选择了择了SPTSPT法则。按概率调度法，将这法则。按概率调度法，将这3 3道工序按道工序按加工时间从小到大排列，然后给每道工序从大加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如到小分配一个被挑选的概率，比如A A、B B和和C C的的挑选概率分别为挑选概率分别为6 61414、5 51414和和3 31414。作业作业第四节第四节 生产作业控制的生产作业控制的“ “漏斗模型漏斗模型漏斗模型漏斗模型” ” 1、“漏斗漏斗”：对处理过程的形象描述：对处理过程的形象描述一个工厂，一个车间，一个工作地，或者一台机床，都可以被看做是一个“
31、漏斗”。漏斗的输入：漏斗的输入：来自用户的订货，或上一工序转来的工件漏斗的输出：漏斗的输出：整个工厂、车间、工作地以及机床完工的任务量输入和输出之间形成的未完工量在制品：输入和输出之间形成的未完工量在制品：漏斗中的物料（如排队等待加工的零件等）某工作地加工能力为8小时天，现对该工作地做了为期10天的观察（某月2029日），在观察期内的投入出产情况如表所示，根据这些数据画出该工作地的输人输出曲线，并计算有关参数。其中110号工件已出产，1115号工件已投入，但尚未出产。例：例：AB AB ：观察期出：观察期出产量产量BABA：观察期初：观察期初在制品；在制品；BEBE：观察期末在：观察期末在制品
32、；制品；MLML：平均生产：平均生产率；率；MZMZ：加权平均：加权平均通过时间；通过时间；MIMI：平均在制品：平均在制品P P：观察期；：观察期；1 1、将一般流转图变为监测流转图、将一般流转图变为监测流转图2 2、监测生产任务从计划到加工结束期间全过程的情况、监测生产任务从计划到加工结束期间全过程的情况“漏斗模型漏斗模型”的应用的应用（1）用图表跟踪显示工作地的实际情况，并进行有关参数的测）用图表跟踪显示工作地的实际情况，并进行有关参数的测平均通过时间、平均在制品库存、设备利用率以及交货期偏差等（2）将计划值与实际值进行比较，若有偏差，找出原因，提出）将计划值与实际值进行比较，若有偏差，找出原因，提出修正措施修正措施通过控制任务投料量的大小或加工能力的调整来弥补已产生的偏差（3）监测已采取措施的执行情况，不断改进，直到满意）监测已采取措施的执行情况，不断改进，直到满意3 3、建立相应的生产监测和诊断系统、建立相应的生产监测和诊断系统
