第10章作业排序与生产作业计划

1、第 十 章 作业排序与生产作业计划第一节 作业排序的基本概念第二节 流水作业排序问题第三节 单件作业排序问题 第四节 多台设备作业排序7/23/20221引 言 在确定了各车间的零部件投入、出产计划、将全厂的生产计划变成了各车间的生产任务后,各车间还应将零部件的投入、出产计划变成车间的作业计划，即将车间的生产任务变成各工段、班组、各工作地的生产任务。编制车间生产作业计划，应该解决工件加工顺序问题。这就是我们要讨论的作业排序问题。采用排序理论与方法，可以得出工件加工的最优或令人满意的顺序。第一节 作业排序的基本概念7/23/20222一、编制生产作业计划与排序的关系 编制生产作业计划与作业排序不

2、同，排序只是确定工件在机器上的加工顺序，可以用一组工件的代号的排列来表示这组工件的加工顺序，而编制生产作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。所以，只有生产作业计划才能指导工人的生产活动。 在编制生产作业计划时常常出现一个工件在某道工序加工完之后，加工它的下一道工序的机器还在加工前一个工件，这时该工件不得不等待一段时间才能开始在下一道工序的机器上加工。这种情况称为“工件等待”。 当某台机器已加工完一个工件，而下一个工件尚未到达。这种情况称为“机器空闲”。第一节 作业排序的基本概念7/23/20223 由于编制生产作业计划的主要问题是确定各台机器上工

3、件的加工顺序，并且一般都是按最早可能开工时间或最早可能完工时间来编制生产作业计划。所以，当工件的加工按一定的时间确定了加工顺序后，作业计划也就确定了。这就造成了人们通常不加区别的使用“排序”与“编制作业计划”两个术语。第一节 作业排序的基本概念7/23/20224几个名词术语排序工件在机器上的加工顺序派工将生产任务安排到具体机床上加工调度范围；赶工实际进度落后于计划进度时采取的行动调度范围；调度发现实际进度落后于计划进度时而采取的调配资源的行动。机器服务者工件服务对象加工路线工件加工的工艺过程工序加工路线上的每一个具体工作地（机器）。7/23/20225 1. 一个工件不能同时在几台不同的机器

4、上被加工。 2. 采取平行移动方式移送被加工的工件。 3. 不允许中断。当一个工件一旦开始加工,必须一直进行到完工,不得中途停止插入其它工件。 4. 工件在每道工序的加工只在一台机器上进行。 5. 工件数（或批量）、机器数已知，单件加工时间已知, 完成加工的时间与加工顺序无关。 6. 每台机器同时只能加工一个工件。第一节 作业排序的基本概念二、假设条件与符号说明 为了便于采用数学模型来分析研究排序问题，做下列假设：7/23/20226第一节 作业排序的基本概念符号说明Wi = m j=1Wij Ji 第 i 工件，i = 1,2,n ； Mj 第 j 台机器，j =1,2,m；(i , j,

5、k) Ji 的第j 道工序在Mk上进行；Pi = mj=1PijPij Ji 在 Mj上的加工时间， Ji加工完的总加工时间；ri Ji 到达工序时间，即可以开始加工的最早时间；di Ji 的完工期限；ai Ji 在车间允许停留的时间（ Ji 进入车间到完工时刻之间的时间间隔： ai = di ri）；Wij Ji 在第 j 道工序前的等待时间， Ji 总的等待时间：7/23/20227Ci = ri +( Pij + Wij ) = ri + Pi + WiLi = Ci di = ri + Pi + Wi di = (Pi + Wi ) (di ri ) = Fi ai Fi = Ci r

6、i = Pi + Wi ;第一节 作业排序的基本概念Ci Ji 的完工时间Cmax 最长完工时间,Cmax = maxCi, 即一批工件中的最长完工时间; Fi Ji 的流程时间,即工件在车间的实际停留时间, Fmax 最长流程时间, Fmax = maxFi, 即一批工件中的最长流程时间;Li Ji 工件的延迟时间，7/23/20228第一节 作业排序的基本概念当 Li 0 时为正延迟, 即Ji 的实际完工时间超过了完工期限;当 Li 0 时为正延迟, 即Ji 的实际完工时间超过了完工期限; 当 Li 0 时为负延迟, 即Ji 提前完工; 当 Li = 0 时为零延迟, 即Ji 按期完工。例

