当前位置： >>
第10章作业排序与生产作业计划
第 十 章 作业排序与生产作业计划 第一节 作业排序的基本概念 第二节 流水作业排序问题 第三节 单件作业排序问题 第四节 多台设备作业排序1第一节 作业排序的基本概念引 言 在确定了各车间的零部件投入、出产计 划、将全厂的生产计划变成了各车间的生产 任务后,各车间还应将零部件的
投入、出产计 划变成车间的作业计划，即将车间的生产任 务变成各工段、班组、各工作地的生产任务。 编制车间生产作业计划，应该解决工件加工 顺序问题。这就是我们要讨论的作业排序问 题。采用排序理论与方法，可以得出工件加 工的最优或令人满意的顺序。第一节 作业排序的基本概念一、编制生产作业计划与排序的关系编制生产作业计划与作业排序不同，排序只是确 定工件在机器上的加工顺序，可以用一组工件的代 号的排列来表示这组工件的加工顺序，而编制生产 作业计划不仅包括确定工件的加工顺序，而且包括 确定机器加工每个工件的开始时间和完成时间。所 以，只有生产作业计划才能指导工人的生产活动。 在编制生产作业计划时常常出现一个工件在某道 工序加工完之后，加工它的下一道工序的机器还在 加工前一个工件，这时该工件不得不等待一段时间 才能开始在下一道工序的机器上加工。这种情况称 为“工件等待”。 当某台机器已加工完一个工件，而下一个工件尚 未到达。这种情况称为“机器空闲”。第一节 作业排序的基本概念由于编制生产作业计划的主要问题是确定 各台机器上工件的加工顺序，并且一般都是 按最早可能开工时间或最早可能完工时间来 编制生产作业计划。所以，当工件的加工按 一定的时间确定了加工顺序后，作业计划也 就确定了。这就造成了人们通常不加区别的 使用“排序”与“编制作业计划”两个术语。几个名词术语? 排序――工件在机器上的加工顺序? 派工――将生产任务安排到具体机床上加工―调度范围；? 赶工――实际进度落后于计划进度时采取的行动―调度范 围；? 调度――发现实际进度落后于计划进度时而采取的调配资 源的行动。? 机器――服务者? 工件――服务对象? 加工路线――工件加工的工艺过程 ? 工序――加工路线上的每一个具体工作地（机器）。 5第一节 作业排序的基本概念二、假设条件与符号说明为了便于采用数学模型来分析研究排序问题，做下列假设：1. 一个工件不能同时在几台不同的机器上被加工。 2. 采取平行移动方式移送被加工的工件。 3. 不允许中断。当一个工件一旦开始加工,必须一直进行到完 工,不得中途停止插入其它工件。 4. 工件在每道工序的加工只在一台机器上进行。 5. 工件数（或批量）、机器数已知，单件加工时间已知, 完 成加工的时间与加工顺序无关。 6. 每台机器同时只能加工一个工件。第一节 作业排序的基本概念符号说明 ? Ji ―― 第 i 工件，i = 1,2,…,n ；? Mj ―― 第 j 台机器，j =1,2,…,m； (i , j, k) ―― Ji 的第j 道工序在Mk上进行；Pi = ∑ Pij Pij ―― Ji 在 Mj上的加工时间， Ji加工完的总加工时间； j=1 ri―― Ji 到达工序时间，即可以开始加工的最早时间； di ―― Ji 的完工期限； ai―― Ji 在车间允许停留的时间（ Ji 进入车间到完工时刻之间的 时间间隔： ai = di －ri）； Wij ―― Ji 在第 j 道工序前的等待时间， m Ji 总的等待时间： Wi = ∑ Wij j=1m7第一节 作业排序的基本概念Ci ―― Ji 的完工时间 Ci = ri +∑( Pij + Wij ) = ri + Pi + Wi ? Cmax ―― 最长完工时间,Cmax = max{Ci}, 即一批工件中的最长 完工时间;? Fi ―― Ji 的流程时间,即工件在车间的实际停留时间, Fi = Ci －ri = Pi + WFmax ―― 最长流程时间, Fmax = max{Fi}, 即一批工件中的最长流 程时间; Li ―― Ji 工件的延迟时间， Li = Ci －di = ri + Pi + Wi － di = (Pi + Wi ) － (di － ri ) = Fi －ai第一节 作业排序的基本概念当 Li & 0 时为正延迟, 即Ji 的实际完工时间超过了完 工期限;当 Li & 0 时为负延迟, 即Ji 提前完工;当 Li = 0 时为零延迟, 即Ji 按期完工。Lmax ―― 最长延迟时间, Lmax = max {Li} . 即在一批 工件中找出的最大延迟时间.第一节 作业排序的基本概念三、排序问题的分类和表示法排序问题常见的分类方法有按机器、工件、目标函数的特 征分类。1. 按机器的种类和数量不同,可以分成 单台机器的排序问题 多台机器的排序问题 对于多台机器的排序问题,按工件加工路线的特征,可以分成 单件作业排序问题 ―― 加工路线不同 流水作业排序问题 ―― 加工路线相同第一节 作业排序的基本概念2. 按工件到达车间的情况不同,可以分成 静态的排序问题 ―― 排序时所有工件都已到达,可以一次 对它们进行排序. 动态的排序问题 ―― 排序时工件陆续到达,要随时安排它们 的加工顺序 3. 按目标函数的性质不同,也可划分不同的排序问题 使平均流程时间最短 单台机器的排序 使误期完工工件数最少 …… 多台机器的排序：不同目标排序问题 单目标排序问题：以往研究的对象 多目标排序问题：很少有人研究第一节 作业排序的基本概念4. 另外，按参数的性质，可以划分为 确定型排序问题 ―― 指加工时间和有关参数是已知 确定的量 随机型排序问题 ――加工时间和有关参数为随机变量这两种排序问题的解法本质上不同。现只讨论几种有代表性的排序问题。第一节 作业排序的基本概念通常采用Conway等人提出的排序方法。这个方法主要涉 及到4个参数，只用4个参数就可以表示大多数不同的排序问 题。这4个参数通常表示为：n / m /A / B。 n 为工件数；m 为机器数 B 为目标函数,通常是使其值最小 A 为车间类型，通常有以下几种情况，在A的位置： (1) 若标以&F&,则代表流水作业排序问题 (2) 若标以“P”,则表示流水作业排列排序问题，也 常被称为“同顺序”排序问题 (3) 若标以“G”,则表示一般单件作业排序问题。第一节 作业排序的基本概念当m=1时，A处为空白。因为对于单台机器的排 序问题来说，不存在所谓的加工路线问题，当然也 就谈不到是流水作业排序问题还是单件作业的排序 问题了。通过 n / m /A / B 这4个符号，就可以简捷的表述 一般的排序问题了。例如， n / 3 / P / Cmax 表示n 个 工件经3台机器加工的流水作业排列排序问题，目标 函数是使最长完工时间最短。第 十 章 作业排序与生产作业计划回顾? ? ? ? ? 排序问题常见的分类方法有按机器、工件、目标函数的特征分类。 排序问题由4个参数表示：n / m /A / B。 n 为工件数； m 为机器数 B 为目标函数,通常是使其值最小 A 为车间类型，通常有以下几种情况，在A的位置：(1) 若标以“F”,则代表流水作业排序问题。 (2) 若标以“P”,则表示流水作业排列排序问题，也常被称为“同顺序”排序问题。 (3) 若标以“G”,则表示一般单件作业排序问题。? Cmax ―― 最长完工时间； Fmax ―― 最长流程时间； Lmax ―― 最长延迟时间。 Lmax = max {Li} . 即在一批工件中找出的最大延迟时间。当 Li & 0 时为正延迟, 即Ji 的实际完工时间超过了完工期限; 当 Li & 0 时为负延迟, 即Ji 提前完工; 当 Li = 0 时为零延迟, 即Ji 按期完工。 例如：n / 3 / P / Cmax 表示n 个工件经3台机器加工的流水作业排列排序问题，目标 函数是使最长完工时间最短。 15第二节 流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致。在 流水生产线上制造不同的零件, 遇到的就是流水作业排序问题。我们 说加工路线一致,是指工件的流向一致,并不要求每个工件必须经过加 工路线上每台机器加工。如果某些工件不经某些机器加工,则设相应 的加工时间为零。 一般说来,对于流水作业排序问题, 工件在不同机器上的加工顺 序不尽一致。但本节要讨论的是一种特殊情况,即所有工件在各台机 器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列 排序问题常被称作&同顺序&排序问题。对于一般情形,排列排序问题 的最优解不一定是相应的流水作业排序问题的最优解,但一般是比较 好的解;对于仅有2台和3台机器的特殊情况,可以证明,排列排序问题 下的最优解一定是相应流水作业排序问题的最优解。本节只讨论排列排序问题。但对于2台机器的排序问题,实际上不 只是排列排序问题，因为两者的最优解及其解法是相同的。第二节 流水作业排序问题一、最长流程时间Fmax的计算 最长流程时间就是工件在车间实际停留的最长时间。 本节所讨论的是n/m/ρ/Fmax问题,目标函数是使最长 流程时间最短。最长流程时间又称作加工周期,它 是从第一个工件在第一台机器开始加工时算起,到 最后一个工件在最后一台机器上完成加工时为止所 经过的时间。由于假设所有工件的到达时间都为零 (r = 0，i = 1,2,…,n),所以Fmax等于排在末位加工的 工件在车间的停留时间,也等于一批工件的最长完 工时间Cmax。第二节 流水作业排序问题设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) = max{Ck-1(si), Ck(si-1)} + Psik显然，当ri = 0 时， Fmax = Cm(sn)在知道了上述计算Fmax 公式后，便可直接在工件加工的 时间矩阵上从左向右计算完工时间。(11 ― 1)第二节 流水作业排序问题例11.1有一个6/4/p/Fmax问题,其加工时间如下表所示。 当按顺序S=(6,1,5,2,4,3)加工时,求Fmax 表11-1 加工时间矩阵iPi1 Pi2 Pi3 Pi414 4 5 422 5 8 233 6 7 441 7 5 354 4 5 362 5 5 1表11-2 顺序S下的加工时间矩阵i Pi1 Pi2 Pi3 6 2 5 5 1 5 2 4 327 12 134 4 5611 17 214 4 51015 22 252 5 81220 30 321 7 51327 35 383 6 71633 42Pi414323446Fmax=46 20第二节 流水作业排序问题二、n/2/F/Fmax问题的最优算法 Johnson算法: (1) 从加工时间矩阵中找出最短的加工时间。 (2) 若最短的加工时间出现在M1上,则对应的工件尽可能往前排； 若最短加工时间出现在M2上，则对应工件尽可能往后排。 然后, 从加工时间矩阵中划去已排序工件的加工时间。若最 短加工时间有多个, 则任挑一个往前排。(3) 若所有工件都已排序, 停止.否则, 转步骤(1).第二节 流水作业排序问题二、n/2/F/Fmax问题的最优算法例11.2求表1１-３所示的6/２/Ｆ/Fmax问题的最优解。 表11-3加工时间矩阵 i ai bi １ ５ ８ ２ ３ ４ ５ ６ ４ ４513１ ２615８ ２1417５ ４192322 ３30 ７2634Fmax0(1,2,3,4,5,6)=34表11-4 改进算法见教材303页i １ ２ (4) １ ２ (1) ８ ２ ３ ４ ５ ６ (2) ４ (3) ４aibi５８５３(6) ４ (5) ７Johnson改进算法： １.将所有ai≤bi的工件按ai值不减的顺序排成一个列Ａ； ２.将所有ai＞bi的工件按bi值不增的顺序排成一个列Ｂ； ３.将Ａ放到Ｂ之前，就构成了最优加工顺序． S = ( 2, 5, 6, 1, 4, 3 ) A=(2,5,6,1) B=(4,3)i ai bi２ １ ２1 3５ ３ ７4 11６ ４8１ ５13４ ５15 23 ４ ８ ４ Fmax*(2,5,6,1,4,3)=29３ 18 26 ８ 27 29 ２23第二节 流水作业排序问题当我们从应用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法则, 但它也是一个最优顺序。例11.2顺序(2,5,6,4,1,3)i ai bi ２ ５ ６ ４ １ ３１ ２1 3３ ７4 11４ ４8 15５ ４13 19５ ８18 27８ ２26 29Fmax*(2,5,6, 4,1, 3)=29 25第二节 流水作业排序问题三、一般n/m/P/Fmax问题的启发式算法 对于3台机器的流水车间排序问题,只有几种特殊类型的问题找到 了有效算法。对于一般的流水车间排列排序问题,可以用分支定界法。 用分支定界法可以保证得到一般n/m/P/Fmax问题的最优解。但对于实 际生产中规模较大的问题,计算量相当大,以至连电子计算机也无法求 解。同时,还需考虑经济性。如果为了求最优解付出的代价超过了这个 最优解所带来的好处,也是不值得的。 为了解决生产实际中的排序问题,人们提出了各种启发式算法。启 发式算法以小的计算量得到足够好的结果,因而十分适用。下面介绍求 一般n/m/p/Fmax问题近优解(Near optimal solution)的启发式算法。第二节 流水作业排序问题(一) 帕尔姆( Palmer)法 1965年,D.S.Palmer提出按工件斜度指标排序的启发式算法。设： 工件的斜度指标为?i ，k为笫k台设备，m为设备数，P i k为i 工 件在Mk上加工时间，k为设备的任意序数，（k=1,2,3,……,m）?i= ∑ ［k－（m+1）/2］P ikk=1m从该式中求出各工件的 ?i，再按着不使?i 增加 的原则排列各 个工件的加工顺序，就可以得出令人满意的结果。例11.3 有一个4/3/F/Fmax排序问题（即4个工件3台设备，流水作 业排序问题，目标是使最长流程时间最短），各个工件在每台 设备上的加工时间如下面的加工时间矩阵表所示，试采用 Palmer法求解。表11-5 加工时间矩阵工件i 设备工时 Pi1 Pi2 Pi3 1 8 491123394122136 218153 9 224284 513826Fmax=28按照排序为：S=（ 2，1，3，4）工件i 设备工时 2 1 3 4Pi1 Pi2Pi32 452 6 111 843 14 186 289 16 263 9212 25 28Fmax=28 29第二节 流水作业排序问题解：由?i= ∑ ［k－（m+1）/2］Pikk=1m可知(见教材304页)?i ? ? pi1 ? pi 3 ?1 ? ? p11 ? p13 ? ?1 ? 4 ? 3 ?2 ? ? p21 ? p23 ? ?2 ? 5 ? 3 ?3 ? ? p31 ? p33 ? ?6 ? 8 ? 2 ?4 ? ? p41 ? p43 ? ?3 ? 2 ? ?1按照? i从大到小的顺序排列就是最优排列顺序。?1 ? ?2 ? ?3 ? ?4最优排列顺序S=（1，2，3，4）或：S=（ 2，1，3，4）P322习题2：请用帕尔玛法排序并计 算最长流程时间求解过程：i Pik Pik Pik Pik (KK 1 2 3 4 K-(m+1)/2 (m+1)/2) *P1k 1 1 9 5 4 2 5 7 6 3 3 4 6 3 5 4 6 2 3 7 -1.5 -0.5 0.5 1.5 -1.5 -2.5 2 9 (K(m+1)/2) *P2k -13.5 -3.5 3 3 (K(m+1)/2) *P3k -7.5 -3 1.5 4.5 (K(m+1)/2) *P4k -6 -1.5 2.5 10.5m=4Ai=(K-(m+1)/2)*P1k7-11-4.5315.5排序为：S=(1,4,3,2)按照 S=(1,4,3,2)计算最长流程时间：i 1 4 1 6 3 5 9 2 10 16PikPik Pik15 443569719 26 32 343210 5 1615 3 2319 6 26Pik6732Fmax=34第二节 流水作业排序问题(二)关键工件法 关键工件法是1983年提出的一个启发式算法。其步骤如下: (1)计算每个工件的总加工时间P i= ∑ Pij, 找出总加工时间最长的工件 C(j=1. 2. 3.…… m), 将其作为关键工件。(2)对于余下的工件, 若Pi1Q Pim, 则按 Pi1不减的顺序排成一个序列 Sa；若Pi1＞ Pim， 则按 Pim不增的顺序排列成一个序列Sb。(3)顺序(sa, C, Sb )即为所求顺序（近优解）。第二节 流水作业排序问题例：有4个工件，在3台设备上加工，每个工件在每台设备上加工的 单件工时消耗如表11-6所示。试采用关键工件法求近优解（近优排 序）。i = 1,2,3,4； m=1,2,3 (见教材305页) 表11- 6 工件在每台设备上的单件工时与总工时 工件i 1 1 8 4 13 2 2 4 5 11 3 6 2 8 16 4 3 9 2 14Pi1Pi2 Pi3Pi1234第二节 流水作业排序问题解： （1）计算每个工件的总加工时间，填写在表11-6上，分 别为（13,11,16,14），可见总加工时间最长的工件为3号 工件，总加工时间P3=16。 （2）余下的工件为1,2,4号工件， Pi1Q 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）表11- 6 工件在每台设备上的单件工时与总工时 Fmax计算过程 工件i 1 1 8 4 1 2 4 5 2 3 6 2 8 3 9 3 9 2 4 12Pi1Pi2 Pi391313181526242836P322习题2：请用关键工件法排序并 计算最长流程时间关键工件法求解过程如下：i Pi1 Pi2 1 1 5 2 9 7 3 5 6 4 4 3Pi3Pi446623357时间求和16241719排序为：S=（1，4，2，3） 37按照S=（1，4，2，3）计算最长流程时间i Pi1 Pi2 Pi3 Pi41 1 5 4 64231 6 10 164 3 5 75 9 15 239 7 6 214 21 27 295 6 3 319 27 30 3338Fmax=33第二节 流水作业排序问题(三)CDS法(Campbell,Dudek,Smith三人提出) (见教材305页) 表11-7 用CDS法求解 1 2 工件i Pi1 1 2 Pi3 Pi1+Pi2 Pi2+ Pi3 4 9 12 5 6 9 3 6 8 8 10 4 3 2 12 11L=1L=2L=1时：按照Johnson法得到加工顺序为：1，2，3，4 L=2时：按照Johnson法得到加工顺序为：2，3，1，4第二节 流水作业排序问题Fmax计算如下表所示工件i 设备工时 2 2 4 52 6 11Fmax=2918 10 193 6 2 8 1 8 449 18 23Pi1Pi2 Pi33 9 212 27 29若加工顺序为（2，3， 1， 4）时，按Johnson算法Fmax=29， 所以取加工顺序（1，2，3，4） Fmax=28为最优解。P322习题2：请用CDS法排序并计算 最长流程时间关键工件法求解过程如下：i Pi1 Pi2 1 1 5 2 9 7 3 5 6 4 4 3Pi3Pi446623357411、L=1时：i Pi1 Pi2 Pi3 Pi4 i L=1 1 1 5 4 6 1 2 9 7 6 2 2 3 5 6 3 3 3 4 4 3 5 7 4Pi1Pi416925347排序为：S1=（1， 4， 3 ， 2） 42排序为：S1=（1， 4， 3 ， 2）i Pi1 1 5 4 1 4 3 216 104 3 559 155 6 31016 19 269 7 61926 32Pi2Pi3Pi4616723323443Fmax=342、L=2时：i Pi1 Pi2 Pi3 Pi4 i 1 1 5 4 6 1 6 2 9 7 6 2 2 16 3 5 6 3 3 3 11 4 4 3 5 7 4 7L=2Pi1Pi410861244排序为：S1=（1， 4， 2 ，3 ）排序为：S1=（ 1， 4， 2 ，3 ）i Pi1 Pi2 Pi3 1 5 4 1 4 2 316 104 3 559 159 7 61421 27 295 6 31927 30Pi4616723233345Fmax=333、L=3时：i 1 2 3 4Pi1 Pi2 Pi3 Pi4i L=3 Pi1 Pi41 5 4 61 10 159 7 6 22 22 155 6 3 33 14 124 3 5 74 12 15排序为：S1=（1， 4， 2 ，3 ） 46排序为：S1=（ 1， 4， 2 ，3 ）i Pi1 Pi2 Pi3 Pi4 1 5 4 6 1 4 2 31 6 10 164 3 5 75 9 15 239 7 6 214 21 27 295 6 3 319 27 30 33Fmax=33所以最终排序为：S1=（ 1， 4， 2 ，3 ）满意解。 47三、采用Johnson法则解决多个工件在三台设备上的作业排序若存在一个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法则进行作业排序 例：有一个4/3/P/ Fmax问题，其加工时间如表11-17所示 表11-17 加工时间表工件 设 备J115J28J36J412M1M2M334110556748试采用Johnson法则进行作业排序解： ① ∵ mint1i =6 maxt2i =6 存在mint1i ≥maxt2i mint3i =4 mint2i =1 存在mint3i ≥ mint2i ∴可采用Johnson法求解该作业排序问题(具备其一即可)。 ② 计算tAi 和tBi，列于表11-18中表11-18工件 设 备tAi 、tBi 与排序结果J118 7J29 11J311 10J418 13(MA) tAi (MB) tBi， 排序结果t1 i t2i t3iJ28 1 108 12J420 6J326 15J1419 6 19 726 5 33 531 3 38 444 48③ 依据11-18中的tAi 和tBi，采用Johnson法进行作业排序。排序结果与 Fmax如表11-18及图11-4所示。Fmax = 48 49J2M1 88J41220J3626J11541M218 9 20626531341 44M391019 26733538 44448时间图11-4 排序结果甘特图 50第三节 单件作业排序问题单件作业排序是最一般的排序问题，也是 最复杂的一种排序问题。该问题本身容易表达， 也能看出该问题所需要求解的是什么，但是朝着 求解方向作任何推进都是极为困难的。许多人在 此问题上都进行了探索，但一无所获者大有人在。第三节 单件作业排序问题一、问题的描述对一般的单件作业排序问题，每个工件都有其独特的加工路 线，工件没有一定的流向。但是，对于流水作业的排序问题，第 k道 工序永远在MK上进行，没有必要将工序号与机器号分开。而对于一 般的单件作业排序问题，要描述一道工序需要 i、j、k三个参数，即 i、 j、k表示第i 个工件的第j道工序在Mk(第k台机器上)上进行的。所以， 可以用加工描述矩阵的形式来描述所有工件的加工。加工描述矩阵 的形式如加工描述矩阵D所示。? 1,1,1 1,2,3 D?? ? 2,1,3 2,2,1 ?1,3,2 ? ? 2,3,2 ? ??5 T ?? ?8 ?4 98? ? 5? ?加工描述矩阵的每一行描述一个工件的加工过程(第1行描述第一个工件的加工 过程，第二行描述第2个工件的加工过程)。D的每一组数中的第1列数表示工件序 号；D的每组数中的第2列数码相同，说明第2列表示工序号；D的每一组数中的第 3列数表示设备序号。第三节 单件作业排序问题二、一般n/m/G/Fmax问题的启发式算法 n/m/G/Fmax 为n个工件，m台机器，一般单件作业排序问题，使最大流程时间最短。对这类 作业排序问题，可以用分支定界法或整数规划法 求最优解。但是，都是无效的方法。为此，在实 际工作中，多采用启发式算法。为了对研究启发 式算法有所帮助，先介绍两种十分重要的作业计 划及其构成方法。二、一般n/m/G/Fmax问题的启发式算法(一) 两种作业计划的构成 一般说来，在可行的加工顺序下，可以拟定出无数种作业计划。 其中，各工序都按最早可能开始工作的时间安排作业计划，称为半能 动作业计划。任何一台机器的每段空闲时间都不足以加工一道可加工 工序的半能动作业计划，又称为能动作业计划。 无延迟作业计划是指没有任何延迟出现的能动作业计划。 所谓“延迟”是指工件等待加工时，机器出现空闲 ( 即使这段空 闲时间不足以完成一道工序的加工)。 能动作业计划和无延迟作业计划在研究一般单件作业排序问题时 有重要作用。△能动作业计划与无延迟作业计划构成过程中涉及到的4个符号： 若将每安排一道工序称为“一步”。 设： ? St } ― 为第 t 步之前已排序工序构成的部分作业计划；? Ot } ― 为第 t 步可以排序的工序集合；Tk T?k ― 为? Ot }中工序 Ok 的最早可能开工时间； ― 为? Ot } 中工序Ok的最早可能完工时间。显然： Ok工序的作业时间 = T?k - Tk 55二、一般n/m/G/Fmax问题的启发式算法(一) 两种作业计划的构成P3101、能动作业计划的构成步骤 1. 2. 设t=1,? S1 }为空集， ? O1 }为各工件第一道工序的集合。 求T*=min|T’k|,并求出T*出现的机器M*。如果M*有多台，则 任选一台。3.4. 5.从? Ot }中挑出满足以下两个条件的工序Oj ，需要机器M*加工， 且Tj&T*。将确定的工序Oj放入? St } ，从? Ot }中消去Oj ，并将Oj的紧后 工序放入? Ot } ，使t=t+1。 若还有未安排的工序，转步骤（2）；否则，停止。例11.5：有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时 间矩阵T分别为：试构成一个能动作业计划。P310? 1,1,1 1,2,3 1,3,2 ? D?? ? 2,1,3 2,2,1 2,3,2 ? ? ? ?? 2 4 1? T ?? ? 3 4 5? ? ? ?? 按表11~9 所示的能动作业计划构成过程，可绘出图11~4能 动作业计划时间安排(排序)图―能动作业计划。57表11―9 能动作业计划的构成T *＝min {T?k}T*2t1 2 3 4 5 6? Ot }1, 1, 1 2, 1, 3 1, 2, 3 2, 1, 3 1, 2, 3 2, 2，1 1, 3，2 2, 2，1 1, 3，2 2, 3，2 2, 3，2Tk0 0 2 0 3 3 7 3 7 7 8T2 3 4 3 4 4 1 4 1 5 5T?k2 3 6 3 7 7 8 7 8 12 13M*M1Oj1, 1, 13 7 7 8M3 M3 M1 M1 M22, 1, 3 1, 2, 3 2, 2，1 1, 3，2 2, 3， 213' k ?1M2' T ? T Tk ?1, T } 或： k 下期工序最早可能开工时间：Tk ? max{ k ?1一个2/3/G/Fmax 问题 D=1,1,1 1,2,3 1,3 2 2,1,3 2,2,1 2,3,22,4,1 T= 3,4,558能动作业计划的甘特图； 最大流程：Fmax=13? 1,1,1 1,2,3 1,3,2 ? D?? ? 2,1,3 2,2,1 2,3,2 ? ? ? ?? 2 4 1? T ?? ? 3 4 5? ? ? ?M1 ―1,1,1 2 32,2,1 7 1,3,2 7 8 2,3,2 13M2 ―2,1,33 M3 ―1,2,37012345678 90123459(一) 两种作业计划的构成1、能动作业计划的构成步骤对表11~9所示的能动作业计划（作业时间排序）构成过程可描述为下列过程： （1）当 t =1时? O1 } 为：2个工件、可以在第1道工序上、进行第1步排序的集合， 即? O1 } = ? （1, 1, 1）；（2, 1, 3）} 。它们的最早可能开工时间 Tk = T1 =0。工序 （1, 1, 1）的最早可能完工时间 T?k = T?1 =2；工序（2, 1, 3）的T?k = T?1 =3，? T*= min ? T?k }=2。可见， T*= 2出现的机器 M*= M1。在这一步中M1上仅有 一道工序（1, 1, 1）可以排序。所以，首先安排（1, 1, 1）在M1上加工。 （2）、（3）…… （略） （4）当 t=4 时， ? O4 } = ? （1, 3, 2）；（2, 2, 1）}， T4 =7或3， T?4 =8或7。 T*=7，出现在M1上， ? 将（2, 2, 1）安排在M1上加工。 （5）…… （略） （6）当 t=6 时， ? O6 } = ? （2, 3, 2）}， T6=8， T?6 =13。 此时只剩下 （2, 3, 2）， ? 将（2, 3, 2）安排在M2上加工。 ?该排序问题最后完工时间为13。2、无延迟作业计划的构成(排序)步骤P311在作业计划中，“延迟”是指工件等待加工，而机器出现空闲 （空闲时间不能完成一道工序的加工作业）。所以，无延迟作业计划 是指没有任何延迟出现的能动作业计划。 无延迟作业计划的构成步骤 1. 设t=1,? S1 }为空集， ? O1 }为各工件第一道工序的集合。 2. 求T*=min|T’k|,并求出T*出现的机器M*。如果M*有多台，则任选一台。 3. 从? Ot }中挑出满足以下两个条件的工序Oj ，需要机器M*加工，且 Tj=T*。 4. 将确定的工序Oj放入? St } ，从? Ot }中消去Oj ，并将Oj的紧后工序放 入? Ot } ，使t=t+1。 5. 若还有未安排的工序，转步骤（2）；否则，停止。? 1,1,1 例：对例11.5：有一个2/3/G/Fmax问题， D?? ? 2,1,3 其加工描述矩阵D和加工时间矩阵T分别 ? 为：试构成一个无延迟作业计划。P3121,2,3 1,3,2 ? ? 2,2,1 2,3,2 ? ?M*M1? 2 4 1? T ?? ? 3 4 5? ? ? ?Oj1, 1, 1解：表11―10无延迟作业计划的构成t1 2 3 4 5 6? Ot }1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1 1, 3 2, 3 1, 3 2, 3 2， 1 3， 2 2，1 3， 2 3， 2 3， 2Tk0 0 2 0 3 3 7 3 7 7 12T2 3 4 3 4 4 1 4 1 5 1T?k2 3 6 3 7 7 8 7 8 12 13T*0 0 0 3 3 3 7 7 12M3 M3 M12, 1, 3 1, 2, 3 2, 2， 1M2 M22, 3，2 1, 3，2最大流程：Fmax=13 62无延迟作业计划的甘特图；最大流程：Fmax=13M1 ―1,1,1 2 32,2,1 7 2,3,2 1,3,2 12 13M2 ―72,1,33 M3 ―1,2,37012345678 90123463二、一般n/m/G/Fmax问题的启发式算法(二) 作业排序的三类启发式算法1、优先调度法 8个主要的优先调度法则：P312对应用优先调度法则的说明2.随机抽样法3.概率调度法( 见教材311~314页)(三) 优先调度法则例题(此为单台设备排序问题例题) 1、SPT法则(最短加工时间规则)例题 SPT法则就是优先选择加工时间最短的工序。即排序 时将各个工件的加工时间由短到长进行排队，排在前面的 加工时间最短的工序优先按排加工。其优点是，使平均流 程时间F最短，使在制品的占用量减少，其缺点是没有考 虑交货期，有可能会使部分工件延误了交货期。 例：现有一个6/1/F问题，其加工时间与交货期如表 11-10所示，试采用SPT法则进行作业排序。表11-10 加工时间与交货期表工序号 加工时间 交货期J1 4 24J2 8 23J3 2 8J4 5 6J5 9 32J6 3 131、SPT法则(最短加工时间规则)例题。解：(1)将各个工件加工时间由短到长排队为： J3 2，J6 3，J1 4，J4 5，J2 8，J5 9 (2)计算各工件加工流程时间，标在加工时间的右上角：2 32549514822931(3)计算平均流程时间 1 F = 6 ?(2+5+9+14+22+31)=13.8 (4) 统计延期交货状况： 表11-11 延期交货统计表 工 件号 J3 J6 J1 J4 J2 J5交货期di流程时间Fi=Ci 延期交货Li82 -6135 -8249 -15614 82322 -13231 -1由求解过程可知，按SPT法则排序顺序为：J3， J6， J1，J4， J2， J5； 流程时间分别为：2， 5 ， 9 ， 14 ， 22， 31；F=13.8；工件 J4 延期交货8个时间单位。其余提前完成转后例(三) 优先调度法则例题(此为单台设备排序问题例题) 2、EDD规则(最早预定交货规则)例题EDD规则就是优先选择完工期限紧的工件。即，在进行工件作 业排序时，按工件完工期限由紧到松进行排序，排在前面的完工期 限最紧的工件优先按排加工。EDD 法则的优点是考虑了交货期， 有利于做到按期交货，使工件中的最大延迟时间最小。其缺点是使 平均流程时间F增加，增大了在制品占用量。 例：(仍采用上例)有一个6/1/Lmax问题(即6个工件，1台机器，使最大 延迟时间最小)，其加工时间与交货期如表11-10所示。工序号 加工时间 交货期表11-10 加工时间与交货期 J1 J2 J3 J4 4 8 2 5 24 23 8 6J5 9 32J6 3 13试进行作业排序(使Lmax最小)。转前例(三) 优先调度法则例题(此为单台设备排序问题例题)2、EDD规则(最早预定交货规则)例题 解：根据EDD法则是将完工期限最紧的工序优先按排，为此 采用 表 11-12把 交货期短的工件先按排，再求出流程时间与交货期相比较， 检查是否存在有延迟时间的工件，延迟时间是多少，是否可以在排序 上再进行调整。 表11-12 延迟时间分析表 工 件号 交货期 加工与流程时 间 5 J4 65J3 87J6 1310J2 2318J1 2422J5 3231238490 0 0 0 0 0 延迟时间 由表11-12计算可知，该例采用EDD法则排序为： J4、 J3 、J6 、 J2 、J1、 J5，且各工件延迟时间均为0。平均流程时间 F=15.5(三) 优先调度法则例题(此为单台设备排序问题例题)3、SPT与EDD混合(结合)法则例题这是将SPT规则(最短加工时间规则)与EDD规则(最早预定 交货规则)结合起来的在单台设备上的排序方法。这种排序方法 克服了SPT与EDD两个单一规则只能达到一个目标的缺点，可 以获得较为理想的结果。为了说明问题方便，仍以表11-10所示 的排序问题为例。表11-10 加工时间与交货期表 J1 J2 J3 J4 4 8 2 5 24 23 8 6工序号加工时间 交货期J5 9 32J6 3 13(三) 优先调度法则例题(此为单台设备排序问题例题)3、SPT与EDD混合(结合)法则例题 按SPT与EDD结合的规则排序步骤如下：（1）首先根据EDD规则排序，即安排一个使Lmax?min(使最长延迟时间最短)的初步方 案。［若该初步方案出现Lmax = 0，说明该初步方案已满足要求。例如表11-10的例子， 可按交货期最短的先安排加工(即根据交货期排序)。所以，其排序为：J4 ― J3 ― J6 ― J2 ― J1 ― J 5按此排序可以求得： Lmax = max{Li}= -1，满足要求。］ （2）计算全部生产任务的总流程时间F总 = Fmax = max{Fi}= F5 =?Pi =P4 + P3 + P6 +P2+P1 + P5 =31 （3）找出初步方案中预定交货期大于Fmax 的工件(可能有多件)，并按SPT规则，把其中加工时间最长的工件排在最后加工。在本例中，预定交 货期大于Fmax=31 的工件只有J5，当然应该将 J5 排在最后加工。(三) 优先调度法则例题(此为单台设备排序问题例题)3、SPT与EDD混合(结合)法则例题 （4）舍弃第（3）步中已排在最后的J5，余下J4 ― J3 ― J6 ― J2 ― J1 重复第（2）步。此时出现情况如表11-13所示。表11-13 余下工件的F与预订交货期工件排序 加 工时间与F预定交货 期J456J35 28J67 313J210 823J118 42422由表11-13可知，余下5个工件中J1 的F最大， Fmax = 22。预定交货期大于Fmax = 22 的有J1 和J2 ，其中J2 的加工时间 P2=8为较大者(P2=8 & P1=4)，故按 SPT 规则将 J 2 排在第5顺序(倒数第2位)加工，即将 J2排在次后顺序上加工。(三) 优先调度法则例题(此为单台设备排序问题例题)3、SPT与EDD混合(结合)法则例题 反复进行（2）、（3）步，直到实现既使Lmax Q0，又使 F (平均流程时间 )为Fmin的排序方案为止。按 SPT与EDD结合规则排序，可得出表11-10的排序问题的排序为：J4 ― J3 ― J6 ― J1 ― J2 ― J5 表11-10排序问题的结论如表11-14所示。表11-14 排序方案及各参数结果表工件排序 加工时间与 F 预定交货期 计划完成时刻 交货延期平均流程时间 F=14.8 J6 J1 J2 J5J4 56 5 0J3528 7 07310 01042414823 22 022932 31 0311314 0第四节 多台设备作业排序一、多个工件在两台设备上的作业排序现有一个n/2/F/Fmax (n个工件，2台设备，流水作业排序问题，使 最长流程时间最短)问题。此问题可采用S.M.Johnson算。例：有一个7/2/F/Fmax 问题，其加工时间如表11-15所示，试进行作业排序。 表11-15 加 工 时 间 工件 Ji加工 时间J1 6J2 8J3 12J4 3J5 7J6 11J7 24M1M21195326182解：按照Johnson法则： （1）如果最短的加工时间出现在M1 上，则对应工件排在最前面(第一个)加 工，如果最短的加工时间出现在M2 上，则对应工件排在最后面(倒数第一个)加工， 如果最短的加工时间同时出现在M1 、 M2 上，则该工件排在最前或最后加工均可。（2）划去已排序工件，在余下来的未排序工件中仍然按上述方法进行作业排序， 直到全部工件安排完为止。 (自己练习)流水作业排序（4―1―5―2―6―3―7）（3）运用Johnson法则对此问题求解如表11-16和图11-3所示。 表11-16 加 工 时 间与排序结果表 工件 Ji加工 时间J16 11J28 9J312 5J43 3J57 26J611 18J724 2M1 M2 M1 M2工件排序结果加工 时间J43 3 3 J5 79J19 6J516 7J224 8 9J635 11J347 12J771 24 26J2 816 2420 11J6 11 J5 2646 26J3 12355518 J7 247357880J4 J1 M1 3 63M2J4 3J1 1147J2 955J6 1871J3 J7 5 278 803 69204673时间Fmax =80图11-3 作业排序甘特图二、多个工件在三台设备上的作业排序(采用Johnson法则)若存在一个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法则进行作业排序例：有一个4/3/P/ Fmax问题，其加工时间如表11-17所示 表11-17 加工时间表工件 设 备J115J28J36J412M1M2M3341105567试采用Johnson法则进行作业排序解： ① ∵ mint1i =6maxt2i =6存在mint1i ≥maxt2imint3i =4 mint2i =1 存在mint3i ≥ mint2i ∴可采用Johnson法求解该作业排序问题(具备其一即可)。 ② 计算tAi 和tBi，列于表11-18中 表11-18工件 设 备tAi 、tBi 与排序结果J118 7J29 11J311 10J418 13(MA) tAi (MB) tBi， 排序结果t1 i t2i t3iJ28 1 108 12J420 6J326 15J1419 6 19 726 5 33 531 3 38 444 48③ 依据11-18中的tAi 和tBi，采用Johnson法进行作业排序。排序 结果与Fmax如表11-18及图11-4所示。Fmax = 48 学生自己练习绘制排序结果甘特图J2M1 88J41220J3626J11541M218 9 20626531341 44M391019 26733538 44448时间图11-4 排序结果甘特图三、两个工件在m台设备上的作业排序（一） 用图解法求解 n个工件在m台设备上排序是比较困难的。但是，对于2个工件在m台设备上 排序问题，运用图解法虽然不一定求到最佳解，却可以求到比较令人满意的解。 例： 2个工件在4台机器上加工，每个工件的加工顺序不同。J1的加工顺序是 M1，M2，M3，M4；J2的加工顺序是M4，M2，M1，M3，其加工时间如表11-19所示。 显然，这是一个非流水作业排序问题，是一个一般的排序问题，故可用 2/4/G/Fmax表示，也可用2/4/G/Cmax表示。表11-19设备 工件 M1加工时间表M2 M3 M4J125541J2236该问题亦可用加工描述矩阵D与加工时间矩阵T表示为：1， 1 ? 1， D?? ? 2， 4 ? 1，1， 2， 2 2， 2， 21， 3， 3 2， 3， 11， 4， 4? ? 2， 4， 3? ??2 5 T ?? ?6 5 ?4 21? ? 3? ?第四节 多台设备作业排序?2 5 1， 1 1， 2， 2 1， 3， 3 1， 4， 4? ? 1， T ?? ? D?? ?6 5 三、两个工件在 m 台设备上的作业排序 ? 2， ? 4 2， 2， 2 2， 3， 1 2， 4， 3? ? ? 1，例，解：该问题可采用图解法求作业排序的解。 （1）画平面直角坐标，横、纵轴分别为J1、J2 的加工时间，对应横轴下部的 甘特图与对应纵轴左侧的甘特图分别表示J1、J2 加工顺序及其所对应的加工时间， 原点O为时间起点。找出表示J1、J2 总加工时间的坐标点D(12，16)。4 21? ? 3? ?（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刚好加工完J1。从B点开始，M2加 工J2， M3加工J1；接着M1加工J2， M4加工J1。到了C点(12,11)， M4刚好加工完J1， M2 刚好加工完J2。C点到D点是竖直线，此段时间 J1已加工完毕， M1和M3只加工 J2 。 79例，解： （3）由原点向D点引连线时，尽量按45° 角方向引线，并使等待时间最小。在实际操 作上，这种排序方法常常通过目视、徒手画 的方法完成的，所以，不能保证求得最佳的 排序结果，只能求得较令人满意的结果。从 作图求解过程可知： J1工件没有等待时间， F1max =12； J2 加工等待时间为1，所以， F2max =17。当然此问题也可写成 C1max =12； C2max =17。该图解法求解 2/4/G/ Cmax 问题 的过程如图11-5所示。J216图11-5 图解法求解2/4/G/Cmax过程图? D(12,16)M313 11III I II? ? ? C(12,11)M1M26A(6,6) M4B(7,6)IV450M1M22 7M3M411 12J181三、两个工件在m台设备上的作业排序例，解： 上述作业 排序问题2/4/G/Fmax ,?2 T ?? ?6 ?J1M1 M2 M35 54 2? 1,1,1 D?? ? 2,1,4 ?1? ? 3? ?1,2,2 2,2,21,3,3 2,3,11,4,4 ? ? 2,4,3 ? ?的排序结果如图11-6所示。J21,1,1（2） 22,3,1J1 J2712 （2）141,2,22 （5）2, 2, 2 2,2,2J1（5）12J21,3,3J27 （4）2,4,311J114 （3） 17M42,1,4（6）(1,4,4)Fmax = Cmax =17611 12（1）o图11-6作业排序甘特图时间三、两个工件在m台设备上的作业排序（二） 用启发式算法求解 1、请同学们按能动作业计划构成步骤求解。 前述的2/4/G/Fmax ,? 1,1,1 D?? ? 2,1,4 ??2 T ?? ?6 ? 5 51,2,2 2,2,24 2 1? ? 3? ?1,3,3 2,3,11,4,4 ? ? 2,4,3 ? ?可采用按能动作业计划构成步骤求解，其求解(排序)过程及结果如表11-20与图11-7所示。 83表11―20t1 2 3 4能动作业计划构成表Tk0 02 0? Ot }1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 3, 2, 4, 2, 1 4 2 4 2 2 3 2 4 2T?k2 67 6T*2M*Oj1, 1, 1M16M4M2 M3 M2 M42,1, 42 77 7 11 7 11 127 1211 12 12 12 12 147111, 2, 2 1, 3, 356 712 122, 2,21, 4, 4 2, 3, 11, 4, 4 2, 3, 1 2, 4, 3842, 3, 1 2, 4, 32, 4, 312 141414 17171417M1 M38（二） 用启发式算法求解1、按能动作业计划构成步骤求解? 根据11-20可绘出如图11-7所示的该问题作业排序甘特图。由图11-7可见， 采用启发式算法，按能动作业计划构成步骤进行求解，作业排序结果甘特 图与图解法得出的图11-6所示的甘特图相同，说明两种方法求解结果相同。J1 M1 1,1,1（2） 2J2 2, 3,1M2 M31, 2, 22 （5）J1J212 （2）142, 2, 277 （5）1, 3, 3J2（4）J112 112, 4, 314 （3） 17J2J16 11 12（1 ）M42, 1, 4（6）(1,4,4)Fmax = Cmax =17o图11-7 作业排序甘特图时间85（二） 用启发式算法求解2、按无延迟作业计划构成步骤求解 1,2,2 ? 1,1,1 前述的2/4/G/Fmax , D ? ? ? 2,1,4 2,2,2 ?1,3,3 2,3,11,4,4 ? ? 2,4,3 ? ??2 T ?? ?6 ?5 54 21? 可采用按无延迟作业计划构成步骤求解， ? ? 3?其求解(排序)过程及结果如表11-21与图11-7所示。(见下一页) 由表11-2中的 M* 栏与 Oj 栏可看出，构成作业计划(排序)中所 选中的设备与工件及其安排次序均与表11-20相同，说明排序结果 相同，绘出的表示作业排序结果的甘特图肯定也与图11-7相同，这 里不再另外绘出。表11~21 t12无延迟作业计划的构成表Tk0 0 2 0 2 7 7 7 11 7? Ot }1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 2, 2, 3, 2, 4, 2, 4, 3, 3, 4, 1 4 2 4 2 2 3 2 4 2 4 1 1 3T?k2 6 7 6 7 12 11 12 12 12T*0 0 0 2 7 7 7M* M1 M4 M4 M2Oj1, 1, 12,1, 434 5 6 7 81, 2, 2 1, 3, 3 2, 2, 1, 4, 4 2, 3, 1 2, 4, 387M3 M2M2 M4 M1 M3211 1212 14 1412 1414 17 171112 142, 4, 3(Fmax = Cmax =17)课堂练习１、5种零件在三台机床上的加工时间如下表所示。表1零件加工时间表（小时）零件 机床 M1 J1 3 J2 5 J3 6 J4 5 J57 26M2M325333412请用约翰逊法则排序并计算最大流程时间。 882、两种零件的加工描述矩阵Ｄ和加 工时间矩阵Ｔ如下。1,1,1 1,2,2 1,3,3 1,4,4 2,1,1 2,2,4 2,3,2 2,4,3 2 1 8 2 T＝ 1 4 1 4Ｄ＝请用能动作业计划表（图解法）确定两种零件的投产方案并绘制甘特图确定加工作业周期．891题解答：n/3/P/Fmax问题，满足mint1i ≥maxt2i 或mint3i ≥ mint2i ( i =1，2，……，n)，则可采用Johnson法排序。求解步骤为： （1）判断mint1i =3≥maxt2i=3或mint3i = 2≥ mint2i1满足关系.可以应用Johnson法排序. （2）将3台设备变换成2台假想设备MA和MB，并令tAi = t1i + t2i ； tBi = t2i + t3i （3）依据 tAi 和tBi，采用Johnson法则进行作业排序 零件 机床 M1 M2 M3 J1 3 2 5 零件 J2 5 3 3 J1 J3 6 3 4 J2 J3 J4 5 1 2 J4 J5 7 2 6 J5 9 890假想机床 T1i=M1i+M2i5 78 69 76 3T2i=M2i+M3i结果为:J1―J5―J3―J2―J4零件 机床 M1 M2 M3 J1 3 2 5 J5 J3 J2 J43 5 107 2 61012 186 3 41619 235 3 32124 275 1 22627 29最大流程时间Fmax=29（小时） 91图 解 法 确 定 两 种 零 件 的 投 产 方 案2题解答：图解法确定两种零件的投产方案并绘制甘特图 2 1 8 2 1,1,1 1,2,2 1,3,3 1,4,4 T＝ 1 4 1 4 Ｄ＝ 2,1,1 2,2,4 2,3,2 2,4,3 J210 9?Q(13,10)M38 7IIIF2=15=2+1+4+1+3+2+2M26 5 4IIF1=16=1+4+1+(6)+2+2M43 2 1IVM10I0 1 2 3 4 5 6 7 8 9 0 1 2 3J192M1M2M3M4? 第二方案甘特图Fmax=15(小时)J2 1,1,1 2,1,1 2 3 J1 1,2,2 2 3 J2 2,3,2 7 8 J1M1M2M31,3,33 112,4,315J2J1M42,2,43 71,4,411 130123456789 012345时间（小时）93排序问题作业练习：P321― 1，2补充4:有一个2/5/G/Cmax的问题。零件1的工艺路线次序为经 过机器：1，2，3，4，5；零件2的工艺路线次序为经过机 器：4，1，2，5，3，工序加工时间见下表。试用图解法求 完成总时间最少的排序，并绘出甘特图。 机床 零件号 M1 机器号 M2 M3 M4 M512243142622 594第五节生产作业监控与调度规则? 生产作业计划实施过程总会出现一些难以预见防碍的因素。因此，要 对生产的全过程进行监控，及时发现计划执行中已发生或即将发生的 各种偏差,并采取措施预防和纠正它。作业监控是生产管理工作的基本 职能之一。 ? 在编制生产作业进度计划时，一般考虑静态情况较多，只有当生产因 素比较稳定和比较理想的情况才能得到最优化。但在动态的生产实施 过程中，影响生产实施的一些因素会发生变化，如零件加工时间有随 机性，原材料供应误期，上一工序延期交付，零件加工中的报废，工 具，设备发生故障，工人缺勤等等；以及外部因素，如市场需求发生 变化而影响生产计划的数量来因此，在生产实施时期，生产控制必须 及时、全面地了解和掌握生产过程情况，采取有效措施保证完成计划 期内预定的生产目标。这对多品种的成批和单件批小生产尤为重要。 95一、生产控制功能生产控制包括以下两个基本功能： 1? 生产系统控制 生产系统控制是控制从原材料到最终产品的物质流。包括： 控制时间（交付期）和产量的生产控制（狭义的生产控制）； 保证产品具有要求的质量和可靠性的质量控制；控制原材料、 产品的库存控制；生产过程中的成本控制等。 2．生产资源控制 生产资源控制主要是指对生产设备的控制功能。它的基本 活动是防止生产设备损坏和修复已损坏的生产设备，即生产设 备的维修工作。96二、对时间和产量的生产控制生产进度计划规定的产量和进度（或交付日期）是生产实 施阶段的生产标准。经常检查实际产量和完工时间并和计划标 准比较，如果发生偏差，就要采取有效措施以保证完成计划。 图11－28是表示生产控制的一般反馈过程。对计划进度与实际 实施情况发生的偏差，应及时报告有关管理人员和领导，迅速 作出决策以追补或调整偏差。生产标准： 计划产量与时间 生产 实施 度量生产效果、 实际产量与时间修正偏差比较计划与 实际效果97图10－28生产控制系统反馈过程对时间（进度）和产量的生产控制，要求经常检查车间（或工段）之 间、车间内部的产品（零件、部件、毛坯）的交付期限，原材料供应和投 入情况，以及生产过程中的库存的在制品储备情况。对生产实施情况的检 查，传统的办法是利用各种形式的图表来对比出产量的计划进度和实际进 度。如用横道图表示的产品（零、部件）出产量进度完成情况如图表、产 品配套计划完成情况图表以及主要零件各道工序的进度完成情况图表。对 于在制品的库存和周转情况也可采用各种形式的图表对比检查。 除了检查生产进度完成情况外，还应检查和督促生产准备工作进行情 况，劳动力配备情况，设备运转和维修情况，运输、动力运行情况以及主 要的技术关键等情况。 生产控制工作要求反映情况的及时性、准确性、全面性；作出决策处 理问题的迅速性。计算机辅助生产信息系统，有利于实现这些要求。从数 据的收集、数据存储、数据取出、数据处理、数据传输到数据显示，它使 生产系统能够适时地精确地处理各种信息，作出适当的决策，采取相应的 措施，从而适应动态地变化着的外部环境。98三、调度规则我们在安排进度计划时，介绍了零件加工的排序寻忧解法。这些解法 都是处理静态问题的；如果出现动态情况，就没有一般求最优解的方法。 当有一个以上工件在机床前排队时，必须确定这些工件的加工次序。 规定机床在加工完一种零件后，接着应加工哪一种零件。在动态加工车间 内，这种进度决策，通常是利用调度（或优先）规则来确定的。有了某一 适当的优先规则，对动态加工车间的进度可以做模拟研究和实验。 当一个车间或工段内加工许多项订货或零件，每项订货或零件又都需 要由许多道工序来完成，而且每项订货或零件所经历的工序内容与次序又 都是不同的。究竟应该如何安排才能取得较好的经济效益，用上述排序的 办法就难以解决这类问题。人们探求其中的规律性，看是否有简单的判别 准则可以应用？ 这类生产中的主要矛盾是在设备和工人的负荷率与在制品资金占用之 间发生的。若要使工人与设备有高的利用率，就必须有大量的订货（零件） 等待着以减少窝工。其结果是在制品占用资金过高以及在安排进度方面的 困难。如果要符合每项订货（零件）按时交货，必须拥有大量的工人与设 备，使每项订货（零件）都不需要等待，势必使工人与设备负荷率下降， 而得到的好处则是在制品占用资金的减少。如何来解决这个复杂系统中的 这对矛盾呢？目前一直集中注意于系统模拟技术，先根据不同要求制定一 些判别准则，运用于生产进度的安排以期取得良好的效果。 99美国休斯飞机公司的勒裕朗德用六种不同的调度规则在加工车 间中进行模拟试验，并用某些评价标准来衡量其结果以作出效 果优劣的判断，他在研究中所用的调度规则有：1.工序加工工时最短（SOT）在设备前排队等候加工的订货（或零件）中 选择加工时间（含准备结束时间）最短的优先加工。 2.工序富裕时间最少也称为待加工工序动态富裕时间最少（DS／RO）的 原则。就是下一个要加工的订货是该项订货总的剩余时间（交货日期减去 目前的日期）减去订货待加工时间，再除以待加工的工序数目。从这批待 加工的订货（零件）中选择这个数字最小（即最紧急）的先安排加工。 3.先来先做（FCFS）这个规则是按订货（零件）送到加工设备前的先后次 序顺序排队，谁先来先为谁服务。 4.计划开工最早（MINSD）按这条规则，先加工的订货（零件）是计划最 早开工日期的订货。也就是按原来理论计算的最早开工的订货（零件）先 安排加工。 5.订货最早到期（FISFS）这个规则是按订货（零件）到期日期排队，先交 货的先加工。 6.随机选择（RAND）这条规则没有特定的优先次序。 1006.随机选择（RAND）这条规则没有特定的优先次序。是从所有等待加工 的订货（零件）中随机地选出。 在评价各种不同的模拟类型时，所用的判别优劣的标准如下： （1）按期完成的订货数。 （2）延期完成的订货的百分比。 （3）订单完成额的分布的平均数。 （4）订单完成额分布的标准偏差。 （5）在车间等待的订单平均数。 （6）订单的平均等候时间。 （7）订单排队的每年成本负担。 （8）等待期间在制品占用费用与加工时间在制品占用费用的比例。 （9）工时利用率。 （10）设备利用率。 加工车间模拟装配的特征见图11―29 101图10―29 加工车间模拟装配的总特征 输 入评价签定 评价报告，检查有麻烦的地 方，考虑操作判断上的变动和 其他可控制的输入参数。 输 出 报 告 1、机器负荷分析 2、车间工作成绩 3、工时利用率 4、等候排队统计 a．来货和交货 b．等待时间 c．排队的长度 5、已存货占用的费用 6、订单完成情况 模 拟 计算机在指定时间内模拟加工车间。 安排提供订单的进度，把它们发交车 间。分配给能够承办的机器与工人， 追踪检查机器负荷，机器和工时的利 用率，等待时间，等待着的加工数， 存货占用的费用，及时完成，提前完 102 成，以及延期完成的各工件的数目。1. 资 源 3. 进度计划和调度 1、机组和工种 1、编制进度计划的程序 2、每班机器数和人数 2、调度规则 3、每小时机动时间比率 4、轮班数 3、每机组的提前期 5、每班工作钟点 4. 其 他 2. 订 单 1、订单号数 1、模拟时间段数 2、数量 3、交货日期（按合同要求） 2、每段时间的日数 4、原始价值 3、每机组转运时间 5、工作顺序 6、每个工序的准备时间与 4、迟到次数和时间 加工时间 5、允许的起动时间 7、工作进行的机组 6、交班调整时间 8、订单交来的频率 9、订单撤消的频率 7、其他项目 10、原始负荷订单数六种判别准则其模拟后的结论是：如果对前述十项判别准 则同等重视来评价的话，工时最短（SOT）的准则效果最好；如 果注重订货的按时交货，即在评价时给它以高的权数，则待加 工工序富裕时间最少（DS／RO）作为判断准则较好；如果领导 重视按期完工，则以交货日期到期最早（FISFS）原则最好。调度规则 提前完成百分比 如期完成百分比 延迟完成百分比 完成额的平均数（日数） 标准偏差（日数） 完成订单总数 计划动工 最早 (MINSD) 54 6 44 3.0 9.2 3118 先来先做 (FCFS) 57 5 38 3.6 10 3190 先到期 先做 (FISFS) 63 5 32 4.2 8.2 3484 动态富裕 时间最少 (DS／RO) 68 12 20 4.2 8.2 3217 随机选择 工时最短 (RAND) (SOT) 65 5 30 5.2 10.4
24 6.6 9.9 3708103作业题? P321――1，2，3104
第10 章内部排序 习题练习答案 1.以关键字序列(265,301,751,129,937,863,742,694,076,438)为例,分别写出执行以下排序算法 的各趟排序结束时,关键字序列的...生产运营管理第10章回家作业和答案_管理学_高等教育_教育专区。生产运营管理计算题和答案第10 章回家作业练习题 3、某网络计划如下图所示 ,箭杆上方为各作业的作业...作业:生产管理学-第3章... 作业:生产管理学-第8章... 作业:生产管理学-第...上层元件的计划发出订货量 E.所有以上因素 计算题 1.完成表 10-7 的处理过程...第10章 GMP良好生产作业规范和卫生标准操作程序(SSOP)_建筑/土木_工程科技_专业资料。浙江科技学院《食品安全与质量控制》教案 作业规范 第 10 章 GMP(良好作业规...第八章 生产作业排序 47页 2下载券 作业排序 18页...38 10.若一组记录的排序码为(46, 79, 56, 38...网络营销部电商运营工作计划80份文档 家装材料选购攻略...9.数据结构作业答案第9章排序作业题答案 隐藏&& 第9章 排序 自测卷题号 题分 得分 一 24 二 18 三 36 姓名四 8 五 14 班级总分 100 一、填空题(每空...《算法设计与分析》上机操作作业实验名称:背包问题和带时限的作业排序 实验章节:算法设计与分析 第 6 章 实验目的:掌握贪心算法解决问题的思想和一般过程,学会使用...作业:生产管理学-第9章... 作业:生产管理学-第10章...1/2 相关文档推荐 ...A.粗略能力计划 B.物料需求计划 C.能力需求计划 D.库存计划 5. 制定生产大纲...郑州大学远程教育学院作业计划生产管理学》第08章在线测试_管理学_高等教育_教育...作业排序 3、以下关于排序说法中正确的是___ A、单台机器的排序不一定简单...《大学语文》第2次作业答案已排序_临床医学_医药卫生_专业资料。( )标志着文言短篇小说的成熟: C.唐传奇 ( )标志着文人传奇的基本确立。A.《浣纱记》 《古诗...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。