流水作业的排序问题.ppt

《流水作业的排序问题.ppt》由会员分享，可在线阅读，更多相关《流水作业的排序问题.ppt（43页珍藏版）》请在装配图网上搜索。

1、第九章 流水作业的排序问题,9.1 排序问题概述 9.2 流水作业排序问题,9.1 排序问题概述 一、排序问题的基本概念 排序是确定工件（零部件）在一台或一组设备 上加工的先后顺序。 在一定约束条件下，寻找总加工时间最短的安 排产品加工顺序的方法，就是生产作业排序。,例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.41015个世纪. 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，

2、所需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,假设条件,1.一个工件不能同时在几台不同的机器上加工。 2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。 3.不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。 4.每道工序只在一台机器上完成。 5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。 6.每台机器同时只能加工一个工件。,排序常用的符号,Ji-工件i，i=1,2,.n。 Mj - 机器j，j1，2，m. pij-工件Ji在机器Mj上的加工时间,j=1,m Pi-工件Ji的加工时

3、间； di-工件Ji 的完工期限； Ci-工件Ji 的完成时间； Fi-工件Ji 的流程时间，即工件在车间的实际停留时间，在工件都已到达的情况下, Fi= Pi+ Wi Wi-工件Ji在加工过程中总的等待时间 Li-工件Ji 的延误时间, Li= Ci- di , Li0 延误 Fmax-最长流程时间， FmaxmaxFi,二、排序问题的分类和表示法,1、排序问题的分类： (1)根据机器数的多少 单台机器的排序问题 多台机器的排序问题 (2)根据加工路线的特征 单件作业排序(Job Shop)：工件加工路线不同 流水作业排序(Flow Shop)：所有工件加工路线完全相同 (3) 根据工件到达

4、系统的情况 静态排序：进行排序时，所有工件都已到达，可以一次对他们排序 动态排序：工件陆续到达，要随时安排他们的加工顺序,（4）根据参数的性质 确定型排序：指加工时间和其他参数是已知确定的量 随机型排序：指加工时间和有关参数为随机变量 （5）根据要实现的目标 单目标排序 多目标排序,2、排序问题的表示法,排序问题常用四个符号来描述: n/m/A/B 其中, n-工件数； m-机器数； A-车间类型； F流水作业排序， P流水作业排列排序 G一般类型,即单件型排序 B-目标函数,9.2 流水作业排序问题,一、最长流程时间Fmax的计算 工件 Si在机器MK 上的完工时间为CKSi 工件 Si在机

5、器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。,二、两台机器排序问题,两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短 。 实现两台机器排序的最大完成时间Fmax最短的目标，一优化算法就是著名的约翰逊法(Johnsons Law)。其具体求解过程如下例所示。,约翰逊贝尔曼法则,约翰逊法解决这种问题分为4个步骤： (1)列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。

6、 (3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。 (4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。,举例 AB两台设备完成6个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,机器,工件编 号,求解过程,由约翰逊法可知，表中最小加工时间值是1个时间单位,出现在设备1上，根据约翰逊法的规则，应将对应的工件2排在第一位，即得： J2- * - * - * - * -* 去掉J2，在剩余的工件中再找最小值，最小值是2个时间单位，它是出现在设备2上，所以应将对应的工件J3

7、排在最后一位，即： 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- J4J3或 J2 J5 J1-J6 - J4J3,求得最优顺序下的Fmax28,Johnson算法的改进,1. 将所有ai bi的工件按ai值不减的顺序排成一个序列A； 2. 将aibi的工件按bi值不增的顺序排成一个序列B；

8、3. 将A放到B之前，就构成了一个最优加工顺序。,ai bi工件按ai值不减的顺序（由小到大）排列 ： J2 J5 J6- J1 ； aibi的工件按bi值不增的顺序（由大到小）排列： J4J3 最后排序 J2 J5 J6- J1- J4J3,三、m(m 3)台机器排序问题的算法,一般采用启发式算法解决这类问题。 斜度指标法 关键工件法 CDS法,（一）Palmer（斜度指标法）,工件的斜度指标计算公式,k1，2，m 式中，m机器数；Pik为工件i在Mk上的加工时间。 按照各工件i不增的顺序排列工件，可得出令人满意 的顺序。,i=,举例,有一个4/3/F/Fmax问题，其加工时间如下表所示，用

9、Palmer法求解。,i -Pi1+Pi3 1-P11+P13= -143 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）,k=1，2，3,Fmax=28,Fmax=28 加工顺序（1，2，3，4）或（2，1，3，4）,（二）关键工件法,1、 计算 Pi= , 找出其中最大者，定义为关键工件 Jc。 2、除Jc外，将满足Pi1Pim的工件，按Pi1值的 大小，从小到大排在Jc的前面。 3 、除Jc外，将满足pi1pim的工件，按Pim值的大小，从大到小排在

10、Jc的后面。,（1）工件3加工时间最长，作为关键工件。 （2）满足Pi1pi3的工件是4，将4排在3的后面。 所以加工顺序为（1，2，3，4）。,举例,具体过程,（1）找出关键工件：工作负荷最大的40，对应的是工 件 6， Jc=J6 （2）满足Pi1Pi5的工件有J1 、J4、J5, 按Pi1值由小到大排在关键工件前面，所以有 J4 J5 J1 -J6 （3）满足pi1pi5的工件有J2、J3，按Pi5值由大到小排在关键工件的后面, 所以有 J6 J2 J3 J4 J5 J1 J6 J2 J3 Fmax=51,（三）CDS法,Campbell, Dudek, Smith三人于1970年共同提

11、出了一个启发式算法，简称CDS法。他们把Johnson算法用于一般的n /m /P/Fmax问题，得到（m一1)个加工顺序，取其中优者。 具体做法是，对加工时间 和 （l=1，2，m-1），用Johnson算法求（m-1)次加工顺序，取其中最好的结果。,举例,当l1时，按Johnson算法得到加工顺序 （1，2，3，4）,Fmax=28,当l=2时，得到加工顺序(2，3，1，4) 对于顺序（2，3，1，4）,Fmax=29 所以，取顺序（1，2，3，4）,四、相同零件、不同移动方式下加工周期的计算 1、顺序移动 一批零件在上道工序全部加工完毕后才整批转移到下道工序继续加工。一批零件的加工周期为

12、：,例：已知n=4,t1=10分，t25分钟，t315分钟， t410分钟，求T顺,T顺4(10+5+15+10)=160（分钟）,2、平行移动方式 每个零件在前道工序加工完毕后，立即转移到下道工序继续加工，形成前后交叉作业。一批零件的加工周期为：,T平（1051510）（4-1) 15 = 85 (分钟）,3、平顺移动方式 当t1ti+1时，零件按平行移动方式转移； 当t1ti+1时，以I工序最后一个零件的完工时间为准，往前推移（n-1) ti+1,作为零件在（i+1)工序的开工时间。一批零件的加工周期为：,T平顺4 （1051510）（41）（5510） 100（分钟）,三种移动方式的比较,练习题： 设某种零件批量为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分,试计算该批零件不同移动方式的生产周期(工序间其他时间不计).,