7、如：n / 3 / P / Cmax 表示n 个工件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间最短。7/23/202215 流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件, 遇到的就是流水作业排序问题。我们说加工路线一致,是指工件的流向一致,并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工,则设相应的加工时间为零。 一般说来,对于流水作业排序问题, 工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况,即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作同顺

8、序排序问题。对于一般情形,排列排序问题的最优解不一定是相应的流水作业排序问题的最优解,但一般是比较好的解;对于仅有2台和3台机器的特殊情况,可以证明,排列排序问题下的最优解一定是相应流水作业排序问题的最优解。 本节只讨论排列排序问题。但对于2台机器的排序问题,实际上不只是排列排序问题，因为两者的最优解及其解法是相同的。第二节 流水作业排序问题7/23/202216一、最长流程时间Fmax的计算最长流程时间就是工件在车间实际停留的最长时间。本节所讨论的是n/m/Fmax问题,目标函数是使最长流程时间最短。最长流程时间又称作加工周期,它是从第一个工件在第一台机器开始加工时算起,到最后一个工件在最后

9、一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(r = 0，i = 1,2,n),所以Fmax等于排在末位加工的工件在车间的停留时间,也等于一批工件的最长完工时间Cmax。第二节 流水作业排序问题7/23/202217 设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), C

10、k(si-1) + Psik (11 1)第二节 流水作业排序问题显然，当ri = 0 时， Fmax = Cm(sn) 在知道了上述计算Fmax 公式后，便可直接在工件加工的时间矩阵上从左向右计算完工时间。7/23/202218第二节 流水作业排序问题例11.1有一个6/4/p/Fmax问题,其加工时间如下表所示。 当按顺序S=(6,1,5,2,4,3)加工时,求Fmax表11-1 加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi44243317/23/202219i615243Pi1244213Pi2544576Pi3555857Pi4143234表11

11、-2 顺序S下的加工时间矩阵261012131671115202733121722303542132125323846Fmax=467/23/202220 Johnson算法: (1) 从加工时间矩阵中找出最短的加工时间。 (2) 若最短的加工时间出现在M1上,则对应的工件尽可能往前排；若最短加工时间出现在M2上，则对应工件尽可能往后排。然后, 从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个, 则任挑一个往前排。 (3) 若所有工件都已排序, 停止.否则, 转步骤(1).第二节 流水作业排序问题二、n/2/F/Fmax问题的最优算法7/23/202221第二节 流水作业排序问题

12、二、n/2/F/Fmax问题的最优算法例11.2求表1-所示的6/Fmax问题的最优解。iaibi表11-3加工时间矩阵5614192226131517233034Fmax0(1,2,3,4,5,6)=347/23/202222iaibi表11-4 改进算法见教材303页 Johnson改进算法：.将所有aibi的工件按ai值不减的顺序排成一个列；.将所有aibi的工件按bi值不增的顺序排成一个列；.将放到之前，就构成了最优加工顺序(1)(2)(3)(4)A=(2,5,6,1)(5)(6)B=(4,3)S = ( 2, 5, 6, 1, 4, 3 )iaibi14813182631115232

13、729Fmax*(2,5,6,1,4,3)=297/23/202223 当我们从应用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法则, 但它也是一个最优顺

14、序。第二节 流水作业排序问题7/23/202224例11.2顺序(2,5,6,4,1,3)iaibi31481318261115192729Fmax*(2,5,6, 4,1, 3)=297/23/202225第二节 流水作业排序问题三、一般n/m/P/Fmax问题的启发式算法 对于3台机器的流水车间排序问题,只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题,可以用分支定界法。用分支定界法可以保证得到一般n/m/P/Fmax问题的最优解。但对于实际生产中规模较大的问题,计算量相当大,以至连电子计算机也无法求解。同时,还需考虑经济性。如果为了求最优解付出的代价超过了这个最优解所

