11章作业排序1

第11章制造作业计划与控制第一节排序问题的基本概念第二节流水作业排序问题第三节单件作业排序问题第四节生产作业控制第一节作业计划和排序问题的基本概念作业计划与作业排序是一回事么？作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。编制作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。根据排序规则对每一个到达的工件安排作业顺序工作地工件排队等待加工来自上游工作地的工件加工完毕的工件流向下一工作地排序的概念排序的概念生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。目的：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货名词术语(略)“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、钻、冲、磨的路线加工，我们可以用M1,M2,M3,M4来表示。“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题排序问题分类按机器单台机器排序问题多台机器排序问题单件作业排序问题流水线作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质分类按参数确定型排序问题随机型排序问题排序问题的分类参数表示法:n/m/A/B。其中,n──零件数；m──机器数；A──作业类型；在A的位置若标以“F”，则代表流水作业排序问题。若标以“P”，则表示流水作业排列排序问题,即同顺序排序，所有零件在每台机器上的加工顺序相同。若标以“G”，则表示一般单件作业排序问题。当m＝1，则A处为空白B──目标函数，通常是使其值最小。参数表示法:n/m/P/Fmax所有零件在每台机器上的加工顺序相同。如在M1上都是第一道工序，M2上都是第二道工序。n/m/F/Fmax不同零件在每台机器上的加工顺序不同。如零件1在M1上不加工，在M2上才是第一道工序；而零件2在M1上是第一道工序。第二节流水作业排序问题流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.只要加工路线一致：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课堂作业：P345第1题（二）算法步骤的改进把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作业：P345第2题用Palmer法求解2、关键工件法（1）计算每个工件的总加工时间，找出加工时间最长的工件C，将其作为关键工件；（2）对于余下的工件若Pi1≤Pim，则按Pi1不减的顺序排成一个序列Sa，若Pi1＞Pim，则按Pim不增的顺序排列成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。关键工件法求近优解举例表11-5加工时间矩阵i12345Pi112634Pi284293Pi345823表11-6用关键零件法求解i2Pi3pii12345Pi112634P842934582313111614101、找出最长时间2、Pi1≤Pim，则按Pi1不减3、若Pi1＞Pim，则按Pim不增4、组成（Sa，C，Sb）1，235，4作业：P345第3题用关键工件法求解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四、相同零件、不同移动方式下加工周期的计算零件在加工过程中可以采用三种典型的移动方式：顺序移动平行移动平行顺序移动例：一批制品，批量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、平行顺序移动方式零件三种移动方式的比较比较项目顺序移动平行移动平行顺序移动生产周期运输次数设备利用组织管理长少好简