流水作业的排序问题课件.ppt

1、第八章第八章 流水作业的排序问题流水作业的排序问题一、排序问题的基本概念一、排序问题的基本概念 排序排序是确定工件（零部件）在一台是确定工件（零部件）在一台或一组设备上加工的先后顺序。或一组设备上加工的先后顺序。在一定约束条件下，寻找总加工时在一定约束条件下，寻找总加工时间最短的安排产品加工顺序的方法，就间最短的安排产品加工顺序的方法，就是是生产作业排序。生产作业排序。例如，考虑例如，考虑32项任务（工件），有项任务（工件），有32！2.6 1035种种方案方案,假定计算机每秒钟可以检查假定计算机每秒钟可以检查1 billion个顺序个顺序,全部检验完毕需要全部检验完毕需要8.4 1015个世

2、纪。个世纪。如果只有如果只有16个工件个工件,同样按每秒钟可以检查同样按每秒钟可以检查1 billion个顺序计算个顺序计算,也需要也需要2/3年。年。以上问题还没有考虑其他的约束条件以上问题还没有考虑其他的约束条件,如机器、人如机器、人力资源、厂房场地等，如果加上这些约束条件，所力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中所以，很有必要去寻找一些有效算法，解决管理中的实际问题。的实际问题。排序困难性排序困难性假设条件假设条件1.一个工件不能同时在几台不同的机器上加工。一个工件不能同时在几台不同的机器上

3、加工。2.工件在加工过程中采取平行移动方式，即当上一道工工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。序完工后，立即送下道工序加工。3.不允许中断。当一个工件一旦开始加工，必须一直进不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。行到完工，不得中途停止插入其它工件。4.每道工序只在一台机器上完成。每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺工件数、机器数和加工时间已知，加工时间与加工顺序无关。序无关。6.每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。排序常用的符号排序常用的符号 Ji

4、-工件工件i，i=1,2,.n。Mj-机器机器j，j1，2，m.di-工件工件Ji 的完工期限。的完工期限。pij-工件工件Ji在机器在机器Mj上的加工时间上的加工时间,j=1,m Pi-工件工件Ji的加工时间的加工时间,wij-工件工件Ji在机器在机器Mj前的等待时间前的等待时间,j=1,m Wi-工件工件Ji在加工过程中总的等待时间在加工过程中总的等待时间,Ci-工件工件Ji 的完成时间的完成时间,Fi-工件工件Ji 的流程时间的流程时间，即工件在车间的实际停留时间即工件在车间的实际停留时间，在工在工件都已到达的情况下件都已到达的情况下,Fi=Pi+Wi Li-工件工件Ji 的延误时间的延

5、误时间,Li=Ci-di,Li0 延误延误 Fmax-最长流程时间，最长流程时间，FmaxmaxFi二、排序问题的分类和表示法二、排序问题的分类和表示法1、排序问题的分类：、排序问题的分类：根据机器数的多少根据机器数的多少 单台机器的排序问题单台机器的排序问题 多台机器的排序问题多台机器的排序问题 根据加工路线的特征根据加工路线的特征 单件作业排序单件作业排序(Job Shop)流水作业排序流水作业排序(Flow Shop)根据工件到达系统的情况根据工件到达系统的情况 静态排序静态排序 动态排序动态排序 根据参数的性质根据参数的性质 确定型排序确定型排序 随机型排序随机型排序 根据要实现的目标

6、根据要实现的目标 单目标排序单目标排序 多目标排序多目标排序 2、排序问题的表示法排序问题的表示法排序问题常用四个符号来描述排序问题常用四个符号来描述:n/m/A/B其中其中,n-工件数；工件数；m-机器数；机器数；A-车间类型；车间类型；F=流水型排序，流水型排序，P=排列排序排列排序 G=一般类型一般类型,即单件型排序即单件型排序 B-目标函数目标函数三、流水作业排序问题三、流水作业排序问题 1、最长流程时间、最长流程时间Fmax的计算的计算举例：有一个举例：有一个6/4/p/Fmax问题，其加工时问题，其加工时间如下表所示。当按顺序间如下表所示。当按顺序S（6，1，5，2，4，3）加工时

7、，求加工时，求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 3Pi1Pi2Pi3pi42 4 4 2 1 35 4 4 5 7 65 5 5 8 5 71 4 3 2 3 4最长流程时间的计算271213610121316111520273317223035422125323846最长流程时间的计算 举例2 i 1 4 6 3 5 2 Pi1 4 5 3 4 8 6 Pi2 3 9 1 3 7 5 Pi3 7 6 8 2 5 9 Pi4 5 6 3 9 2 44912162

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

9、。列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。找出作业时间最小者。(3)如果该最小值是在设备如果该最小值是在设备1上，将对应的工件排在上，将对应的工件排在前面，如果该最小值是在设备前面，如果该最小值是在设备2上，则将对应的工件上，则将对应的工件排在后面。排在后面。(4)排除已安排好的工件，在剩余的工件中重复步排除已安排好的工件，在剩余的工件中重复步骤骤(2)和和(3)，直到所有工件都安排完毕。，直到所有工件都安排完毕。举例举例 AB两台设备完成两台设备完成5个零件的加工任务，每个个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总工件在设备上的加工时间如下表所示。求总