15、带来的好处,也是不值得的。 为了解决生产实际中的排序问题,人们提出了各种启发式算法。启发式算法以小的计算量得到足够好的结果,因而十分适用。下面介绍求一般n/m/p/Fmax问题近优解(Near optimal solution)的启发式算法。7/23/202226第二节 流水作业排序问题 (一) 帕尔姆( 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，再

16、按着不使i 增加 的原则排列各个工件的加工顺序，就可以得出令人满意的结果。7/23/20222713912915132413261828工件i设备工时1234Pi11263Pi28429Pi34582表11-5 加工时间矩阵例11.3 有一个4/3/F/Fmax排序问题（即4个工件3台设备，流水作业排序问题，目标是使最长流程时间最短），各个工件在每台设备上的加工时间如下面的加工时间矩阵表所示，试采用 Palmer法求解。Fmax=287/23/202228按照排序为：S=（ 2，1，3，4）工件i设备工时2134Pi12163Pi24829Pi3548223912614162511182628

17、Fmax=287/23/202229第二节 流水作业排序问题 解：由 i = m k=1k（m+1）/2Pik可知(见教材304页)按照 i从大到小的顺序排列就是最优排列顺序。最优排列顺序S=（1，2，3，4）或：S=（ 2，1，3，4）7/23/202230P322习题2：请用帕尔玛法排序并计算最长流程时间iK1234K-(m+1)/2(K-(m+1)/2)*P1k(K-(m+1)/2)*P2k(K-(m+1)/2)*P3k(K-(m+1)/2)*P4kPik11954-1.5-1.5-13.5-7.5-6Pik25763-0.5-2.5-3.5-3-1.5Pik346350.5231.52

18、.5Pik462371.5934.510.5m=4Ai=(K-(m+1)/2)*P1k7-11-4.55.5求解过程：排序为：S=(1,4,3,2)7/23/202231按照 S=(1,4,3,2)计算最长流程时间：i1432Pik1459Pik5367Pik4536Pik67321510192669161015193216232634Fmax=347/23/202232 (二)关键工件法 关键工件法是1983年提出的一个启发式算法。其步骤如下:(1)计算每个工件的总加工时间P i= Pij, 找出总加工时间最长的工件 C(j=1. 2. 3. m), 将其作为关键工件。(2)对于余下的工件,

19、 若Pi1 Pim, 则按 Pi1不减的顺序排成一个序列Sa；若Pi1 Pim， 则按 Pim不增的顺序排列成一个序列Sb。 (3)顺序(sa, C, Sb )即为所求顺序（近优解）。第二节 流水作业排序问题7/23/202233表11- 6 工件在每台设备上的单件工时与总工时(见教材305页)第二节 流水作业排序问题例：有4个工件，在3台设备上加工，每个工件在每台设备上加工的单件工时消耗如表11-6所示。试采用关键工件法求近优解（近优排序）。i = 1,2,3,4； m=1,2,3工件i1234Pi11263Pi28429Pi34582Pi1311161431247/23/202234解：（

20、1）计算每个工件的总加工时间，填写在表11-6上，分别为（13,11,16,14），可见总加工时间最长的工件为3号工件，总加工时间P3=16。（2）余下的工件为1,2,4号工件， Pi1 Pi3的工件为1,2号；按 Pi1不减（相等或增加）(P11=1, P21=2)的顺序排成一个序列Sa=（1, 2）； Pi1 Pim的工件为4号工件，按Pim不增（相等或减少）顺序排成一个序列Sb= ( 4 ) （只有一个工件）。（3）近优解的顺序（ Sa ,C, Sb ）为（工件1,2,3 ,4）第二节 流水作业排序问题7/23/202235表11- 6 工件在每台设备上的单件工时与总工时工件i1234P

21、i11263Pi28429Pi3458213912913152413182628Fmax计算过程7/23/202236P322习题2：请用关键工件法排序并计算最长流程时间i1234Pi11954Pi25763Pi34635Pi46237时间求和16241719排序为：S=（1，4，2，3）关键工件法求解过程如下：7/23/202237按照S=（1，4，2，3）计算最长流程时间i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=337/23/202238(三)CDS法(Campbell,Dudek,Smith三人提出

22、) (见教材305页)第二节 流水作业排序问题 工件i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+ Pi31291011表11-7 用CDS法求解L=1时：按照Johnson法得到加工顺序为：1，2，3，4L=2时：按照Johnson法得到加工顺序为：2，3，1，47/23/2022398912618102711231929Fmax计算如下表所示Fmax=29 若加工顺序为（2，3， 1， 4）时，按Johnson算法Fmax=29，所以取加工顺序（1，2，3，4） Fmax=28为最优解。工件i设备工时2314Pi12613Pi24289Pi35842第二

23、节 流水作业排序问题27/23/202240P322习题2：请用CDS法排序并计算最长流程时间i1234Pi11954Pi25763Pi34635Pi46237关键工件法求解过程如下：7/23/202241排序为：S1=（1， 4， 3 ， 2）i1234L=1Pi11954Pi46237i1234Pi11954Pi25763Pi34635Pi462371、L=1时：7/23/202242排序为：S1=（1， 4， 3 ， 2）i1432Pi11459Pi25367Pi34536Pi467321510196916261015193216232634Fmax=347/23/202243排序为：S

24、1=（1， 4， 2 ，3 ）i1234L=2Pi1616117Pi4108612i1234Pi11954Pi25763Pi34635Pi462372、L=2时：7/23/202244排序为：S1=（ 1， 4， 2 ，3 ）i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=337/23/202245排序为：S1=（1， 4， 2 ，3 ）i1234L=3Pi110221412Pi415151215i1234Pi11954Pi25763Pi34635Pi462373、L=3时：7/23/202246排序为：S1=

25、（ 1， 4， 2 ，3 ）i1423Pi11495Pi25376Pi34563Pi467231514196921271015273016232933Fmax=33所以最终排序为：S1=（ 1， 4， 2 ，3 ）满意解。7/23/202247三、采用Johnson法则解决多个工件在三台设备上的作业排序 若存在一个n/3/P/Fmax问题，且mint1i maxt2i 或mint3i mint2i ( i =1，2，n)，则可采用Johnson法排序。 求解步骤为： （1）先找出mint1i maxt2i或mint3i mint2i关系 （2）将3台设备变换成2台假想设备MA和MB，并令 tA

26、i = t1i + t2i ； tBi = t2i + t3i （3）依据 tAi 和tBi，采用Johnson法则进行作业排序试采用Johnson法则进行作业排序工 件设 备J1J2 J3 J4M1158612M231 5 6M341057表11-17 加工时间表例：有一个4/3/P/ Fmax问题，其加工时间如表11-17所示7/23/202248解： mint1i =6 maxt2i =6 存在mint1i maxt2i mint3i =4 mint2i =1 存在mint3i mint2i 可采用Johnson法求解该作业排序问题(具备其一即可)。 计算tAi 和tBi，列于表11-1

27、8中表11-18 tAi 、tBi 与排序结果工 件设 备J1J2 J3 J4(MA) tAi1891118(MB) tBi，7111013排序结果J2J4J3J1t1i812615t2i1653t3i107548202641926314419333848 依据11-18中的tAi 和tBi，采用Johnson法进行作业排序。排序结果与Fmax如表11-18及图11-4所示。Fmax = 487/23/202249J2 J4 J3 J18 12 6 151 6 5 38 9 20 26 31 41 44 8 20 26 4110 7 5 4 9 19 26 33 38 44 48M1M2M3时

28、 间图11-4 排序结果甘特图7/23/202250 单件作业排序是最一般的排序问题，也是最复杂的一种排序问题。该问题本身容易表达，也能看出该问题所需要求解的是什么，但是朝着求解方向作任何推进都是极为困难的。许多人在此问题上都进行了探索，但一无所获者大有人在。第三节 单件作业排序问题7/23/202251第三节 单件作业排序问题一、问题的描述 对一般的单件作业排序问题，每个工件都有其独特的加工路线，工件没有一定的流向。但是，对于流水作业的排序问题，第 k道工序永远在MK上进行，没有必要将工序号与机器号分开。而对于一般的单件作业排序问题，要描述一道工序需要 i、j、k三个参数，即 i、j、k表示

29、第i 个工件的第j道工序在Mk(第k台机器上)上进行的。所以，可以用加工描述矩阵的形式来描述所有工件的加工。加工描述矩阵的形式如加工描述矩阵D所示。 加工描述矩阵的每一行描述一个工件的加工过程(第1行描述第一个工件的加工过程，第二行描述第2个工件的加工过程)。D的每一组数中的第1列数表示工件序号；D的每组数中的第2列数码相同，说明第2列表示工序号；D的每一组数中的第3列数表示设备序号。7/23/202252第三节 单件作业排序问题 二、一般n/m/G/Fmax问题的启发式算法 n/m/G/Fmax 为n个工件，m台机器，一般单件作业排序问题，使最大流程时间最短。对这类作业排序问题，可以用分支定

30、界法或整数规划法求最优解。但是，都是无效的方法。为此，在实际工作中，多采用启发式算法。为了对研究启发式算法有所帮助，先介绍两种十分重要的作业计划及其构成方法。7/23/202253 (一) 两种作业计划的构成 一般说来，在可行的加工顺序下，可以拟定出无数种作业计划。其中，各工序都按最早可能开始工作的时间安排作业计划，称为半能动作业计划。任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划，又称为能动作业计划。 无延迟作业计划是指没有任何延迟出现的能动作业计划。 所谓“延迟”是指工件等待加工时，机器出现空闲 ( 即使这段空闲时间不足以完成一道工序的加工)。 能动作业计划和无延迟作

31、业计划在研究一般单件作业排序问题时有重要作用。二、一般n/m/G/Fmax问题的启发式算法7/23/202254能动作业计划与无延迟作业计划构成过程中涉及到的4个符号： 若将每安排一道工序称为“一步”。 设： St 为第 t 步之前已排序工序构成的部分作业计划； Ot 为第 t 步可以排序的工序集合；Tk 为 Ot 中工序 Ok 的最早可能开工时间；Tk 为 Ot 中工序Ok的最早可能完工时间。显然： Ok工序的作业时间 = Tk - Tk 7/23/202255设t=1, S1 为空集， O1 为各工件第一道工序的集合。求T*=min|Tk|,并求出T*出现的机器M*。如果M*有多台，则任选

32、一台。从 Ot 中挑出满足以下两个条件的工序Oj ，需要机器M*加工，且Tj P1=4)，故按 SPT 规则将 J 2 排在第5顺序(倒数第2位)加工，即将 J2排在次后顺序上加工。表11-13 余下工件的F与预订交货期5710 18227/23/202271 反复进行（2）、（3）步，直到实现既使Lmax 0，又使 F (平均流程时间 )为Fmin的排序方案为止。 5710 142231 表11-14 排序方案及各参数结果表(三) 优先调度法则例题(此为单台设备排序问题例题) 按 SPT与EDD结合规则排序，可得出表11-10的排序问题的排序为：J4 J3 J6 J1 J2 J5表11-10

