流水作业排序问题

《流水作业排序问题》由会员分享，可在线阅读，更多相关《流水作业排序问题（53页珍藏版）》请在金锄头文库上搜索。

1、第二节 流水作业排序问题,流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致. 只要加工路线一致：M1， M2, M3，Mm,不要求每个零件都经过每台机器加工,一、最长流程时间Fmax的计算,最长流程时间又称作加工周期 例题：6/4/p/ Fmax问题，当按顺序S( 6,1,5,2,4,3)加工时，求Fmax.,加工周期为46,表2顺序S下的加工时间矩阵,i,6 1 5 2 4 3,i1,P,2,2,4,6,4,10,2,12,1,13,3,16,i2,5,7,4,11,4,15,5,20,7,27,6,33,5,12,5,17,5,22,8,30,5,35,7,42,1,1

2、3,4,21,3,25,2,32,3,38,4,46,P,一、最长流程时间Fmax的计算,加工周期为37,表3顺序S下的加工时间矩阵,i,1 2 3 4 5 6,i1,P,3,3,3,6,4,10,2,12,1,13,3,16,i2,2,5,5,11,4,15,3,18,7,25,6,31,5,10,4,15,5,20,7,27,5,32,4,36,1,11,2,17,3,23,2,29,3,35,1,37,P,课堂作业：求Fmax.,二、n/2/F/Fmax问题的最优算法,（一）Johnson算法： 从加工时间矩阵中找出最短的加工时间。 若最短的加工时间出现在M1上，则对应的零件尽可能往前排

3、；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个 若所有零件都已排序，停止。否则，转步骤。,例题：求表11-3所示的6/2/F/Fmax问题的最优解。,最优加工顺序为S=（2，5，6，1，4，3）。,课堂作业： Johnson法则，最优排序！ 以及计算Fmax,（二）算法步骤的改进,把Johnson算法作些改变，改变后的算法按以下步骤进行： 将所有aibi的零件按ai值不减的顺序排成一个序列A。 将所有aibi的零件按bi值不增的顺序排成一个序列B。 将A放到B之前，就构成了最优加工顺序,序列A为 (2， 5

4、，6，1)，序列B为(4，3)，构成最优顺序为 (2，5，6，1， 4，3)，与Johnson算法结果一致。,表,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,3,ai,5,8,bi,7,2,4,aibi， bi值不增,aibi， ai值不减,Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序 对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。 对于一般的流水车间排列排

5、序问题，可以用分支定界法。,三、求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法,1、Palmer法：按斜度指标排列工件的启发式算法 工件的斜度指标按下式计算：,m为机器数；Pik 为工件i在Mk 上的加工时间，k是机器编号，按照各工件i不增的顺序排列工件,可得出满意顺序,例：有一个4/3/P/ Fmax 问题，其加工时间如下表所示，用Palmer法求解。,=(1-2) Pi1+(2-2) Pi2+(3-2) Pi3 =- P i1 + P i3,解,K=1,1 = - P 11 + P 13= -1+4 = 3 2 = -P21 + P23=

6、 -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,作业：用Palmer法求解,2、关键工件法 （1）计算每个工件的总加工时间，找出加工时间最长的工件C，将其作为关键工件； （2）对于余下的工件若Pi1Pim，则按Pi1不减的顺序排成一个序列Sa，若Pi1Pim，则按Pim不增的顺序排列成一个序列Sb。 （3）顺序（ Sa，C，Sb）即为所求顺序。,关键工件法求近优解举例

7、,表11-6用关键零件法求解,i2,P,i3,p,i,1、找出最长时间 2、 Pi1Pim，则按Pi1不减 3、若Pi1Pim，则按Pim不增 4、组成（ Sa，C，Sb）,1，2,3,4,作业： 用关键工件法求解,3、CDS法,Campbell-Dudek-Smith 三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(1)个加工顺序，取其中优者。,CDS法可以总结为： L=1时，求第1道和最后一道工序的加工时间矩阵 L=2时，求前2道和后2道工序的加工时间和的矩阵 L=3时，求前3道和后3道工序的加工时间和的矩阵 L=4时，求前4道和后

8、4道工序的加工时间和的矩阵 L=m-1，求前m-1道和后m-1道工序的加工时间和的矩阵,如：用CDS求机器数M为3时的加工顺序。 首先，计算L=1时的加工时间，,再计算L=2时的加工时间，,和,当L1时，按Johnson算法得到加工顺序(1，2，3，4)，相应的Fmax28。 当L2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1， 4)，相应的Fmax29。 所以，取顺序(1，2，3，4)。我们已经知道，这就是最优顺序。,表,11-7,用,CDS,法求解,i,1 2 3 4,P,i1,1 2 6 3,L=1,P,i3,4 5 8 2,P,i1,+P,i2,9 6 8 12,L=2,P

