流水作业的排序问题

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 流水作业的排序问题,9.1,排序问题概述,9.2,流水作业排序问题,9.1,排序问题概述,一、排序问题的基本概念,排序是确定工件（零部件）在一台或一组设备,上加工的先后顺序。,在一定约束条件下，寻找总加工时间最短的安,排产品加工顺序的方法，就是生产作业排序。,例如，考虑32项任务（工件），有32！,2.610,35,种方案,假定计算机每秒钟可以检查1,billion,个顺序, 全部检验完毕需要8,.410,15,个世纪.,如果只有16个工件, 同样按每秒钟可以检查1,billion,个顺序计算, 也需要2/3年.,以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。,所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,假设条件,1.一个工件不能同时在几台不同的机器上加工。,2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。,3.不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。,4.每道工序只在一台机器上完成。,5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。,6.每台机器同时只能加工一个工件。,排序常用的符号,Ji-,工件,i，i=1,2,.n。,Mj,-,机器,j，j1，2，m.,pij,-,工件,Ji,在机器,Mj,上的加工时间,j=1,m,Pi-,工件,J,i,的加工时间；,di-,工件,J,i,的完工期限；,Ci-,工件,J,i,的完成时间；,Fi-,工件,J,i,的流程时间,，,即工件在车间的实际停留时间,，,在工件都已到达的情况下,Fi= Pi+ Wi,Wi-,工件,J,i,在加工过程中总的等待时间,Li-,工件,J,i,的延误时间,Li= Ci- di , Li0,延误,Fmax-,最长流程时间，,Fmax,maxFi,二、排序问题的分类和表示法,1、排序问题的分类：,(1),根据机器数的多少,单台机器的排序问题,多台机器的排序问题,(2),根据加工路线的特征,单件作业排序(,Job Shop),：,工件加工路线不同,流水作业排序(,Flow Shop),：所有,工件加工路线完全相同,(3),根据工件到达系统的情况,静态排序：,进行排序时，所有工件都已到达，可以一次对他们排序,动态排序：,工件陆续到达，要随时安排他们的加工顺序,（,4,）根据参数的性质,确定型排序：,指加工时间和其他参数是已知确定的量,随机型排序：,指加工时间和有关参数为随机变量,（,5,）根据要实现的目标,单目标排序,多目标排序,2、,排序问题的表示法,排序问题常用四个符号来描述:,n/m/A/B,其中,n-,工件数；,m-,机器数；,A-,车间类型；,F,流水作业排序，,P,流水作业排列排序,G,一般类型,即单件型排序,B-,目标函数,9.2,流水作业排序问题,一、,最长流程时间,F,max,的计算,工件,S,i,在机器,M,K,上的完工时间为,C,KSi,工件,S,i,在机器,M,K,上的加工时间为,P,SiK,C,1Si,= C,1Si-1,+P,Si1,C,KSi,=max,C,(k-1)Si, C,kSi-1,+P,Sik,举例：有一个6/,4/,p,/,F,max,问题，其加工时间如下表所示。当按顺序,S（6，1，5，2，4，3）,加工时，求,F,max。,i,1 2 3 4 5 6,P,i1,P,i2,P,i3,p,i4,4 2 3 1 4 2,4 5 6 7 4 5,5 8 7 5 5 5,4 2 4 3 3 1,i,6 1 5 2 4 3,P,i1,P,i2,P,i3,p,i4,2,2,4,6,4,10,2,12,1,13,3,16,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,13,4,21,3,25,2,32,3,38,4,46,二、两台机器排序问题,两台机器排序的目标是使最大完成时间（总加工周期）,Fmax,最短 。,实现两台机器排序的最大完成时间,Fmax,最短的目标，一优化算法就是著名的约翰逊法(,Johnsons Law)。,其具体求解过程如下例所示。,约翰逊贝尔曼法则,约翰逊法解决这种问题分为4个步骤：,(1)列出所有工件在两台设备上的作业时间。,(2)找出作业时间最小者。,(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。,(4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。,举例,AB,两台设备完成,6,个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,J,1,J,2,J,3,J,4,J,5,J,6,机器,A,5,1,8,5,3,4,机器,B,7,2,2,4,7,4,机器,工件编 号,求解过程,由约翰逊法可知，表中最小加工时间值是1个时间单位,出现在设备1上，根据约翰逊法的规则，应将对应的工件,2,排在第一位，即得：,J2- * - * - * - * -*,去掉,J2，,在剩余的工件中再找最小值，最小值是2个时间单位，它是出现在设备2上，所以应将对应的工件,J3,排在最后一位，即：,J2 - * - * - * -* J3,再去掉,J3，,在剩余的,J1、J4、J5,、,J6,中重复上述步骤，求解过程为：,J2,J5 - * - * - * - J3,J2 J5,J6,- * - * J3,J2 J5,J6,- * -J4 J3,J2 J5,J6, J1 - -J4 J3,当同时出现多个最小值时，可从中任选一个。,J2 J5 J6- J1- J4,J3,或,J2 J5 J1-J6 - J4,J3,i,2 5 6 1 4 3,P,i1,P,i2,1,1,3,4,4,8,5,13,5,18,8,26,2,3,7,11,4,15,7,22,4,26,2,28,i,2 5 1 6 4 3,P,i1,P,i2,1,1,3,4,5,9,4,13,5,18,8,26,2,3,7,11,7,18,4,22,4,26,2,28,求得最优顺序下的,Fmax,28,Johnson,算法的改进,1.,将所有,a,i,b,i,的工件按,a,i,值不减的顺序排成一个序列,A,；,2.,将,a,i,b,i,的工件按,b,i,值不增的顺序排成一个序列,B,；,3.,将,A,放到,B,之前，就构成了一个最优加工顺序。,J,1,J,2,J,3,J,4,J,5,J,6,机器,A,5,1,8,5,3,4,机器,B,7,2,2,4,7,4,ai bi,工件按,ai,值不减的顺序（由小到大）排列 ：,J2 J5 J6- J1,；,ai,bi,的工件按,bi,值不增的顺序（由大到小）排列：,J4,J3,最后排序,J2 J5 J6- J1- J4,J3,三、,m(m,3),台机器排序问题的算法,一般采用启发式算法解决这类问题。,斜度指标法,关键工件法,CDS,法,（一）,Palmer（,斜度指标法）,工件的斜度指标计算公式,k1，2，m,式中，,m,机器数；,Pik,为工件,i,在,Mk,上的加工时间。,按照各工件,i,不增的顺序排列工件，可得出令人满意,的顺序。,i=,举例,有一个4/3/,F/Fmax,问题，其加工时间如下表所示，用,Palmer,法求解。,i,1 2 3 4,P,i1,P,i2,P,i3,1 2 6 3,8 4 2 9,4 5 8 2,i , -,P,i1,+,P,i3,1-,P,11,+,P,13,= -143,2-,P,21,+,P,23,= -2+5=3,3-,P,31,+,P,33,= -6+8=2,4-,P,41,+,P,43,= -3+2=-1,按,i,不增的顺序排列工件，得到加工顺序,（1，2，3，4）或（2，1，3，4）,k=1,，,2,，,3,i,1 2 3 4,P,i1,P,i2,P,i3,1,1,2,3,6,9,3,12,8,9,4,13,2,15,9,24,4,13,5,18,8,26,2,28,Fmax=28,i,2 1 3 4,P,i1,P,i2,P,i3,2,2,1,3,6,9,3,12,4,6,8,14,2,16,9,25,5,11,4,18,8,26,2,28,Fmax=28,加工顺序（1，2，3，4）或（2，1，3，4）,（二）关键工件法,1、 计算,Pi= ,找出其中最大者，定义为关键工件,Jc。,2、除,Jc,外，将满足,P,i1,P,im,的工件，按,P,i1,值的 大小，从小到大排在,Jc,的前面。,3 、除,Jc,外，将满足,p,i1,p,im,的工件，按,P,im,值的大小，从大到小排在,Jc,的后面。,i,1 2 3 4,P,i1,P,i2,P,i3,1 2 6 3,8 4 2 9,5 8 2,P,i,13 11 16 14,（,1,）工件,3,加工时间最长，作为关键工件。,（,2,）,满足,Pi1p,i3,的工件是,4,，将,4,排在,3,的后面。,所以加工顺序为（,1,，,2,，,3,，,4,）。,i,1 2 3 4,P,i1,P,i2,P,i3,1,1,2,3,6,9,3,12,8,9,4,13,2,15,9,24,4,13,5,18,8,26,2,28,举例,J,1,J,2,J,3,J,4,J,5,J,6,机器1,p,i1,5,5,4,1,2,10,机器2,p,i2,5,5,5,3,6,10,机器3,p,i3,8,3,3,4,7,4,机器4,p,i4,2,8,2,1,5,6,机器5,p,i5,5,2,1,2,8,10,总和,25,23,15,11,28,40,具体过程,（,1,）找出关键工件：工作负荷最大的40，对应的是工 件 6，,Jc=J6,（,2,）满足,P,i1,P,i5,的工件有,J1,、,J4,、,J5,按,P,i1,值由小到大,排在关键工件前面，所以有,J4 J5 J1 -J6,（,3,）满足,p,i1,p,i5,的工件有,J2,、,J3,，按,P,i5,值由大到小,排在关键工件的后面,所以有 ,J6 J2 J3,J4 J5 J1 J6 J2 J3 Fmax=51,（三）,CDS,法,Campbell, Dudek, Smith,三人于1970年共同提出了一个启发式算法，简称,CDS,法。他们把,Johnson,算法用于一般的,n /m /P/Fmax,问题，得到（,m,一1)个加工顺序，取其中优者。,具体做法是，对加工时间 和,（,l,=1，2，,，m-1），,用,Johnson,算法求（,m-1),次加工顺序，取其中最好的结果。,i,1 2 3 4,l,=1,P,i1,1 2 6 3,P,i3,4 5 8 2,l,=2,P,i1,+,P,i2,9 6 8 12,P,i2,+,P,i3,12 9 10 11,举例,当,l,1,时，按,Johnson,算法得到加工顺序,（1，2，3，4）,i,1 2 3 4,P,i1,P,i2,P,i3,1,1,2,3,6,9,3,12,8,9,4,13,2,15,9,24,4,13,5,18,8,26,2,28,Fmax=28,当,l,=2,时，得到加工顺序(2，3，1，4),对于顺序（2，3，1，4）,i,2 3 1 4,P,i1,P,i2,P,i3,2,2,6,8,1,9,3,12,4,6,2,10,8,18,9,27,5,11,8,19,4,23,2,29,Fmax=29,所以，取顺序（1，2，3，4）,四、相同零件、不同移动方式下加工周期的计算,1,、顺序移动,一批零件在上道工序全部加工完毕后才整批转移到下道工序继续加工。一批零件的加工周期为：,例：已知,n=4,t,1,=10,分，,t,2,5,分钟，,t,3,15,分钟，,t,4,10,分钟，求,T,顺,t,1,t,4,t,2,t,3,工序,40 60 120 160,T,顺,4(10+5+15+10)=,160,（分钟）,2,、平行移动方式,每个零件在前道工序加工完毕后，立即转移到下道工,序继续加工，形成前后交叉作业。一批零件的加工周期为：,T,平,（,10,5,15,10,）（,4-1) 15 = 85 (,分钟）,t,1,t,3,时间,t,4,t,2,30 75 85,3,、平顺移动方式,当,t1ti+1,时，零件按平行移动方式转移；,当,t1ti+1,时，以,I,工序最后一个零件的完工时间为准，往前推移（,n-1) ti+1,作为零件在（,i+1),工序的开工时间。一批零件的加工周期为：,t,1,t,4,t,3,工序,时间,t,2,100 160,T,平顺,4 ,（,10,5,15,10,）（,4,1,）,（,5,5,10,） ,100,（分钟）,三种移动方式的比较,移动方式,顺序移动,平行移动,平行顺序移动,优缺点,（,1,）管理简单，设备不停歇，可充分负荷。,（,2,）有等待现象，加工周期长。,（,1,）周期最短，,（,2,）零件等待少，设备有停歇。,（,3,）运输频繁，管理复杂。,两者结合,扬长避短,适用条件,小而轻；单件小批；加工时间短，调整时间长；工艺专业化。,大且重；大量大批；加工时间长，调整时间短；对象专业化。,小而轻；大量大批；加工时间长，调整时间短；对象专业化。,练习题：,设某种零件批量为,5,件，加工工序数为,4,，每道工序单件加工时间为,t,1,=6,小时，,t,2,=10,小时，,t,3,=8,小时,t,4,=16,小时，试求三种移动方式下该批零件的加工周期？,T,顺,=5*(6+10+8+16)=5*40=200,小时,T,平,=(5-1)*16+40=4*16+40=64+40=104,小时,T,平顺,=5*40-(5-1)*(6+8+8)=200-4*22=200-88=112,小时,作业题：,某零件批量为,6,件,共,5,道工序,各工序的单件工时分别为,:t,1,=5,分, t,2,=2,分, t,3,=5,分, t,4,=3,分,t,5,=4,分,试计算该批零件不同移动方式的生产周期,(,工序间其他时间不计,).,