33、排序问题的结论如表11-14所示。3、SPT与EDD混合(结合)法则例题工件排序J4J3J6J1J2J5加工时间与F5 23 4 8 9预定交货期68 13 242332 计划完成时刻5 7 10 14 2231交货延期000000平均流程时间 F=14.87/23/202272现有一个n/2/F/Fmax (n个工件，2台设备，流水作业排序问题，使最长流程时间最短)问题。此问题可采用S.M.Johnson算。工件 JiJ1J2J3J4J5J6J7加工时间M16812371124M21195326182解：按照Johnson法则： （1）如果最短的加工时间出现在M1 上，则对应工件排在最前面(

34、第一个)加工，如果最短的加工时间出现在M2 上，则对应工件排在最后面(倒数第一个)加工，如果最短的加工时间同时出现在M1 、 M2 上，则该工件排在最前或最后加工均可。 （2）划去已排序工件，在余下来的未排序工件中仍然按上述方法进行作业排序，直到全部工件安排完为止。 (自己练习)表11-15 加 工 时 间例：有一个7/2/F/Fmax 问题，其加工时间如表11-15所示，试进行作业排序。第四节 多台设备作业排序流水作业排序（4152637）一、多个工件在两台设备上的作业排序7/23/202273 3 11 26 9 18 5 2表11-16 加 工 时 间与排序结果表 3 9 16 24 3

