作业排序

第二节流水作业排序问题流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.只要加工路线一致：M1，M2,M3，…..，Mm,不要求每个零件都经过每台机器加工一、最长流程时间Fmax的计算最长流程时间又称作加工周期例题：6/4/p/Fmax问题，当按顺序S＝(6,1,5,2,4,3)加工时，求Fmax.表1加工时间矩阵-i123456Pi1423142Pi2456745Pi3587555Pi4424331加工周期为46表2顺序S下的加工时间矩阵i615243i1P2246410212113316i2P57411415520727633Pi3512517522830535742Pi4113421325232338446Pi1P一、最长流程时间Fmax的计算加工周期为37表3顺序S下的加工时间矩阵i123456i1P3336410212113316i2P25511415318725631Pi3510415520727532436Pi4111217323229335137Pi1P课堂作业：求Fmax.二、n/2/F/Fmax问题的最优算法（一）Johnson算法：①从加工时间矩阵中找出最短的加工时间。②若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个③若所有零件都已排序，停止。否则，转步骤①。例题：求表11-3所示的6/2/F/Fmax问题的最优解。将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143最优加工顺序为S=（2，5，6，1，4，3）。最优顺序下的Fmax=28表11-3加工时间矩阵i123456bi722474518534ai课堂作业：Johnson法则，最优排序！以及计算Fmax（二）算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：①将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。②将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。③将A放到B之前，就构成了最优加工顺序序列A为(2，5，6，1)，序列B为(4，3)，构成最优顺序为(2，5，6，1，4，3)，与Johnson算法结果一致。表11-4改进算法i123456ai518534bi722474i13ai58bi212537644724454ai＞bi，bi值不增ai≤bi，ai值不减Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题，可以用分支定界法。三、求一般n/m/P/Fmax问题近优解(Nearoptimalsolution)的启发式算法1、Palmer法：按斜度指标排列工件的启发式算法工件的斜度指标按下式计算：m为机器数；Pik为工件i在Mk上的加工时间，k是机器编号，按照各工件λi不增的顺序排列工件,可得出满意顺序k=1，2，3...mm1kikiP]2/)1m(k[例：有一个4/3/P/Fmax问题，其加工时间如下表所示，用Palmer法求解。表11-5加工时间矩阵i1234Pi11263Pi28429Pi34582=(1-2)Pi1+(2-2)Pi2+(3-2)Pi3=-Pi1+Pi3解K=1),3,2,1(,]2/)1([1kPmkmkikimkikiPk1]2/)13([mkikiPk1]2[λ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。λi=-Pi1+Pi3作业：用Palmer法求解2、关键工件法（1）计算每个工件的总加工时间，找出加工时间最长的工件C，将其作为关键工件；（2）对于余下的工件若Pi1≤Pim，则按Pi1不减的顺序排成一个序列Sa，若Pi1＞Pim，则按Pim不增的顺序排列成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。关键工件法求近优解举例表11-5加工时间矩阵i1234Pi11263Pi28429Pi34582表11-6用关键零件法求解i2Pi3pii1234Pi11263P84294582131116141、找出最长时间2、Pi1≤Pim，则按Pi1不减3、若Pi1≥Pim，则按Pim不增4、组成（Sa，C，Sb）1，234作业：用关键工件法求解3、CDS法Campbell-Dudek-Smith三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(ｍ－1)个加工顺序，取其中优者。具体做法,对加工时间Lkikp1和mLmkikp1L=1,2,....,m-1用Johnson算法求(ｍ－1)次加工顺序,取最优.L表示多少个加工工序.表示前面L个工序的时间和，mLmkikp1表示后面L个工序的时间和。Lkikp1CDS法可以总结为：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时的加工时间，和即Pi1和Pi3Lkkikikpp1113313113kikmLmkkikikppp再计算L=2时的加工时间，和21121iiLkkikikpppp323213213iikikmLmkkikikppppp当L＝1时，按Johnson算法得到加工顺序(1，2，3，4)，相应的Fmax＝28。当L＝2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1，4)，相应的Fmax＝29。所以，取顺序(1，2，3，4)。我们已经知道，这就是最优顺序。表11-7用CDS法求解i1234Pi11263L=1Pi34582Pi1+Pi296812L=2Pi2+Pi31291011作业：用CDS法求解四、相同零件、不同移动方式下加工周期的计算零件在加工过程中可以采用三种典型的移动方式：顺序移动平行移动平行顺序移动例：一批制品，批量n=4件，须经四道工序加工，各工序时间分别为：t1=10,t2=5,t3=15,t4=10。n——加工批量；m——工序数目；ti——工件在第i工序的单件工时；四、相同零件、不同移动方式下加工周期的计算一批零件在上道工序全部加工完毕后,才整批转移到下道工序加工。n——加工批量；m——工序数目；ti——工件在第i工序的单件工时；工序M1M2M3M4T顺序t2t1t3t4时间1、顺序移动方式:顺序移动方式下的加工周期计算工序数。批量；其中一般式：分钟））（代入例中数字：mntnTTtnntntntntTmiiii:(160101551041414321顺序移动方式下的加工周期计算每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。LmiitntT)1(1平行工序T平行时间M1M2M3M42、平行移动方式t1t2t3t4最长者。所有工序中，单件时间一般式：分钟）（代入例中数字：周期计算：平行移动方式下的加工长长:)1()(851531015510)1(13414321ttntTTtnttntttTmiiii平行移动方式下的加工周期计算要求每道工序连续进行，但又要求各道工序尽可能平行地加工。111)1(miismiitntnT平顺工序M1M2M3M4T平顺t2t1t3t4时间3、平行顺序移动方式工序M1M2M3M4T平顺t2t1t3t4时间第1种情况：titi+1考虑平行性，实现交叉作业按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，第2个工序的第1个工件加工完成后立刻转移到第3个工序进行加工。3、平行顺序移动方式工序M1M2M3M4T平顺t2t1t3时间t4第2种情况：ti≥ti+1考虑设备加工的连续性第1个工序的所有工件加工完成的时刻为基准，向前推（n-1）个t2时间，作为第2个工序的开始时间。即从红线开始向前推3个作为第2个工序的开始时间。3、平行顺序移动方式xT=nt1+t2+x+t4X=nt3-(n-1)t2T=n(t1+t2+t3+t4)-(n-1)(t2+t2+t4)),min()1(1111jmijmiittntnT平顺Min(tj,tj+1)——前后相邻两工序中单件工时之较小者T=4×(10+5+15+10)-(4-1)×(5+5+10)=100分钟),min()1(1111jmijmiittntnT平顺工序M1M2M3M4M5T平顺t2t1t3时间t4加工周期的计算Min(tj,tj+1)——前后相邻两工序中单件工时之较小者3、平行顺序移动方式第三节单件作业排序问题1、问题描述用（i，j，k）表示工件i的第j道工序在机器k上进行。其中i表示工件代号，j表示工序号，k表示完成任务的机器代号。如加工描述矩阵D。232122312231321111，，，，，，，，，，，，D二、一般n/m/G/Fmax问题的算法1、符号说明{St}──t步之前已排序工序构成的部分作业计划；{Ot}──第t步可以排序的工序的集合；Tk──{Ot}中工序Ok的最早可能开工时间；Tk’──{Ot}中工序Ok的最早可能完工时间。作业计划构成分类能动作业计划：各工序按最早可能完工时间安排的作业计划。无延迟作业计划：各工序按最早可能开工时间安排的作业计划。2、能动作业计划的构成步骤:①设t＝1，{S1}为空集，{O1}为各工件第一道工序的集合。②求T*＝min{T`k}，并求出T*出现的机器M*。如果M*有多台，则任选一台。T`k最早完成时间.③从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加工，且Tk＜T*。Tk最早开工时间.④将确定的工序Oj放入{St}，从{Ot}中消去Oj，并将Oj的紧后工序放入{Ot}，使t＝t＋1。⑤若还有未安排的工序，转步骤②；否则，停止。例题：有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：232122312231321111，，，，，，，，，，，，D543142T232122312231321111，，，，，，，，，，，，D543142T试构成一个能动作业计划。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,1M1223001,1,12.1.31QjM*T*T`kTk{Qt}t解：Tk最早开工时间；T`k=最早完成时间；T*=最早完工时间中的最小者1,1,11,2,31,3,2D＝2,1,32,2,12,3,2241T＝345最优作业计划为：1,1,12,1,31,2,32,2,11,3,22,3,2机器M1M2M30时间1,1,12