10、加工周期最短的作业顺序。加工周期最短的作业顺序。设备设备工件编号工件编号J1J2J3J4J5设备设备A36715设备设备B28643求解过程求解过程由约翰逊法可知，表由约翰逊法可知，表5-8中最小加工时间值是中最小加工时间值是1个时间单位，它又是个时间单位，它又是出现在设备出现在设备1上，根据约翰逊法的规则，应将对应的工件上，根据约翰逊法的规则，应将对应的工件4排在排在第一位，即得：第一位，即得：J4-*-*-*-*去掉去掉J4，在剩余的工件中再找最小值，不难看出，最小值是在剩余的工件中再找最小值，不难看出，最小值是2个个时间单位，它是出现在设备时间单位，它是出现在设备2上的，所以应将对应的工

11、件上的，所以应将对应的工件J1排排在最后一位，即：在最后一位，即：J4-*-*-*-J1 再去掉再去掉J1，在剩余的在剩余的J2、J3、J5中重复上述步骤，求解过程为：中重复上述步骤，求解过程为：J4-*-*-J5-J1 J4-J2-*-J5-J1 J4-J2-J3-J5-J1 当同时出现多个最小值时，可从中任选一个。最后得当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J1(a)J1-J2-J3-J4-J5 30AB(b)J4-J2-J3-J5-J1 26AB比较比较 可以看出，初始作业顺序的总加工周期可以看出，初始作业顺序的总加工周期是是30，用约翰逊法排出的作业顺序

12、总加工，用约翰逊法排出的作业顺序总加工周期是周期是26，显然后者的结果优于前者。，显然后者的结果优于前者。将工件2排在第1位 2将工件3排在第6位 2 3将工件5排在第2位 2 5 3将工件6排在第3位 2 5 6 3将工件4排在第5位 2 5 6 4 3将工件1排在第4位 2 5 6 1 4 3最优加工顺序为S=(2,5,6,1,4,3),Fmax=28I 1 2 3 4 5 6Ai 5 1 8 5 3 4Bi 7 2 2 4 7 4两台机器排序问题的算法（续）Johnson算法的改进 1.将所有ai bi的工件按ai值不减的顺序排成一个序列A；2.将aibi的工件按bi值不增的顺序排成一个

13、序列B；3.将A放到B之前，就构成了一个最优加工顺序。改进算法举例工件号 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 最优顺序：2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 2 ai bi 最优顺序下的加工周期为最优顺序下的加工周期为28148131826311152226283、m(m 3)台机器排序问题台机器排序问题的算法的算法 一般采用启发式算法解决这类问一般采用启发式算法解决这类问题。题。关键工件法关键工件法 斜度指标法斜度指标法 CDS法法（1）关键工件法）关键工件法1、计算计算 Pi=,找出其中最大者，定义为关键工件找出

14、其中最大者，定义为关键工件Jc。2、除除Jc外，将满足外，将满足Pi1pim的工件，按的工件，按Pim值的大小，值的大小，从大到小排在从大到小排在Jc的后面。的后面。4、除、除Jc外，将满足外，将满足Pi1=Pim的工件，排在的工件，排在Jc的前面或者的前面或者后面后面 步骤步骤5 如有多个方案，可再加比较，从中选优。如有多个方案，可再加比较，从中选优。mjPij1举例举例J1J2J3J4J5J6机器机器1pi15541210机器机器2pi25553610机器机器3pi3833474机器机器4pi4282156机器机器5pi5 5212810总和总和252315112840具体过程具体过程找出

15、关键工件：工作负荷最大的找出关键工件：工作负荷最大的40，对应的是工件，对应的是工件6，所以所以 Jc=J6 确定排在关键工件前面的工件：满足步骤确定排在关键工件前面的工件：满足步骤2条件的有条件的有J4,J5,所以有所以有 J4 J5 J6 确定排在关键工件后面的工件：满足步骤确定排在关键工件后面的工件：满足步骤3条件的有条件的有J2,J3,所以有所以有 J6 J2 J3满足步骤满足步骤4条件的有条件的有J1,所以有所以有 J6 J1，或者或者J1 J6最后有：最后有：J4 J5 J6 J1 J2 J3，或或 J4 J5 J1 J6 J2 J3关键工件法（续）工件i 1 2 3 4Pi1 2

16、 1 6 3Pi2 4 8 2 9Pi3 5 4 8 211 13 16 14JCSa(2,1)Sb(4)所求顺序：（2,1,3,4）练习练习J1J2J3J4J5J6机器机器1pi1835424机器机器2pi2282156机器机器3pi35212810机器机器4pi45541710总和总和20181282230练习练习J5J2J6J1J3J4机器机器1pi1234854机器机器2pi2586221机器机器3pi38210512机器机器4pi4751054125917222671522152123252717313637392741465051练习练习J1J2J3J4J5J6机器机器1pi183