35、5 47 71 6 20 46 55 73 78 80（3）运用Johnson法则对此问题求解如表11-16和图11-3所示。J4 J1 J5 J2 J6 J3 J7 3 6 7 8 11 12 24 3 9 16 24 35 47 713 6 9 20 46 55 73 78 80M1M2时间Fmax =80图11-3 作业排序甘特图工件 JiJ1J2J3J4J5J6J7加工时间M168 12 3 7 11 24M21195 326 182工件排序结果J4J1 J5 J2 J6 J3 J7加工时间M13 6 7 8 11 12 24M23 11 269 1852J4 J1 J5 J2 J6

36、J3 J77/23/202274 若存在一个n/3/P/Fmax问题，且mint1i maxt2i 或mint3i mint2i ( i =1，2，n)，则可采用Johnson法排序。 求解步骤为： （1）先找出mint1i maxt2i或mint3i mint2i关系 （2）将3台设备变换成2台假想设备MA和MB，并令 tAi = t1i + t2i ； tBi = t2i + t3i （3）依据 tAi 和tBi，采用Johnson法则进行作业排序 二、多个工件在三台设备上的作业排序(采用Johnson法则)试采用Johnson法则进行作业排序工 件设 备J1J2 J3 J4M115861

37、2M231 5 6M341057表11-17 加工时间表例：有一个4/3/P/ Fmax问题，其加工时间如表11-17所示7/23/202275解： mint1i =6 maxt2i =6 存在mint1i maxt2i mint3i =4 mint2i =1 存在mint3i mint2i 可采用Johnson法求解该作业排序问题(具备其一即可)。 计算tAi 和tBi，列于表11-18中表11-18 tAi 、tBi 与排序结果学生自己练习绘制排序结果甘特图工 件设 备J1J2 J3 J4(MA) tAi1891118(MB) tBi，7111013排序结果J2J4J3J1t1i81261

