[精选]作业排序与生产作业计划培训课件.pptx

第第 十十 章章 作业排序与生产作业计划作业排序与生产作业计划第一节第一节 作业排序的基本概念作业排序的基本概念第二节第二节 流水作业排序问题流水作业排序问题第三节第三节 单件作业排序问题单件作业排序问题 第四节第四节 多台设备作业排序多台设备作业排序4/17/20231引引 言言 在确定了各车间的零部件投入、出产计划、将全厂的生产计划变成了各车间的生产任务后,各车间还应将零部件的投入、出产计划变成车间的作业计划，即将车间的生产任务变成各工段、班组、各工作地的生产任务。编制车间生产作业计划，应该解决工件加工顺序问题。这就是我们要讨论的作业排序问题。采用排序理论与方法，可以得出工件加工的最优或令人满意的顺序。第一节第一节 作业排序的基本概念作业排序的基本概念4/17/20232一、编制生产作业计划与排序的关系一、编制生产作业计划与排序的关系编制生产作业计划与作业排序不同，排序只是确定工件在机器上的加工顺序，可以用一组工件的代号的排列来表示这组工件的加工顺序，而编制生产作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。所以，只有生产作业计划才能指导工人的生产活动。在编制生产作业计划时常常出现一个工件在某道工序加工完之后，加工它的下一道工序的机器还在加工前一个工件，这时该工件不得不等待一段时间才能开始在下一道工序的机器上加工。这种情况称为“工件等待”。当某台机器已加工完一个工件，而下一个工件尚未到达。这种情况称为“机器空闲”。第一节第一节 作业排序的基本概念作业排序的基本概念4/17/20233由于编制生产作业计划的主要问题是确定各台机器上工件的加工顺序，并且一般都是按最早可能开工时间或最早可能完工时间来编制生产作业计划。所以，当工件的加工按一定的时间确定了加工顺序后，作业计划也就确定了。这就造成了人们通常不加区别的使用“排序”与“编制作业计划”两个术语。第一节第一节 作业排序的基本概念作业排序的基本概念4/17/20234几个名词术语排序工件在机器上的加工顺序派工将生产任务安排到具体机床上加工调度范围；赶工实际进度落后于计划进度时采取的行动调度范围；调度发现实际进度落后于计划进度时而采取的调配资源的行动。机器服务者工件服务对象加工路线工件加工的工艺过程工序加工路线上的每一个具体工作地（机器）。4/17/20235 1.1.一个工件不能同时在几台不同的机器上被加工。一个工件不能同时在几台不同的机器上被加工。一个工件不能同时在几台不同的机器上被加工。一个工件不能同时在几台不同的机器上被加工。2.2.采取平行移动方式移送被加工的工件。采取平行移动方式移送被加工的工件。采取平行移动方式移送被加工的工件。采取平行移动方式移送被加工的工件。3.3.不允许中断。当一个工件一旦开始加工不允许中断。当一个工件一旦开始加工不允许中断。当一个工件一旦开始加工不允许中断。当一个工件一旦开始加工,必须一直进行到必须一直进行到必须一直进行到必须一直进行到完工完工完工完工,不得中途停止插入其它工件。不得中途停止插入其它工件。不得中途停止插入其它工件。不得中途停止插入其它工件。4.4.工件在每道工序的加工只在一台机器上进行。工件在每道工序的加工只在一台机器上进行。工件在每道工序的加工只在一台机器上进行。工件在每道工序的加工只在一台机器上进行。5.5.工件数（或批量）、机器数已知，单件加工时间已知工件数（或批量）、机器数已知，单件加工时间已知工件数（或批量）、机器数已知，单件加工时间已知工件数（或批量）、机器数已知，单件加工时间已知,完完完完成加工的时间与加工顺序无关。成加工的时间与加工顺序无关。成加工的时间与加工顺序无关。成加工的时间与加工顺序无关。6.6.每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。第一节第一节 作业排序的基本概念作业排序的基本概念二、假设条件与符号说明二、假设条件与符号说明 为了便于采用数学模型来分析研究排序问题，做下列假设：为了便于采用数学模型来分析研究排序问题，做下列假设：为了便于采用数学模型来分析研究排序问题，做下列假设：为了便于采用数学模型来分析研究排序问题，做下列假设：4/17/20236第一节第一节 作业排序的基本概念作业排序的基本概念符号说明符号说明Wi=m j=1Wij Ji第i工件，i=1,2,n；Mj第 j台机器，j=1,2,m；(i,j,k)Ji的第j道工序在Mk上进行；Pi=mj=1PijPijJi在Mj上的加工时间，加工时间，加工时间，加工时间，Ji加工完的总加工时间；ri Ji 到达工序时间到达工序时间到达工序时间到达工序时间，即可以开始加工的最早时间；di Ji 的完工期限完工期限完工期限完工期限；aiJi 在车间允许停留的时间车间允许停留的时间车间允许停留的时间车间允许停留的时间（Ji 进入车间到完工时刻之间的时间间隔：ai=di ri）；Wij Ji 在第j 道工序前的等待时间工序前的等待时间工序前的等待时间工序前的等待时间，Ji 总的等待时间：4/17/20237Ci=ri+(Pij+Wij)=ri+Pi+WiLi=Ci di=ri+Pi+Widi=(Pi+Wi)(di ri)=FiaiFi=Ciri=Pi+Wi;第一节第一节 作业排序的基本概念作业排序的基本概念CiJi 的完工时间Cmax 最长完工时间,Cmax=maxCi,即一批工件中的最长完工时间;Fi Ji 的流程时间,即工件在车间的实际停留时间,Fmax 最长流程时间,Fmax=maxFi,即一批工件中的最长流程时间;Li Ji 工件的延迟时间，4/17/20238第一节第一节 作业排序的基本概念作业排序的基本概念当Li 0 时为正延迟,即Ji 的实际完工时间超过了完工期限;当Li 0 时为正延迟,即Ji 的实际完工时间超过了完工期限;当Li0 时为负延迟,即Ji 提前完工;当Li=0 时为零延迟,即Ji 按期完工。例如：例如：n/3/P/Cmax 表示n个工件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间最短。4/17/202315 流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件,遇到的就是流水作业排序问题。我们说加工路线一致,是指工件的流向一致,并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工,则设相应的加工时间为零。一般说来,对于流水作业排序问题,工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况,即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作同顺序排序问题。对于一般情形,排列排序问题的最优解不一定是相应的流水作业排序问题的最优解,但一般是比较好的解;对于仅有2台和3台机器的特殊情况,可以证明,排列排序问题下的最优解一定是相应流水作业排序问题的最优解。本节只讨论排列排序问题。但对于2台机器的排序问题,实际上不只是排列排序问题，因为两者的最优解及其解法是相同的。第二节第二节 流水作业排序问题流水作业排序问题4/17/202316一、最长流程时间Fmax的计算最长流程时间就是工件在车间实际停留的最长时间。最长流程时间就是工件在车间实际停留的最长时间。最长流程时间就是工件在车间实际停留的最长时间。最长流程时间就是工件在车间实际停留的最长时间。本节所讨论的是n/m/Fmax问题,目标函数是使最长流程时间最短。最长流程时间又称作加工周期,它是从第一个工件在第一台机器开始加工时算起,到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(r=0，i=1,2,n),所以Fmax等于排在末位加工的工件在车间的停留时间,也等于一批工件的最长完工时间Cmax。第二节第二节 流水作业排序问题流水作业排序问题4/17/202317设n个工件的加工顺序为S=(S1,S2,Sn),其中Si为排第i位加工的工件的代号。以Ck(si)表示工件Si 在机器Mk上的完工时间,Psik表示工件Si 在Mk上的加工时间,k=1,2,m；i=1,2,n则Ck(si)可按以下公式计算:C1(si)=C1(si-1)+Psi1 Ck(si)=maxCk-1(si),Ck(si-1)+Psik (111)第二节第二节 流水作业排序问题流水作业排序问题显然，当ri=0时，Fmax=Cm(sn)在知道了上述计算Fmax公式后，便可直接在工件加工的时间矩阵上从左向右计算完工时间。4/17/202318第二节第二节 流水作业排序问题流水作业排序问题例11.1有一个6/4/p/Fmax问题,其加工时间如下表所示。当按顺序S=(6,1,5,2,4,3)加工时,求Fmax表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi44243314/17/202319i i6 61 15 52 24 43 3Pi1Pi12 24 44 42 21 13 3Pi2Pi25 54 44 45 57 76 6Pi3Pi35 55 55 58 85 57 7Pi4Pi41 14 43 32 23 34 4表11-2顺序S下的加工时间矩阵2 26 610101212131316167 711111515202027273333121217172222303035354242131321212525323238384646Fmax=464/17/202320 Johnson Johnson算法算法算法算法:(1)(1)从加工时间矩阵中找出最短的加工时间。从加工时间矩阵中找出最短的加工时间。从加工时间矩阵中找出最短的加工时间。从加工时间矩阵中找出最短的加工时间。(2)(2)若最短的加工时间出现在若最短的加工时间出现在若最短的加工时间出现在若最短的加工时间出现在M1M1上上上上,则对应的工件尽可能往前排；则对应的工件尽可能往前排；则对应的工件尽可能往前排；则对应的工件尽可能往前排；若最短加工时间出现在若最短加工时间出现在若最短加工时间出现在若最短加工时间出现在M2M2上，则对应工件尽可能往后排。上，则对应工件尽可能往后排。上，则对应工件尽可能往后排。上，则对应工件尽可能往后排。然后然后然后然后,从加工时间矩阵中划去已排序工件的加工时间。若最从加工时间矩阵中划去已排序工件的加工时间。若最从加工时间矩阵中划去已排序工件的加工时间。若最从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个短加工时间有多个短加工时间有多个短加工时间有多个,则任挑一个往前排。则任挑一个往前排。则任挑一个往前排。则任挑一个往前排。(3)(3)若所有工件都已排序若所有工件都已排序若所有工件都已排序若所有工件都已排序,停止停止停止停止.否则否则否则否则,转步骤转步骤转步骤转步骤(1).(1).第二节第二节 流水作业排序问题流水作业排序问题二、二、二、二、n/2/F/Fmaxn/2/F/Fmax问题的最优算法问题的最优算法问题的最优算法问题的最优算法4/17/202321第二节第二节 流水作业排序问题流水作业排序问题二、n/2/F/Fmax问题的最优算法例11.2求表1-所示的6/Fmax问题的最优解。i iaiaibibi表11-3加工时间矩阵5 56 61414191922222626131315151717232330303434Fmax0(1,2,3,4,5,6)=344/17/202322i iaiaibibi表11-4改进算法见教材303页Johnson改进算法：.将所有aibi的工件按ai值不减的顺序排成一个列；.将所有aibi的工件按bi值不增的顺序排成一个列；.将放到之前，就构成了最优加工顺序(1)(1)(2)(2)(3)(3)(4(4)A=(2,5,6,1)A=(2,5,6,1)(5)(5)(6)(6)B=(4,3)B=(4,3)S=(2,5,6,1,4,3)S=(2,5,6,1,4,3)i iaiaibibi1 14 48 81313181826263 311111515232327272929Fmax*(2,5,6,1,4,3)=294/17/202323当我们从应用Johnson法则求得的最优顺序中任意去掉一些工件时,余下的工件仍构成最优顺序。如对例11.2的最优顺序(2,5,6,1,4,3),若去掉一些工件,得到的顺序(5,6,1,4,3)、(2,6,4,3)、(2,6,1,4)等仍为余下工件的最优顺序。但是,工件的加工顺序不能颠倒,否则不一定是最优顺序。同时,我们还要指出,Johnson 法则只是一个充分条件,不是必要条件。不符合这个法则的加工顺序,也可能是最优顺序。对例11.2顺序(2,5,6,4,1,3)不符合Johnson法则,但它也是一个最优顺序。第二节第二节 流水作业排序问题流水作业排序问题4/17/202324例11.2顺序(2,5,6,4,1,3)i iaiaibibi31481318261115192729Fmax*(2,5,6,4,1,3)=294/17/202325第二节第二节 流水作业排序问题流水作业排序问题三、一般n/m/P/Fmax问题的启发式算法对于3台机器的流水车间排序问题,只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题,可以用分支定界法。用分支定界法可以保证得到一般n/m/P/Fmax问题的最优解。但对于实际生产中规模较大的问题,计算量相当大,以至连电子计算机也无法求解。同时,还需考虑经济性。如果为了求最优解付出的代价超过了这个最优解所带来的好处,也是不值得的。为了解决生产实际中的排序问题,人们提出了各种启发式算法。启发式算法以小的计算量得到足够好的结果,因而十分适用。下面介绍求一般n/m/p/Fmax问题近优解(Nearoptimalsolution)的启发式算法。4/17/202326第二节第二节 流水作业排序问题流水作业排序问题(一)帕尔姆(Palmer)法1965年,D.S.Palmer提出按工件斜度指标排序的启发式算法。设：工件的斜度指标为 i ，k为笫k台设备，m为设备数，P i k为i工件在Mk上加工时间，k为设备的任意序数，（k=1,2,3,m）i=m k=1k（m+1）/2P ik从该式中求出各工件的 i，再按着不使 i 增加的原则排列各个工件的加工顺序，就可以得出令人满意的结果。4/17/2023271 13 39 912129 91515131324241313262618182828工件i设备工时1234Pi11263Pi28429Pi34582表表表表11-5 11-5 加工时间矩阵加工时间矩阵加工时间矩阵加工时间矩阵例例例例11.3 11.3 有一个有一个有一个有一个4/3/F/Fmax4/3/F/Fmax排序问题（即排序问题（即排序问题（即排序问题（即4 4个工件个工件个工件个工件3 3台设备，流水作台设备，流水作台设备，流水作台设备，流水作业排序问题，目标是使最长流程时间最短），各个工件在每台业排序问题，目标是使最长流程时间最短），各个工件在每台业排序问题，目标是使最长流程时间最短），各个工件在每台业排序问题，目标是使最长流程时间最短），各个工件在每台设备上的加工时间如下面的加工时间矩阵表所示，试采用设备上的加工时间如下面的加工时间矩阵表所示，试采用设备上的加工时间如下面的加工时间矩阵表所示，试采用设备上的加工时间如下面的加工时间矩阵表所示，试采用 PalmerPalmer法求解。法求解。法求解。法求解。Fmax=284/17/202328按照排序为：按照排序为：S=（2，1，3，4）工件i设备工时2134Pi12163Pi24829Pi3548223912614162511182628Fmax=284/17/202329第二节第二节 流水作业排序问题流水作业排序问题 解：由 i=m k=1k（m+1）/2Pik可知(见教材304页)按照按照按照按照 i i从大到小的顺序排列就是最优排列顺序。从大到小的顺序排列就是最优排列顺序。从大到小的顺序排列就是最优排列顺序。从大到小的顺序排列就是最优排列顺序。最优排列顺序最优排列顺序最优排列顺序最优排列顺序S=S=（1 1，2 2，3 3，4 4）或：或：或：或：S=S=（2 2，1 1，3 3，4 4）4/17/202330P322习题习题2：请用帕尔玛法排序并计：请用帕尔玛法排序并计算最长流程时间算最长流程时间i i i iK K K K 1 1 1 1 2 2 2 2 3 3 3 34 4 4 4K-(m+1)/2K-(m+1)/2K-(m+1)/2K-(m+1)/2(K-(K-(K-(K-(m+1)/2)(m+1)/2)(m+1)/2)(m+1)/2)*P1k*P1k*P1k*P1k(K-(K-(K-(K-(m+1)/2)(m+1)/2)(m+1)/2)(m+1)/2)*P2k*P2k*P2k*P2k(K-(K-(K-(K-(m+1)/2)(m+1)/2)(m+1)/2)(m+1)/2)*P3k*P3k*P3k*P3k(K-(K-(K-(K-(m+1)/2)(m+1)/2)(m+1)/2)(m+1)/2)*P4k*P4k*P4k*P4kPikPikPikPik1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 54 4 4 4-1.5-1.5-1.5-1.5-1.5-1.5-1.5-1.5-13.5-13.5-13.5-13.5-7.5-7.5-7.5-7.5-6-6-6-6PikPikPikPik2 2 2 2 5 5 5 5 7 7 7 7 6 6 6 63 3 3 3-0.5-0.5-0.5-0.5-2.5-2.5-2.5-2.5-3.5-3.5-3.5-3.5-3-3-3-3-1.5-1.5-1.5-1.5PikPikPikPik3 3 3 3 4 4 4 4 6 6 6 6 3 3 3 35 5 5 50.50.50.50.52 2 2 23 3 3 31.51.51.51.52.52.52.52.5PikPikPikPik4 4 4 4 6 6 6 6 2 2 2 2 3 3 3 37 7 7 71.51.51.51.59 9 9 93 3 3 34.54.54.54.510.510.510.510.5m=4m=4Ai=(K-(m+1)/2)*P1kAi=(K-(m+1)/2)*P1kAi=(K-(m+1)/2)*P1kAi=(K-(m+1)/2)*P1k7 7 7 7-11-11-11-11-4.5-4.5-4.5-4.55.55.55.55.5求解过程：求解过程：求解过程：求解过程：排序为：排序为：S=(1,4,3,2)4/17/202331按照S=(1,4,3,2)计算最长流程时间：i1432Pik1459Pik5367Pik4536Pik67321510192669161015193216232634Fmax=344/17/202332(二)关键工件法关键工件法是1983年提出的一个启发式算法。其步骤如下:(1)计算每个工件的总加工时间P i=Pij,找出总加工时间最长的工件C(j=1.2.3.m),将其作为关键工件。(2)对于余下的工件,若Pi1Pim,则按Pi1不减的顺序排成一个序列Sa；若Pi1Pim，则按Pim不增的顺序排列成一个序列Sb。(3)顺序(sa,C,Sb )即为所求顺序（近优解）。第二节第二节 流水作业排序问题流水作业排序问题4/17/202333表11-6工件在每台设备上的单件工时与总工时(见教材305页)第二节第二节 流水作业排序问题流水作业排序问题例：有4个工件，在3台设备上加工，每个工件在每台设备上加工的单件工时消耗如表11-6所示。试采用关键工件法求近优解（近优排序）。i=1,2,3,4；m=1,2,3工件i1234Pi11263Pi28429Pi34582PiPi131311111616141431244/17/202334解：（1）计算每个工件的总加工时间，填写在表11-6上，分别为（13,11,16,14），可见总加工时间最长的工件为3号工件，总加工时间P3=16。（2）余下的工件为1,2,4号工件，Pi1Pi3的工件为1,2号；按Pi1不减（相等或增加）(P11=1,P21=2)的顺序排成一个序列Sa=（1,2）；Pi1Pim的工件为4号工件，按Pim不增（相等或减少）顺序排成一个序列Sb=(4)（只有一个工件）。（3）近优解的顺序（Sa,C,Sb）为（工件1,2,3,4）第二节第二节 流水作业排序问题流水作业排序问题4/17/202335表11-6工件在每台设备上的单件工时与总工时工件i1234Pi11263Pi28429Pi345821 13 39 912129 91313151524241313181826262828FmaxFmax计算过程计算过程计算过程计算过程4/17/202336P322习题习题2：请用关键工件法排序并：请用关键工件法排序并计算最长流程时间计算最长流程时间i i i i1 1 1 12 2 2 23 3 3 34 4 4 4Pi1Pi1Pi1Pi11 1 1 19 9 9 95 5 5 54 4 4 4Pi2Pi2Pi2Pi25 5 5 57 7 7 76 6 6 63 3 3 3Pi3Pi3Pi3Pi34 4 4 46 6 6 63 3 3 35 5 5 5Pi4Pi4Pi4Pi46 6 6 62 2 2 23 3 3 37 7 7 7时间求和时间求和时间求和时间求和16161616242424241717171719191919排序为：排序为：排序为：排序为：S=S=（1 1，4 4，2 2，3 3）关键工件法求解过程如下：关键工件法求解过程如下：关键工件法求解过程如下：关键工件法求解过程如下：4/17/202337按照按照S=（1，4，2，3）计算最长流程时间）计算最长流程时间i i i i1 1 1 14 4 4 42 2 2 23 3 3 3Pi1Pi1Pi1Pi11 1 1 14 4 4 49 9 9 95 5 5 5Pi2Pi2Pi2Pi25 5 5 53 3 3 37 7 7 76 6 6 6Pi3Pi3Pi3Pi34 4 4 45 5 5 56 6 6 63 3 3 3Pi4Pi4Pi4Pi46 6 6 67 7 7 72 2 2 23 3 3 31514196921271015273016232933Fmax=334/17/202338(三)CDS法(Campbell,Dudek,Smith三人提出)(见教材305页)第二节第二节 流水作业排序问题流水作业排序问题 工件i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+Pi31291011表11-7用CDS法求解L=1时：按照时：按照Johnson法得到加工顺序为：1，2，3，4L=2时：按照时：按照Johnson法得到加工顺序为：2，3，1，44/17/2023398 89 912126 61818101027271111232319192929Fmaxmax计算如下表所示计算如下表所示计算如下表所示计算如下表所示F Fmax=29max=29 若加工顺序为（若加工顺序为（若加工顺序为（若加工顺序为（2 2，3 3，1 1，4 4）时，按）时，按）时，按）时，按JohnsonJohnson算法算法算法算法Fmax=29Fmax=29，所以取加工顺序（所以取加工顺序（所以取加工顺序（所以取加工顺序（1 1，2 2，3 3，4 4）Fmax=28 Fmax=28为最优解。为最优解。为最优解。为最优解。工件i设备工时2314Pi12613Pi24289Pi35842第二节第二节 流水作业排序问题流水作业排序问题2 24/17/202340P322习题习题2：请用：请用CDS法排序并计算法排序并计算最长流程时间最长流程时间i i i i1 1 1 12 2 2 23 3 3 34 4 4 4Pi1Pi1Pi1Pi11 1 1 19 9 9 95 5 5 54 4 4 4Pi2Pi2Pi2Pi25 5 5 57 7 7 76 6 6 63 3 3 3Pi3Pi3Pi3Pi34 4 4 46 6 6 63 3 3 35 5 5 5Pi4Pi4Pi4Pi46 6 6 62 2 2 23 3 3 37 7 7 7关键工件法求解过程如下：关键工件法求解过程如下：关键工件法求解过程如下：关键工件法求解过程如下：4/17/202341排序为：排序为：S1=（1，4，3，2）i i i i1 1 1 12 2 2 23 3 3 34 4 4 4L=1L=1Pi1Pi1Pi1Pi11 1 1 19 9 9 95 5 5 54 4 4 4Pi4Pi4Pi4Pi46 6 6 62 2 2 23 3 3 37 7 7 7i i i i1 1 1 12 2 2 23 3 3 34 4 4 4Pi1Pi1Pi1Pi11 1 1 19 9 9 95 5 5 54 4 4 4Pi2Pi2Pi2Pi25 5 5 57 7 7 76 6 6 63 3 3 3Pi3Pi3Pi3Pi34 4 4 46 6 6 63 3 3 35 5 5 5Pi4Pi4Pi4Pi46 6 6 62 2 2 23 3 3 37 7 7 71、L=1时：时：4/17/202342排序为：排序为：S1=（1，4，3，2）i i i i1 1 1 14 4 4 43 3 3 32 2 2 2Pi1Pi1Pi1Pi11 1 1 14 4 4 45 5 5 59 9 9 9Pi2Pi2Pi2Pi25 5 5 53 3 3 36 6 6 67 7 7 7Pi3Pi3Pi3Pi34 4 4 45 5 5 53 3 3 36 6 6 6Pi4Pi4Pi4Pi46 6 6 67 7 7 73 3 3 32 2 2 21510196916261015193216232634Fmax=344/17/202343排序为：排序为：排序为：排序为：S1=S1=（1 1，4 4，2 2，3 3）i i i i1 1 1 12 2 2 23 3 3 34 4 4 4L=L=2 2Pi1Pi1Pi1Pi16 6 6 616161616111111117 7 7 7Pi4Pi4Pi4Pi4101010108 8 8 86 6 6 612121212i i i i1 1 1 12 2 2 23 3 3 34 4 4 4Pi1Pi1Pi1Pi11 1 1 19 9 9 95 5 5 54 4 4 4Pi2Pi2Pi2Pi25 5 5 57 7 7 76 6 6 63 3 3 3Pi3Pi3Pi3Pi34 4 4 46 6 6 63 3 3 35 5 5 5Pi4Pi4Pi4Pi46 6 6 62 2 2 23 3 3 37 7 7 72 2、L=2L=2时：时：时：时：4/17/202344排序为：排序为：S1=（1，4，2，3）i i i i1 1 1 14 4 4 42 2 2 23 3 3 3Pi1Pi1Pi1Pi11 1 1 14 4 4 49 9 9 95 5 5 5Pi2Pi2Pi2Pi25 5 5 53 3 3 37 7 7 76 6 6 6Pi3Pi3Pi3Pi34 4 4 45 5 5 56 6 6 63 3 3 3Pi4Pi4Pi4Pi46 6 6 67 7 7 72 2 2 23 3 3 31514196921271015273016232933Fmax=334/17/202345排序为：排序为：排序为：排序为：S1=S1=（1 1，4 4，2 2，3 3）i i i i1 1 1 12 2 2 23 3 3 34 4 4 4L=L=3 3Pi1Pi1Pi1Pi11010222214141212Pi4Pi4Pi4Pi41515151512121515i i i i1 1 1 12 2 2 23 3 3 34 4 4 4Pi1Pi1Pi1Pi11 1 1 19 9 9 95 5 5 54 4 4 4Pi2Pi2Pi2Pi25 5 5 57 7 7 76 6 6 63 3 3 3Pi3Pi3Pi3Pi34 4 4 46 6 6 63 3 3 35 5 5 5Pi4Pi4Pi4Pi46 6 6 62 2 2 23 3 3 37 7 7 73 3、L=3L=3时：时：时：时：4/17/202346排序为：排序为：S1=（1，4，2，3）i i i i1 1 1 14 4 4 42 2 2 23 3 3 3Pi1Pi1Pi1Pi11 1 1 14 4 4 49 9 9 95 5 5 5Pi2Pi2Pi2Pi25 5 5 53 3 3 37 7 7 76 6 6 6Pi3Pi3Pi3Pi34 4 4 45 5 5 56 6 6 63 3 3 3Pi4Pi4Pi4Pi46 6 6 67 7 7 72 2 2 23 3 3 31514196921271015273016232933Fmax=33所以最终排序为：所以最终排序为：S1=（1，4，2，3）满意解。）满意解。4/17/202347三、采用三、采用三、采用三、采用JohnsonJohnson法则解决多个工件在三台设备上的作业排序法则解决多个工件在三台设备上的作业排序法则解决多个工件在三台设备上的作业排序法则解决多个工件在三台设备上的作业排序 若存在一个若存在一个若存在一个若存在一个n/3/P/Fmaxn/3/P/Fmax问题，且问题，且问题，且问题，且mint1i mint1i maxt2i maxt2i 或或或或mint3i mint3i mint2i(mint2i(i=1i=1，2 2，n)n)，则可采用，则可采用，则可采用，则可采用JohnsonJohnson法排序。法排序。法排序。法排序。求解步骤为：求解步骤为：求解步骤为：求解步骤为：（1 1）先找出）先找出）先找出）先找出mint1i mint1i maxt2imaxt2i或或或或mint3i mint3i mint2imint2i关系关系关系关系 （2 2）将）将）将）将3 3台设备变换成台设备变换成台设备变换成台设备变换成2 2台假想设备台假想设备台假想设备台假想设备MAMA和和和和MBMB，并令，并令，并令，并令 tAi=t1i+t2i tAi=t1i+t2i ；tBi=t2i+t3i tBi=t2i+t3i （3 3）依据）依据）依据）依据 tAi tAi 和和和和tBitBi，采用，采用，采用，采用JohnsonJohnson法则进行作业排序法则进行作业排序法则进行作业排序法则进行作业排序试采用试采用试采用试采用JohnsonJohnson法则进行作业排序法则进行作业排序法则进行作业排序法则进行作业排序工工工工 件件件件设设设设 备备备备J J1 1J J2 2 J J3 3 J J4 4MM1 115158 86 61212MM2 23 31 1 5 5 6 6MM3 34 410105 57 7表表表表11-17 11-17 加工时间表加工时间表加工时间表加工时间表例：有一个例：有一个例：有一个例：有一个4/3/P/Fmax4/3/P/Fmax问题，其加工时间如表问题，其加工时间如表问题，其加工时间如表问题，其加工时间如表11-1711-17所示所示所示所示4/17/202348解：解：解：解：mint1i mint1i=6 =6 maxt2i maxt2i=6 =6 存在存在存在存在mint1i mint1i maxt2i maxt2i mint3i mint3i=4 =4 mint2i mint2i=1 =1 存在存在存在存在mint3i mint3i mint2i mint2i 可采用可采用可采用可采用JohnsonJohnson法求解该作业排序问题法求解该作业排序问题法求解该作业排序问题法求解该作业排序问题(具备其一即可具备其一即可具备其一即可具备其一即可)。计算计算计算计算tAi tAi 和和和和tBitBi，列于表，列于表，列于表，列于表11-1811-18中中中中表表表表11-18 11-18 t tAiAi 、t tBi Bi 与排序结果与排序结果与排序结果与排序结果工件设备J1J2J3J4(MA)tAi1891118(MB)tBi，7111013排序结果J2J4J3J1t1i812615t2i1653t3i107548 82020262641419 92626313144441919333338384848 依据依据依据依据11-1811-18中的中的中的中的t tAiAi 和和和和t tBiBi，采用采用采用采用JohnsonJohnson法进行作业排序。排序结果与法进行作业排序。排序结果与法进行作业排序。排序结果与法进行作业排序。排序结果与F Fmaxmax如表如表如表如表11-1811-18及图及图及图及图11-411-4所示。所示。所示。所示。F Fmax max=48=484/17/202349J2J4J3J181261516538920263141448202641107549192633384448M1M2M3时间图11-4排序结果甘特图4/17/202350单件作业排序是最一般的排序问题，也是最复杂的一种排序问题。该问题本身容易表达，也能看出该问题所需要求解的是什么，但是朝着求解方向作任何推进都是极为困难的。许多人在此问题上都进行了探索，但一无所获者大有人在。第三节第三节 单件作业排序问题单件作业排序问题4/17/202351第三节第三节 单件作业排序问题单件作业排序问题一、问题的描述一、问题的描述对一般的单件作业排序问题，每个工件都有其独特的加工路对一般的单件作业排序问题，每个工件都有其独特的加工路线，工件没有一定的流向。但是，对于流水作业的排序问题，第线，工件没有一定的流向。但是，对于流水作业的排序问题，第k k道道工序永远在工序永远在MMK K上上进行，没有必要将工序号与机器号分开。而对于一进行，没有必要将工序号与机器号分开。而对于一般的单件作业排序问题，要描述一道工序需要般的单件作业排序问题，要描述一道工序需要i i、j j、k k三个参数，即三个参数，即i i、j j、k k表示第表示第i i个工件的第个工件的第j j道工序在道工序在MMk k(第第k k台机器上台机器上)上进行的。所以，上进行的。所以，可以用加工描述矩阵的形式来描述所有工件的加工。加工描述矩阵可以用加工描述矩阵的形式来描述所有工件的加工。加工描述矩阵的形式如加工描述矩阵的形式如加工描述矩阵D D所示。所示。加工描述矩阵的每一行描述一个工件的加工过程加工描述矩阵的每一行描述一个工件的加工过程(第第1 1行描述第一个工件的加工行描述第一个工件的加工过程，第二行描述第过程，第二行描述第2 2个工件的加工过程个工件的加工过程)。D D的每一组数中的第的每一组数中的第1 1列数表示工件序列数表示工件序号；号；D D的每组数中的第的每组数中的第2 2列数码相同，说明第列数码相同，说明第2 2列表示工序号；列表示工序号；D D的每一组数中的第的每一组数中的第3 3列数表示设备序号。列数表示设备序号。4/17/202352第三节第三节 单件作业排序问题单件作业排序问题 二、一般n/m/G/Fmax问题的启发式算法n/m/G/Fmax为n个工件，m台机器，一般单件作业排序问题，使最大流程时间最短。对这类作业排序问题，可以用分支定界法或整数规划法求最优解。但是，都是无效的方法。为此，在实际工作中，多采用启发式算法。为了对研究启发式算法有所帮助，先介绍两种十分重要的作业计划及其构成方法。4/17/202353 (一一一一)两种作业计划的构成两种作业计划的构成两种作业计划的构成两种作业计划的构成 一般说来，在可行的加工顺序下，可以拟定出无数种作业计划。一般说来，在可行的加工顺序下，可以拟定出无数种作业计划。一般说来，在可行的加工顺序下，可以