流水作业的排序问题

第九章流水作业的排序问题9.1排序问题概述9.2流水作业排序问题9.1排序问题概述一、排序问题的基本概念排序是确定工件（零部件）在一台或一组设备上加工的先后顺序。在一定约束条件下，寻找总加工时间最短的安排产品加工顺序的方法，就是生产作业排序。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪.如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年.以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。假设条件1.一个工件不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。4.每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件。排序常用的符号Ji---工件i，i=1,2,..n。Mj----机器j，j＝1，2，…，m.pij----工件Ji在机器Mj上的加工时间,j=1,…,mPi----工件Ji的加工时间；di----工件Ji的完工期限；Ci----工件Ji的完成时间；Fi----工件Ji的流程时间，即工件在车间的实际停留时间，在工件都已到达的情况下,Fi=Pi+WiWi----工件Ji在加工过程中总的等待时间Li----工件Ji的延误时间,Li=Ci-di,Li=0按期或完成提前；Li0延误Fmax----最长流程时间，Fmax＝max{Fi}二、排序问题的分类和表示法1、排序问题的分类：•(1)根据机器数的多少单台机器的排序问题多台机器的排序问题•(2)根据加工路线的特征单件作业排序(JobShop)：工件加工路线不同流水作业排序(FlowShop)：所有工件加工路线完全相同•(3)根据工件到达系统的情况静态排序：进行排序时，所有工件都已到达，可以一次对他们排序动态排序：工件陆续到达，要随时安排他们的加工顺序•（4）根据参数的性质确定型排序：指加工时间和其他参数是已知确定的量随机型排序：指加工时间和有关参数为随机变量•（5）根据要实现的目标单目标排序多目标排序2、排序问题的表示法排序问题常用四个符号来描述:n/m/A/B其中,n-----工件数；m-----机器数；A----车间类型；F－流水作业排序，P－流水作业排列排序G－一般类型,即单件型排序B-----目标函数9.2流水作业排序问题一、最长流程时间Fmax的计算工件Si在机器MK上的完工时间为CKSi•工件Si在机器MK上的加工时间为PSiK•C1Si=C1Si-1+PSi1•CKSi=max｛C(k-1)Si,CkSi-1｝+PSik举例：有一个6/4/p/Fmax问题，其加工时间如下表所示。当按顺序S＝（6，1，5，2，4，3）加工时，求Fmax。i123456Pi1Pi2Pi3pi4423142456745587555424331i615243Pi1Pi2Pi3pi4224641021211331657411415520727633512517522830535742113421325232338446二、两台机器排序问题两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。实现两台机器排序的最大完成时间Fmax最短的目标，一优化算法就是著名的约翰逊法(Johnson’sLaw)。其具体求解过程如下例所示。约翰逊－贝尔曼法则•约翰逊法解决这种问题分为4个步骤：•(1)列出所有工件在两台设备上的作业时间。•(2)找出作业时间最小者。•(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。•(4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。••举例•AB两台设备完成6个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。J1J2J3J4J5J6机器A518534机器B722474机器工件编号求解过程由约翰逊法可知，表中最小加工时间值是1个时间单位,出现在设备1上，根据约翰逊法的规则，应将对应的工件2排在第一位，即得：J2-*-*-*-*-*去掉J2，在剩余的工件中再找最小值，最小值是2个时间单位，它是出现在设备2上，所以应将对应的工件J3排在最后一位，即：J2-*-*-*--*J3再去掉J3，在剩余的J1、J4、J5、J6中重复上述步骤，求解过程为：J2－J5-*-*-*-J3J2–J5－J6-*-*–J3J2–J5－J6-*-J4–J3J2–J5－J6–J1--J4–J3当同时出现多个最小值时，可从中任选一个。J2–J5–J6-J1-J4－J3或J2–J5–J1-J6-J4－J3i256143Pi1Pi211344851351882623711415722426228i251643Pi1Pi211345941351882623711718422426228求得最优顺序下的Fmax＝28Johnson算法的改进•1.将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；•2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；•3.将A放到B之前，就构成了一个最优加工顺序。J1J2J3J4J5J6机器A518534机器B722474○○○○○○ai≤bi工件按ai值不减的顺序（由小到大）排列：J2–J5–J6-J1；ai＞bi的工件按bi值不增的顺序（由大到小）排列：J4－J3最后排序J2–J5–J6-J1-J4－J3三、m(m≥3)台机器排序问题的算法一般采用启发式算法解决这类问题。•斜度指标法•关键工件法•CDS法（一）Palmer（斜度指标法）•工件的斜度指标计算公式Pikmkmk12/)1(k＝1，2，……m式中，m机器数；Pik为工件i在Mk上的加工时间。按照各工件λi不增的顺序排列工件，可得出令人满意的顺序。•λi=举例有一个4/3/F/Fmax问题，其加工时间如下表所示，用Palmer法求解。i1234Pi1Pi2Pi3126384294582•λi＝•＝-Pi1+Pi3•λ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）Pikkk312/)13(k=1，2，3i1234Pi1Pi2Pi311236931289413215924413518826228Fmax=28i2134Pi1Pi2Pi322136931246814216925511418826228Fmax=28加工顺序（1，2，3，4）或（2，1，3，4）（二）关键工件法•1、计算Pi=,找出其中最大者，定义为关键工件Jc。2、除Jc外，将满足Pi1≦Pim的工件，按Pi1值的大小，从小到大排在Jc的前面。3、除Jc外，将满足pi1pim的工件，按Pim值的大小，从大到小排在Jc的后面。mjPij1i1234Pi1Pi2Pi3126384294582Pi13111614（1）工件3加工时间最长，作为关键工件。（2）满足Pi1Pi3的工件有1、2，按Pi1值由小到大排在3的前面，1-2-3。（3）满足pi1pi3的工件是4，将4排在3的后面。所以加工顺序为（1，2，3，4）。i1234Pi1Pi2Pi311236931289413215924413518826228举例J1J2J3J4J5J6机器1pi15541210机器2pi25553610机器3pi3833474机器4pi4282156机器5pi55212810总和252315112840具体过程（1）找出关键工件：工作负荷最大的40，对应的是工件6，Jc=J6（2）满足Pi1≦Pi5的工件有J1、J4、J5,按Pi1值由小到大排在关键工件前面，所以有J4–J5–J1-J6（3）满足pi1pi5的工件有J2、J3，按Pi5值由大到小排在关键工件的后面,所以有–J6–J2–J3J4–J5–J1–J6–J2–J3Fmax=51（三）CDS法Campbell,Dudek,Smith三人于1970年共同提出了一个启发式算法，简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到（m一1)个加工顺序，取其中优者。具体做法是，对加工时间和（l=1，2，…，m-1），用Johnson算法求（m-1)次加工顺序，取其中最好的结果。lkPik1mlmkPik1i1234l=1Pi11263Pi34582l=2Pi1+Pi296812Pi2+Pi31291011举例当l＝1时，按Johnson算法得到加工顺序（1，2，3，4）i1234Pi1Pi2Pi311236931289413215924413518826228Fmax=28当l=2时，得到加工顺序(2，3，1，4)对于顺序（2，3，1，4）i2314Pi1Pi2Pi322681931246210818927511819423229Fmax=29所以，取顺序（1，2，3，4）四、相同零件、不同移动方式下加工周期的计算1、顺序移动一批零件在上道工序全部加工完毕后才整批转移到下道工序继续加工。一批零件的加工周期为：工序的单件加工时间第零件加工的工序数零件加工批量＝顺imnnttTimii1例：已知n=4,t1=10分，t2＝5分钟，t3＝15分钟，t4＝10分钟，求T顺t1t4t2t3工序4060120160T顺＝4×(10+5+15+10)=160（分钟）2、平行移动方式每个零件在前道工序加工完毕后，立即转移到下道工序继续加工，形成前后交叉作业。一批零件的加工周期为：最长的单件工序时间平tttTLLmiin)1(1T平＝（10＋5＋15＋10）＋（4-1)×15=85(分钟）t1t3时间t4t23075853、平顺移动方式当t1ti+1时，零件按平行移动方式转移；当t1≥ti+1时，以I工序最后一个零件的完工时间为准，往前推移（n-1)×ti+1,作为零件在（i+1)工序的开工时间。一批零件的加工周期为：),min()1(1111tttTjmjjmiinn＝平顺t1t4t3工序时间t2100160T平顺＝4×（10＋5＋15＋10）－（4－1）×（5＋5＋10）＝100（分钟）三种移动方式的比较移动方式顺序移动平行移动平行顺序移动优缺点（1）管理简单，设备不停歇，可充分负荷。（2）有等待现象，加工周期长。（1）周期最短，（2）零件等待少，设备有停歇。（3）运输频繁，管理复杂。两者结合,扬长避短适用条件小而轻；单件小批；加工时间短，调整时间长；工艺专业化。大且重；大量大批；加工时间长，调整时间短；对象专业化。小而轻；大量大批；加工时间长，调整时间短；对象专业化。练习题：设某种零件批量为5件，加工工序数为4，每道工序单件加工时间为t1=6小时，t2=10小时，t3=8小时t4=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道工序,各工序的单件工时分别为:t1=5分,t2=2分,t3=5分,t4=3分,t5=4分,试计算该批零件不同移动方式的生产周期(工序间其他时间不计).