38、5t2i1653t3i107548202641926314419333848 依据11-18中的tAi 和tBi，采用Johnson法进行作业排序。排序结果与Fmax如表11-18及图11-4所示。Fmax = 487/23/202276J2 J4 J3 J18 12 6 151 6 5 38 9 20 26 31 41 44 8 20 26 4110 7 5 4 9 19 26 33 38 44 48M1M2M3时 间图11-4 排序结果甘特图7/23/202277 n个工件在m台设备上排序是比较困难的。但是，对于2个工件在m台设备上排序问题，运用图解法虽然不一定求到最佳解，却可以求到比较令

39、人满意的解。 例： 2个工件在4台机器上加工，每个工件的加工顺序不同。J1的加工顺序是M1，M2，M3，M4；J2的加工顺序是M4，M2，M1，M3，其加工时间如表11-19所示。显然，这是一个非流水作业排序问题，是一个一般的排序问题，故可用2/4/G/Fmax表示，也可用2/4/G/Cmax表示。三、两个工件在m台设备上的作业排序该问题亦可用加工描述矩阵D与加工时间矩阵T表示为：表11-19 加工时间表 （一） 用图解法求解设 备工 件M1M2M3M4J12 541J22 5 367/23/202278第四节 多台设备作业排序 （1）画平面直角坐标，横、纵轴分别为J1、J2 的加工时间，对应

40、横轴下部的甘特图与对应纵轴左侧的甘特图分别表示J1、J2 加工顺序及其所对应的加工时间，原点O为时间起点。找出表示J1、J2 总加工时间的坐标点D(12，16)。 （2）划去不可能同时加工两个工件的时间。开始时， J1 在M1上加工， M1 便不能加工J2 ，故划去方格的区域，同理划去方格、的区域。 （3）从原点开始，在未划去的区域中，连线到终点D。连线若为45角，表示2个工件同时在被加工。例如A点(6,6)，表示 J1在M1上加工早已完毕，正在M2上加工； J2 在 M4上加工刚好完毕，正准备进入 M2上加工，但由于M2正在加工J1，所以，又等了1个单位时间到B点(7,6) ，此时，M2刚好

41、加工完J1。从B点开始，M2加工J2， M3加工J1；接着M1加工J2， M4加工J1。到了C点(12,11)， M4刚好加工完J1，M2 刚好加工完J2。C点到D点是竖直线，此段时间 J1已加工完毕， M1和M3只加工J2 。三、两个工件在m台设备上的作业排序例，解：该问题可采用图解法求作业排序的解。7/23/202279 例，解： （3）由原点向D点引连线时，尽量按45角方向引线，并使等待时间最小。在实际操作上，这种排序方法常常通过目视、徒手画的方法完成的，所以，不能保证求得最佳的排序结果，只能求得较令人满意的结果。从作图求解过程可知： J1工件没有等待时间，F1max =12； J2 加

42、工等待时间为1，所以，F2max =17。当然此问题也可写成 C1max =12； C2max =17。该图解法求解 2/4/G/ Cmax 问题的过程如图11-5所示。7/23/202280图11-5 图解法求解2/4/G/Cmax过程图J1J2M1M227M311M412M4M2611M113M316IIIIIIIVA(6,6)B(7,6)C(12,11)D(12,16)7/23/202281 例，解： 上述作业 排序问题2/4/G/Fmax , 三、两个工件在m台设备上的作业排序的排序结果如图11-6所示。2, 2, 2(1,4,4)（2） 2 12 （2）14 2 （5） 7 （5）

43、12 7 （4） 11 14 （3） 17 （6） 6 11 12 （1）Fmax = Cmax =17J1J2J2J2J2J1J1J1M1M2M3M4o时间图11-6 作业排序甘特图1,1,12,3,11,2,21,3,32,2,22,4,32,1,47/23/202282三、两个工件在m台设备上的作业排序（二） 用启发式算法求解1、请同学们按能动作业计划构成步骤求解。前述的2/4/G/Fmax ,可采用按能动作业计划构成步骤求解，其求解(排序)过程及结果如表11-20与图11-7所示。7/23/202283表1120 能动作业计划构成表t Ot Tk TkT*M*Oj11, 1, 1 2,