17、5424机器机器2pi2282156机器机器3pi35212810机器机器4pi4554171081116202226101520192122273321222435452630314255(2)Palmer（斜度指标法）斜度指标法）i=Pikmkmk12/)1(工件的斜度指标计算公式工件的斜度指标计算公式k1，2，m式中，式中，m机器数；机器数；Pik为工件为工件i在在Mk上上的加工时间。的加工时间。举例举例有一个有一个4/3/P/Fmax问题，其加工时间如下问题，其加工时间如下表所示，用表所示，用Palmer法求解。法求解。i1 2 3 4Pi1Pi2Pi31 2 6 38 4 2 94

18、5 8 2求解过程 求解过程求解过程 i -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），），Fmax=28Pikkk312/)13(k=1，2，3 计算计算Fmaxi1 2 3 4Pi1Pi2Pi31 2 6 38 4 2 94 5 8 213912913152413182628（3）CDS法法Campbell,Dudek,Smith三人于1970年共同提出了一个启发式算法，简称CDS

19、法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到（m一1)个加工顺序，取其中优者。具体做法是，对加工时间 和（l=1，2，m-1），用Johnson算法求（m-1)次加工顺序，取其中最好的结果。lkPik1mlmkPik1举例举例有一个有一个4/3/P/Fmax问题，其加工时间如下问题，其加工时间如下表所示，用表所示，用Palmer法求解。法求解。i1 2 3 4Pi1Pi2Pi31 2 6 38 4 2 94 5 8 2 i1 2 3 4l=1 Pi11 2 6 3 Pi34 5 8 2l=2 Pi1+Pi29 6 8 12 Pi2+Pi312 9 10 11举例举例 当

20、当l1时，按时，按Johnson算法得到加工顺算法得到加工顺序（序（1，2，3，4）；当）；当l=2时，得到加时，得到加工顺序工顺序(2，3，1，4)。对于顺序（。对于顺序（2，3，1，4），相应的），相应的Fmax=29。所以，取所以，取顺序（顺序（1，2，3，4）。）。三种方法比较三种方法比较 以上三种方法，优度最高的是以上三种方法，优度最高的是CDS法，法，其次是关键工件法，其次是关键工件法，Palmer法最低。法最低。从计算工作量来讲，关键工件法最简从计算工作量来讲，关键工件法最简便，便，Palmer法次之，法次之，CDS最复杂。最复杂。四、相同零件不同移动方式下加工周期的计算 当n个

21、零件相同，则无排序问题。但不同移动方式下的加工周期不同 三种典型的移动方式顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工平行移动方式：单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式：两者混合服务业企业作业排序问题服务业企业作业排序问题服务作业排序与生产作业排序的主要区别服务作业排序与生产作业排序的主要区别l 所提供产品的类型所提供产品的类型 由于服务过程有顾客参与由于服务过程有顾客参与,作业排序对他们有直接影响作业排序对他们有直接影响,并因并因此成为服务的一部分此成为服务的一部分,而在生产作业排序对产品的最终使用而在生产作业排序对产品的最终使用者没有直接影响。者没有直

22、接影响。l l 排序内容排序内容 在服务业中在服务业中,排序要定义服务交易的时间或消耗点；而在制造排序要定义服务交易的时间或消耗点；而在制造业中仅仅定义产品生产的操作步骤。业中仅仅定义产品生产的操作步骤。l 过程控制过程控制 在服务业中在服务业中,顾客参与服务过程顾客参与服务过程,并且对全部操作过程施加影响。并且对全部操作过程施加影响。l 人员规模人员规模 在顾客化服务中在顾客化服务中,服务的输出与劳动力的最佳服务的输出与劳动力的最佳规模之间的关系很难确定；而生产作业中规模之间的关系很难确定；而生产作业中,两者两者之间的关系有紧密联系之间的关系有紧密联系,因此最佳的作业顺序可因此最佳的作业顺序

23、可以被计算出来以被计算出来。服务作业排序方法之一服务作业排序方法之一安排顾客需求安排顾客需求 预约：如医生、律师等的服务预约：如医生、律师等的服务 预定：顾客预定旅馆房间、火车或飞机票预定：顾客预定旅馆房间、火车或飞机票 排队等待：一种为顾客排序的不太准确的排队等待：一种为顾客排序的不太准确的方法是允许需求积压，让顾客排队等待。方法是允许需求积压，让顾客排队等待。例如，餐馆、银行、零售商店等。例如，餐馆、银行、零售商店等。服务作业排序方法之二服务作业排序方法之二安排服务人员安排服务人员 当需要快速响应顾客需求、且需求当需要快速响应顾客需求、且需求量大致可以预计时，通常使用这种量大致可以预计时，通常使用这种方法。如邮局营业员、护士、警察方法。如邮局营业员、护士、警察的工作日和休息日安排；一天营业的工作日和休息日安排；一天营业24小时、一周小时、一周7天都营业的商店保天都营业的商店保安人员安排；等等安人员安排；等等。