9、,i2,+P,i3,12 9 10 11,作业： 用CDS法求解,四、相同零件、不同移动方式下加工周期的计算,零件在加工过程中可以采用三种典型的移动方式： 顺序移动 平行移动 平行顺序移动,例：一批制品，批量n =4件，须经四道工序加工，各工序时间分别为：t1=10, t2=5, t3=15, t4=10。,n加工批量； m工序数目； ti工件在第i工序的单件工时；,四、相同零件、不同移动方式下加工周期的计算,一批零件在上道工序全部加工完毕后,才整批转移 到下道工序加工。,n加工批量； m工序数目； ti工件在第i工序的单件工时；,工序,M1,M2,M3,M4,T顺序,t2,t1,t3,t4,

10、时间,1、顺序移动方式:,顺序移动方式下的加工周期计算,顺序移动方式下的加工周期计算,每个零件在前道工序加工完毕后，立即转移到后 道工序去继续加工，形成前后工序交叉作业。,工序,T平行,时间,M1,M2,M3,M4,2、平行移动方式,t1,t2,t4,平行移动方式下的加工周期计算,要求每道工序连续进行，但又要求各道工序尽可能 平行地加工。,工序,M1,M2,M3,M4,T平顺,t2,t1,t3,t4,时间,3、平行顺序移动方式,工序,M1,M2,M3,M4,T平顺,t2,t1,t3,t4,时间,第1种情况：ti ti+1 考虑平行性，实现交叉作业,按平行移动方式的原则加工，即工件加工完成后立刻

11、转移到下一个工序，此处，第2个工序的第1个工件加工完成后立刻转移到第3个工序进行加工。,3、平行顺序移动方式,工序,M1,M2,M3,M4,T平顺,t2,t1,t3,时间,第2种情况：ti ti+1 考虑设备加工的连续性,第1个工序的所有工件加工完成的时刻为基准，向前推（n-1）个t2时间，作为第2个工序的开始时间。即从红线开始向前推3个作为第2个工序的开始时间。,3、平行顺序移动方式,x,T=nt1+t2+x+t4,X=nt3-(n-1)t2,T=n(t1+t2+t3+t4)-(n-1)(t2+t2+t4),Min(tj,tj+1)前后相邻两工序中单件工时之较小者,T=4(10+5+15+1

12、0)-(4-1) (5+5+10)=100分钟,工序,M1,M2,M3,M4,M5,T平顺,t2,t1,t3,时间,加工周期的计算,Min(tj,tj+1)前后相邻两工序中单件工时之较小者,3、平行顺序移动方式,第三节 单件作业排序问题,1、问题描述,用（i，j，k）表示工件i 的第j道工序在机器k上进行。其中i表示工件代号，j表示工序号，k表示完成任务的机器代号。如加工描述矩阵D。,二、一般n/m/G/Fmax问题的算法,1、符号说明 Stt步之前已排序工序构成的部分作业计划； Ot 第t步可以排序的工序的集合； Tk Ot 中工序Ok的最早可能开工时间； Tk Ot 中工序Ok的最早可能完

13、工时间。,作业计划构成分类,能动作业计划：各工序按最早可能完工时间安排的作业计划。 无延迟作业计划：各工序按最早可能开工时间安排的作业计划。,2、能动作业计划的构成步骤:,设t1，S1为空集，O1为各工件第一道工序的集合。 求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台。Tk最早完成时间. 从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TkT*。 Tk最早开工时间. 将确定的工序Oj放入St，从 Ot 中消去Oj，并将Oj的紧后工序放入 Ot ，使tt1。 若还有未安排的工序，转步骤；否则，停止。,例题：,有一个2/3/G/Fmax问题，其加工描述矩阵D和

14、加工时间矩阵T分别为：,试构成一个能动作业计划。,2,3,2,M2,13,13,8,2,3,2,6,1,3,2,M2,8,8 12,7 7,1,3,2 2,3,2,5,2,2,1,M1,7,8 7,7 3,1,3,2 2,2,1,4,1,2,3,M3 M1,7,7 7,3 3,1,2,3 2,2,1,3,2,1,3,M3,3,6 3,2 0,1,2,3 2,1,3,2,1,1,1,M1,2,2 3,0 0,1,1,1 2.1.3,1,Qj,M*,T*,Tk,Tk,Qt,t,解：Tk最早开工时间；Tk=最早完成时间；T*=最早完工时间中的最小者,1,1,1 1,2,3 1,3,2,D,2,1,3 2,2,1 2,3,2,最优作业计划为： 1,1,1 2,1,3 1,2,3 2,2,1 1,3,2 2,3,2,3、无延迟作业计划的构成步骤:, 设t1，S1为空集，O1为各工件第一道工序的集合。 求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台。Tk最早开始时间