44、 1, 400262M11, 1, 121, 2, 2 2, 1, 420766M42, 1, 431, 2, 2 2, 2, 2277127M21, 2, 241, 3, 3 2, 2, 277111211M31, 3, 351, 4, 42, 2, 2117121212M22, 2, 261, 4, 42, 3, 11112121412M41, 4, 472, 3, 12, 4, 31214141714M12, 3, 182, 4, 3141717M32, 4, 37/23/202284（二） 用启发式算法求解1、按能动作业计划构成步骤求解根据11-20可绘出如图11-7所示的该问题作业排

45、序甘特图。由图11-7可见，采用启发式算法，按能动作业计划构成步骤进行求解，作业排序结果甘特图与图解法得出的图11-6所示的甘特图相同，说明两种方法求解结果相同。1,1,12, 3,11, 2, 22, 2, 21, 3, 32, 4, 3 2, 1, 4(1,4,4)（2） 2 12 （2）14 2 （5） 7 （5） 12 7 （4） 11 14 （3） 17 （6） 6 11 12 （1）Fmax = Cmax =17J1J2J2J2J2J1J1J1M1M2M3M4o时间图11-7 作业排序甘特图7/23/202285 （二） 用启发式算法求解 2、按无延迟作业计划构成步骤求解 其求解(

46、排序)过程及结果如表11-21与图11-7所示。(见下一页) 由表11-2中的 栏与 栏可看出，构成作业计划(排序)中所选中的设备与工件及其安排次序均与表11-20相同，说明排序结果相同，绘出的表示作业排序结果的甘特图肯定也与图11-7相同，这里不再另外绘出。前述的2/4/G/Fmax ,M* Oj可采用按无延迟作业计划构成步骤求解，7/23/202286表1121 无延迟作业计划的构成表t Ot Tk TkT*M*Oj11, 1, 1 2, 1, 4002600M1M41, 1, 121, 2, 2 2, 1, 420760M42, 1, 431, 2, 2 2, 2, 2277122M21

47、, 2, 241, 3, 3 2, 2, 277111277M3M21, 3, 351, 4, 42, 2, 211712127M22, 2, 261, 4, 42, 3, 11112121411M41, 4, 472, 3, 12, 4, 31214141712M12, 3, 182, 4, 3141714M32, 4, 3(Fmax = Cmax =17)7/23/202287课堂练习、5种零件在三台机床上的加工时间如下表所示。 零件机床J1J2J3J4J5M135657M223312M353426表1零件加工时间表（小时）请用约翰逊法则排序并计算最大流程时间。7/23/2022882、两

48、种零件的加工描述矩阵和加工时间矩阵如下。请用能动作业计划表（图解法）确定两种零件的投产方案并绘制甘特图确定加工作业周期1,1,1 1,2,2 1,3,3 1,4,42,1,1 2,2,4 2,3,2 2,4,3T2 1 8 21 4 1 47/23/2022891题解答：n/3/P/Fmax问题，满足mint1i maxt2i 或mint3i mint2i ( i =1，2，n)，则可采用Johnson法排序。求解步骤为： （1）判断mint1i =3maxt2i=3或mint3i = 2 mint2i1满足关系.可以应用Johnson法排序. （2）将3台设备变换成2台假想设备MA和MB，并

49、令tAi = t1i + t2i ； tBi = t2i + t3i （3）依据 tAi 和tBi，采用Johnson法则进行作业排序 零件机床J1J2J3J4J5M135657M223312M353426 零件假想机床J1J2J3J4J5T1i=M1i+M2i58969T2i=M2i+M3i767387/23/202290结果为:J1J5J3J2J4 零件机床J1J5J3J2J4M137655M222331M3564323101621265121924271018232729最大流程时间Fmax=29（小时）7/23/2022912题解答：图解法确定两种零件的投产方案并绘制甘特图图解法确定两

50、种零件的投产方案1,1,1 1,2,2 1,3,3 1,4,42,1,1 2,2,4 2,3,2 2,4,3T2 1 8 21 4 1 4M1M1M3M40 1 2 3 4 5 6 7 8 9 0 1 2 3109876543210M4M2M3M2IIVIIIIIJ1J2Q(13,10)F2=15=2+1+4+1+3+2+2F1=16=1+4+1+(6)+2+27/23/202292 第二方案甘特图Fmax=15(小时)0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5时间（小时）M2M1M3M41,1,11,2,21,3,31,4,42,1,12,2,42323331111132

