《第九章 流水作业的排序问题.ppt》由会员分享，可在线阅读，更多相关《第九章 流水作业的排序问题.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章第九章流水作业的排序问题流水作业的排序问题9.1 9.1 排序问题概述排序问题概述9.2 9.2 流水作业排序问题流水作业排序问题9.1 9.1 排序问题概述排序问题概述一、排序问题的基本概念一、排序问题的基本概念排序是确定工件（零部件）在一台或一组设备排序是确定工件（零部件）在一台或一组设备上加工的先后顺序。上加工的先后顺序。在一定约束条件下，寻找总加工时间最短的安在一定约束条件下，寻找总加工时间最短的安排产品加工顺序的方法，就是生产作业排序。排产品加工顺序的方法，就是生产作业排序。例如，考虑例如，考虑32项任务（工件），有项任务（工件），有32！2.6 1035种方案种方案,假定计算
2、机每秒钟可以检假定计算机每秒钟可以检查查1billion个顺序个顺序,全部检验完毕需要全部检验完毕需要8.4 1015个世纪个世纪.如果只有如果只有16个工件个工件,同样按每秒钟可以检查同样按每秒钟可以检查1billion个顺序计算个顺序计算,也需要也需要2/3年年.以上问题还没有考虑其他的约束条件以上问题还没有考虑其他的约束条件,如机如机器、人力资源、厂房场地等，如果加上这些器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决所以，很有必要去寻找一些有效算法，解决管理中的实际问题。管理中的实际问题
3、。假设条件假设条件1.一个工件不能同时在几台不同的机器上加工。一个工件不能同时在几台不同的机器上加工。2.工工件件在在加加工工过过程程中中采采取取平平行行移移动动方方式式，即即当当上上一一道道工工序完工后，立即送下道工序加工。序完工后，立即送下道工序加工。3.不不允允许许中中断断。当当一一个个工工件件一一旦旦开开始始加加工工，必必须须一一直直进进行到完工，不得中途停止插入其它工件。行到完工，不得中途停止插入其它工件。4.每道工序只在一台机器上完成。每道工序只在一台机器上完成。5.工工件件数数、机机器器数数和和加加工工时时间间已已知知，加加工工时时间间与与加加工工顺顺序无关。序无关。6.每台机器
4、同时只能加工一个工件。每台机器同时只能加工一个工件。排序常用的符号排序常用的符号 Ji-Ji-工件工件i i，i=1,2,.ni=1,2,.n。Mj Mj-机器机器j j，j j1 1，2 2，m.m.pijpij-工件工件JiJi在机器在机器MjMj上的加工时间上的加工时间,j=1,j=1,m,m Pi-Pi-工件工件J Ji i的加工时间；的加工时间；di-di-工件工件J Ji i 的完工期限；的完工期限；Ci-Ci-工件工件J Ji i 的完成时间；的完成时间；Fi-Fi-工件工件J Ji i 的流程时间的流程时间，即工件在车间的实际停留即工件在车间的实际停留时间时间，在工件都已到达的
5、情况下在工件都已到达的情况下,Fi=Pi+WiFi=Pi+Wi Wi-工件工件Ji在加工过程中总的等待时间在加工过程中总的等待时间 Li-Li-工工件件J Ji i 的的延延误误时时间间,Li=Li=Ci-Ci-di di,Li=0 Li0 Li0 延误延误 Fmax-Fmax-最长流程时间，最长流程时间，FmaxFmaxmaxFimaxFi二、排序问题的分类和表示法二、排序问题的分类和表示法1、排序问题的分类：、排序问题的分类：(1)根据机器数的多少根据机器数的多少单台机器的排序问题单台机器的排序问题多台机器的排序问题多台机器的排序问题(2)根据加工路线的特征根据加工路线的特征单件作业排序单
6、件作业排序(JobShop)：工件加工路线不同工件加工路线不同流水作业排序流水作业排序(FlowShop)：所有：所有工件加工路线完全相同工件加工路线完全相同(3)根据工件到达系统的情况根据工件到达系统的情况静态排序：静态排序：进行排序时，所有工件都已到达，可以一次对他们排序进行排序时，所有工件都已到达，可以一次对他们排序动态排序：动态排序：工件陆续到达，要随时安排他们的加工顺序工件陆续到达，要随时安排他们的加工顺序（4）根据参数的性质）根据参数的性质确定型排序：确定型排序：指加工时间和其他参数是已知确定的量指加工时间和其他参数是已知确定的量随机型排序：随机型排序：指加工时间和有关参数为随机变
7、量指加工时间和有关参数为随机变量（5）根据要实现的目标）根据要实现的目标单目标排序单目标排序多目标排序多目标排序2、排序问题的表示法排序问题的表示法排序问题常用四个符号来描述排序问题常用四个符号来描述:n/m/A/B其中其中,n-工件数；工件数；m-机器数；机器数；A-车间类型；车间类型；F流水作业排序，流水作业排序，P流水作业排列排序流水作业排列排序G一般类型一般类型,即单件型排序即单件型排序B-目标函数目标函数9.2流水作业排序问题流水作业排序问题一、一、最长流程时间最长流程时间Fmax的计算的计算工件工件Si在机器MK 上的完工时间为CKSi工件工件Si在机器MK 上的加工时间为PSiK
8、 C1Si=C1Si-1+PSi1 CKSi=max C(k-1)Si(k-1)Si,CkSi-1kSi-1+PSikSik举例：有一个举例：有一个6/4/p/Fmax问题，其加工时间如下问题，其加工时间如下表所示。当按顺序表所示。当按顺序S（6，1，5，2，4，3）加工时，求加工时，求Fmax。i1 2 3 4 5 6Pi1Pi2Pi3pi44 2 3 1 4 24 5 6 7 4 55 8 7 5 5 54 2 4 3 3 1i6 1 5 2 4 3Pi1Pi2Pi3pi422 4 6 410 212 113 31657 4 11 415 520 727 633512 517 5 22 8
9、 30 535 742 113 4 21 325 2 32 338 446二、两台机器排序问题二、两台机器排序问题两台机器排序的目标是使最大完成时间（总两台机器排序的目标是使最大完成时间（总加工周期）加工周期）Fmax最短最短。实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间Fmax最短最短的目标，一优化算法就是著名的约翰逊法的目标，一优化算法就是著名的约翰逊法(JohnsonsLaw)。其具体求解过程如下例其具体求解过程如下例所示。所示。约翰逊贝尔曼法则约翰逊贝尔曼法则约翰逊法解决这种问题分为约翰逊法解决这种问题分为4个步骤：个步骤：(1)列出所有工件在两台设备上的作业时间。列出
10、所有工件在两台设备上的作业时间。(2)找出作业时间最小者。找出作业时间最小者。(3)如如果果该该最最小小值值是是在在设设备备1上上，将将对对应应的的工工件件排排在在前前面面，如如果果该该最最小小值值是是在在设设备备2上上，则则将对应的工件排在后面。将对应的工件排在后面。(4)排除已安排好的工件，在剩余的工件中排除已安排好的工件，在剩余的工件中重复步骤重复步骤(2)和和(3)，直到所有工件都安排完，直到所有工件都安排完毕。毕。举例举例ABAB两台设备完成两台设备完成6 6个零件的加工任务，每个工个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总加件在设备上的加工时间如下表所示。求总加工
11、周期最短的作业顺序。工周期最短的作业顺序。J1J2J3J4J5J6机器机器A A518534机器机器B B722474机器机器工件工件编编号号求解过程求解过程由由约约翰翰逊逊法法可可知知，表表中中最最小小加加工工时时间间值值是是1个个时时间间单单位位,出出现现在在设设备备1上，根据约翰逊法的规则，应将对应的工件上，根据约翰逊法的规则，应将对应的工件2排在第一位，即得：排在第一位，即得：J2-*-*-*-*-*去去掉掉J2，在在剩剩余余的的工工件件中中再再找找最最小小值值，最最小小值值是是2个个时时间间单单位位，它它是出现在设备是出现在设备2上，所以应将对应的工件上，所以应将对应的工件J3排在最
12、后一位，即：排在最后一位，即：J2-*-*-*-*J3再去掉再去掉J3，在剩余的在剩余的J1、J4、J5、J6中重复上述步骤，求解过程为：中重复上述步骤，求解过程为：J2J5-*-*-*-J3J2J5J6-*-*J3J2J5J6-*-J4J3J2J5J6J1-J4J3当同时出现多个最小值时，可从中任选一个。当同时出现多个最小值时，可从中任选一个。J2J5J6-J1-J4J3或或J2J5J1-J6-J4J3i2 5 6 1 4 3Pi1Pi211 34 48 513 518 82623 7 11 415 722 426 228i2 5 1 6 4 3Pi1Pi211 34 59 413 518
13、82623 7 11 718 422 426 228求得最优顺序下的求得最优顺序下的Fmax28 Johnson算法的改进1.将所有ai bi的工件按ai值不减的顺序排成一个序列A；2.将aibi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。J1J2J3J4J5J6机器机器A A518534机器机器B B722474aibi工件按工件按ai值不减的顺序（由小到大）排列值不减的顺序（由小到大）排列：J2J5J6-J1；aibi的工件按的工件按bi值不增的顺序（由大到小）排列：值不增的顺序（由大到小）排列：J4J3最后排序最后排序J2J5J6-J1-J4J3
14、三、三、m(mm(m 3)3)台机器排序问题的算法台机器排序问题的算法一般采用启发式算法解决这类问题。一般采用启发式算法解决这类问题。斜度指标法斜度指标法关键工件法关键工件法CDS法法（一）（一）Palmer（斜度指标法）斜度指标法）工件的斜度指标计算公式工件的斜度指标计算公式k1，2，m式中，式中，m机器数；机器数；Pik为工件为工件i在在Mk上的加工时间。上的加工时间。按照各工件按照各工件i不增的顺序排列工件，可得出令人满意不增的顺序排列工件，可得出令人满意的顺序。的顺序。i=举例举例有一个有一个4/3/F/Fmax问题，其加工时间如下问题，其加工时间如下表所示，用表所示，用Palmer法
15、求解。法求解。i1 2 3 4Pi1Pi2Pi31 2 6 38 4 2 94 5 8 2i-Pi1+Pi31-P11+P13=-1432-P21+P23=-2+5=33-P31+P33=-6+8=24-P41+P43=-3+2=-1按按i不增的顺序排列工件，得到加工顺序不增的顺序排列工件，得到加工顺序（1，2，3，4）或（）或（2，1，3，4）k=1，2，3i1 2 3 4 Pi1Pi2Pi311 2 3 69 312 89 4 13 215 924 413 518 8 26 2 28 Fmax=28i2 1 3 4 Pi1Pi2Pi322 13 69 312 46 814 216 925
16、511 418 8 26 2 28 Fmax=28加工顺序（加工顺序（1，2，3，4）或（）或（2，1，3，4）（二）关键工件法（二）关键工件法1、计算计算Pi=,找出其中最大者，定义为关键工件找出其中最大者，定义为关键工件Jc。2、除、除Jc外，将满足外，将满足Pi1Pim的工件，按的工件，按Pi1值的值的大小，从小到大排在大小，从小到大排在Jc的前面。的前面。3、除、除Jc外，将满足外，将满足pi1pim的工件，按的工件，按Pim值的大值的大小，从大到小排在小，从大到小排在Jc的后面。的后面。i1 2 3 4Pi1Pi2Pi31 2 6 38 4 2 94 5 8 2Pi13 11 16
17、14（1 1）工件）工件3 3加工时间最长，作为关键工件。加工时间最长，作为关键工件。（2 2）满足满足Pi1pi3的工件是的工件是4，将，将4排在排在3的后面。的后面。所以加工顺序为（所以加工顺序为（1，2，3，4）。）。i1 2 3 4 Pi1Pi2Pi311 2 3 69 312 89 4 13 215 924 413 518 8 26 2 28 举例举例J1J2J3J4J5J6机器机器1 1pi15541210机器机器2 2pi25553610机器机器3 3pi3833474机器机器4 4pi4282156机器机器5 5pi55212810总和总和252315112840具体过程具体过
18、程（1）找出关键工件：工作负荷最大的）找出关键工件：工作负荷最大的40，对应的是工，对应的是工件件6，Jc=J6（2）满足）满足Pi1Pi5的工件有的工件有J1、J4、J5,按按Pi1值由小到值由小到大大排在关键工件前面，所以有排在关键工件前面，所以有J4J5J1-J6（3）满足）满足pi1pi5的工件有的工件有J2、J3，按，按Pi5值由大到小值由大到小排在排在关键工件的后面关键工件的后面,所以有所以有J6J2J3J4J5J1J6J2J3Fmax=51（三）（三）CDS法法 Campbell,Dudek,Smith Campbell,Dudek,Smith三人于三人于19701970年共同年
19、共同提出了一个启发式算法，简称提出了一个启发式算法，简称CDSCDS法。他们把法。他们把JohnsonJohnson算法用于一般的算法用于一般的n/m/P/Fmaxn/m/P/Fmax问题，得到问题，得到（m m一一1)1)个加工顺序，取其中优者。个加工顺序，取其中优者。具体做法是，对加工时间具体做法是，对加工时间 和和 （l l=1=1，2 2，m-1m-1），用用JohnsonJohnson算算法法求求（m-1)m-1)次加工顺序，取其中最好的结果。次加工顺序，取其中最好的结果。i1234l=1 Pi11263 Pi34582l=2 Pi1+Pi296812 Pi2+Pi31291011举
20、例举例当当l1时，按时，按Johnson算法得到加工顺序算法得到加工顺序（1，2，3，4）i1 2 3 4 Pi1Pi2Pi311 2 3 69 312 89 4 13 215 924 413 518 8 26 2 28 Fmax=28当当l=2时，得到加工顺序时，得到加工顺序(2，3，1，4)对于顺序（对于顺序（2，3，1，4）i2 3 1 4 Pi1Pi2Pi322 6 8 19 312 46 2 10 818 927 511 819 423 2 29 Fmax=29所以，取顺序（所以，取顺序（1，2，3，4）四、相同零件、不同移动方式下加工周期的计算四、相同零件、不同移动方式下加工周期的
21、计算1 1、顺序移动、顺序移动 一批零件在上道工序全部加工完毕后才整批转移到下一批零件在上道工序全部加工完毕后才整批转移到下道工序继续加工。一批零件的加工周期为：道工序继续加工。一批零件的加工周期为：例：已知n=4,t1=10分，t25分钟，t315分钟，t410分钟，求T顺t1t4t2t3工序40 60 120 160T顺4(10+5+15+10)=160（分钟）2 2、平行移动方式、平行移动方式 每个零件在前道工序加工完毕后，立即转移到下道工每个零件在前道工序加工完毕后，立即转移到下道工序继续加工，形成前后交叉作业。一批零件的加工周期序继续加工，形成前后交叉作业。一批零件的加工周期为：为：
22、T平（1051510）（4-1)15 =85(分钟）t1t3时间t4t t2 230 75 853 3、平顺移动方式、平顺移动方式当当t1ti+1t1ti+1时，零件按平行移动方式转移；时，零件按平行移动方式转移；当当t1ti+1t1ti+1时，以时，以I I工序最后一个零件的完工时间为准，工序最后一个零件的完工时间为准，往前推移（往前推移（n-1)n-1)ti+1,ti+1,作为零件在（作为零件在（i+1)i+1)工序的开工序的开工时间。一批零件的加工周期为：工时间。一批零件的加工周期为：t1t4t3工序时间t2100 160T平顺4（1051510）（41）（5510）100（分钟）三种移
23、动方式的比较三种移动方式的比较三种移动方式的比较三种移动方式的比较移动方式移动方式移动方式移动方式顺序移动顺序移动顺序移动顺序移动平行移动平行移动平行移动平行移动平行顺序移动平行顺序移动平行顺序移动平行顺序移动优缺点优缺点优缺点优缺点（1 1 1 1）管理简单，）管理简单，）管理简单，）管理简单，设备不停歇，可设备不停歇，可设备不停歇，可设备不停歇，可充分负荷。充分负荷。充分负荷。充分负荷。（2 2 2 2）有等待现象，）有等待现象，）有等待现象，）有等待现象，加工周期长。加工周期长。加工周期长。加工周期长。（1 1 1 1）周期最短，）周期最短，）周期最短，）周期最短，（2 2 2 2）零件
24、等待少，）零件等待少，）零件等待少，）零件等待少，设备有停歇。设备有停歇。设备有停歇。设备有停歇。（3 3 3 3）运输频繁，）运输频繁，）运输频繁，）运输频繁，管理复杂。管理复杂。管理复杂。管理复杂。两者结合两者结合两者结合两者结合,扬长避短扬长避短扬长避短扬长避短适用条适用条件件小而轻；单件小小而轻；单件小小而轻；单件小小而轻；单件小批；加工时间短，批；加工时间短，批；加工时间短，批；加工时间短，调整时间长；工调整时间长；工调整时间长；工调整时间长；工艺专业化。艺专业化。艺专业化。艺专业化。大且重；大量大大且重；大量大大且重；大量大大且重；大量大批；加工时间长，批；加工时间长，批；加工时间
25、长，批；加工时间长，调整时间短；对调整时间短；对调整时间短；对调整时间短；对象专业化。象专业化。象专业化。象专业化。小而轻；大量大小而轻；大量大小而轻；大量大小而轻；大量大批；加工时间长，批；加工时间长，批；加工时间长，批；加工时间长，调整时间短；对调整时间短；对调整时间短；对调整时间短；对象专业化。象专业化。象专业化。象专业化。练习题：设某种零件批量为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分,试计算该批零件不同移动方式的生产周期(工序间其他时间不计).