51、,3,27782,4,315J1J2J2J2J1J17/23/202293排序问题作业练习：P321 1，2补充4:有一个2/5/G/Cmax的问题。零件1的工艺路线次序为经过机器：1，2，3，4，5；零件2的工艺路线次序为经过机器：4，1，2，5，3，工序加工时间见下表。试用图解法求完成总时间最少的排序，并绘出甘特图。机床零件号机器号M1M2M3M4M51234622412257/23/202294第五节生产作业监控与调度规则生产作业计划实施过程总会出现一些难以预见防碍的因素。因此，要对生产的全过程进行监控，及时发现计划执行中已发生或即将发生的各种偏差,并采取措施预防和纠正它。作业监控是生产

52、管理工作的基本职能之一。在编制生产作业进度计划时，一般考虑静态情况较多，只有当生产因素比较稳定和比较理想的情况才能得到最优化。但在动态的生产实施过程中，影响生产实施的一些因素会发生变化，如零件加工时间有随机性，原材料供应误期，上一工序延期交付，零件加工中的报废，工具，设备发生故障，工人缺勤等等；以及外部因素，如市场需求发生变化而影响生产计划的数量来因此，在生产实施时期，生产控制必须及时、全面地了解和掌握生产过程情况，采取有效措施保证完成计划期内预定的生产目标。这对多品种的成批和单件批小生产尤为重要。7/23/202295一、生产控制功能生产控制包括以下两个基本功能： 1生产系统控制 生产系统控

53、制是控制从原材料到最终产品的物质流。包括：控制时间（交付期）和产量的生产控制（狭义的生产控制）；保证产品具有要求的质量和可靠性的质量控制；控制原材料、产品的库存控制；生产过程中的成本控制等。 2生产资源控制 生产资源控制主要是指对生产设备的控制功能。它的基本活动是防止生产设备损坏和修复已损坏的生产设备，即生产设备的维修工作。7/23/202296二、对时间和产量的生产控制 生产进度计划规定的产量和进度（或交付日期）是生产实施阶段的生产标准。经常检查实际产量和完工时间并和计划标准比较，如果发生偏差，就要采取有效措施以保证完成计划。图1128是表示生产控制的一般反馈过程。对计划进度与实际实施情况发

54、生的偏差，应及时报告有关管理人员和领导，迅速作出决策以追补或调整偏差。生产标准：计划产量与时间生产实施度量生产效果、实际产量与时间比较计划与实际效果修正偏差图1028生产控制系统反馈过程7/23/202297 对时间（进度）和产量的生产控制，要求经常检查车间（或工段）之间、车间内部的产品（零件、部件、毛坯）的交付期限，原材料供应和投入情况，以及生产过程中的库存的在制品储备情况。对生产实施情况的检查，传统的办法是利用各种形式的图表来对比出产量的计划进度和实际进度。如用横道图表示的产品（零、部件）出产量进度完成情况如图表、产品配套计划完成情况图表以及主要零件各道工序的进度完成情况图表。对于在制品的

55、库存和周转情况也可采用各种形式的图表对比检查。 除了检查生产进度完成情况外，还应检查和督促生产准备工作进行情况，劳动力配备情况，设备运转和维修情况，运输、动力运行情况以及主要的技术关键等情况。 生产控制工作要求反映情况的及时性、准确性、全面性；作出决策处理问题的迅速性。计算机辅助生产信息系统，有利于实现这些要求。从数据的收集、数据存储、数据取出、数据处理、数据传输到数据显示，它使生产系统能够适时地精确地处理各种信息，作出适当的决策，采取相应的措施，从而适应动态地变化着的外部环境。7/23/202298三、调度规则我们在安排进度计划时，介绍了零件加工的排序寻忧解法。这些解法都是处理静态问题的；如果出现动态情况，就没有一般求最优解的方法。当有一个以上工件在机床前排队时，必须确定这些工件的加工次序。规定机床在加工完一种零件后，接着应加工哪一种零件。在动态加工车间内，这种进度决策，通常是利用调度（或优先）规则来确定的。有了某一适当的优先规则，对动态加工车间的进度可以做模拟研究和实验。当一个车间或工段内加工许多项订货或零件，每项订货或零件又都需要由许多道工序来完成，而且每项订货或零件所经历的工序内容与次序又都是不同的。究竟应该如何安排才能取得较好的经济效益，用上述排序的办法就难以解决这类问题。人们探求其中的规律性，看是否有简单的判别准则可以应用？这类生产中的主