生产运作管理-制造业作业计划与控制.ppt

《生产运作管理-制造业作业计划与控制.ppt》由会员分享，可在线阅读，更多相关《生产运作管理-制造业作业计划与控制.ppt（108页珍藏版）》请在装配图网上搜索。

1、第十一章 制造业作业计划与控制 引言 通过 MRP确定各车间的零部件投入出产计划， 从而将全厂性的产品出产计划变成了各车间生 产作业计划，将车间的生产任务变成各个班组、 各个工作地和各个工人的任务。只有将计划安 排到工作地和工人，任务才算真正落到实处。 将任务安排到工作地，牵涉到任务分配和作业 排序问题，这正是本章要讨论的。 11.1 作业计划问题的基本概念 11.2 流水作业排序问题 11.3 单件作业的排序问题 11.4 生产作业控制 11 收入、费用和利润 要求掌握： 1.最长流程时间的计算 2.约翰逊算法 3.一般流水作业排序问题的 3种启发式算法 4. 相同零件的 3种移动方式下机器

2、加工周期的计算方法 学习目的与要求 重点 最长流程时间的计算 约翰逊算法 相同零件的 3种移动方式下机器加工周期的计算方法 难点 一般流水作业排序问题的启发式算法 教学重点与难点 生产任务的最终落实 MRP确定各车间的零部件投入出产计划，将全 厂性的产品出产计划变成了各车间的生产任务。 各车间要将车间的生产任务变成各个班组、各 个工作地和各个工人的任务。 将任务安排到工作地，牵涉到作业计划。 编制作业计划要解决的问题 由于每台机器都可能被分配了多项任务，就带来了 零件在机器上加工的顺序问题。 编制作业计划要解决先加工哪个工件、后加工哪个 工件的加工顺序问题 确定机器加工每个工件的开始时间和完成

3、时间 例如 ;医院要安排病人手术，为此要安排手术室， 配备手术器械、手术医师和护士。 第一节 排序问题的基本概念 一、名词术语 排序：确定工件在机器上的加工顺序。 作业计划：不仅要确定工件的加工顺序，而且还 要确定机器加工每个工件的开始时间和完成时间。 通常情况下都是按最早可能开（完）工时间来编 制作业计划。 派工：按作业计划的要求，将具体生产任务安排 到具体的机床上加工。 赶工：实际进度已落后于计划进度时采取的行动。 “机器 ” ，可以是工厂里的各种机床，也可以是维 修工人，表示 “ 服务者 ” “ 零件 ” 代表 “ 服务对象 ” 。零件可以是单个零 件，也可以是一批相同的零件 “ 加工顺

4、序 ” 则表示每台机器加工 n个零件的先后 顺序，是排序和编制作业计划要解决的问题 二、假设条件和符号说明 假设条件： 1.一个工件不能同时在几台不同的机器上加工。 2.工件在加工过程中采取平行移动方式，即当上一道 工序完工后，立即送下道工序加工。 3.不允许中断。一个工件一旦开始加工，必须一直进 行到完工，不得中途停止插入其他工件。 4.每道工序只在一台机器上完成。 5.工件数、机器数和加工时间已知，加工时间与加工 顺序无关。 6.每台机器同时只能加工一个工件 有关符号 Ji：工件 i， i=1， 2， ， n Mj：机器 j， j=1， 2， ， n pij为 Ji在 Mj上的加工时间 r

5、i为 Ji的到达时间，指 Ji从外部进入车间，可以加工的最 早时间 di为 Ji的完工期限 Ci为 Ji的完工时间 Cmax为最长完工时间 Fi为 Ji的流程时间，即工件在车间的实际停留时间 Fmax为最长流程时间 Li为工件的延迟时间 Lmax为最长延迟时间 三、排序问题的分类 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 对于多台机器排序问题，根据加工路线的特征，分成 单件作业排序 (Job - Shop)问题 流水作业排序 (Flow - Shop)问题 工件的加工路线不同，是单件作业排序问题的基本特征； 所有工件的加工路线完全相同，是流水作业排序问题的 基本特征。也就是说，

6、每个零件都顺序地经过线上不同 机器加工，它们的加工路线一致。 根据工件到达系统的情况 静态排序 动态排序 根据参数的性质 确定型排序 随机型排序 4参数法 n/m/A/B 其中， n为工件数 m为机器数 A车间类型。在 A的位置若标以标以 “ P”，则 表示 流水作业排列排序 问题；若标以 “ G”， 则表示一般单件作业排序问题。当 m=1，则 A处为空白。 B为目标函数，通常是使其值最小 例如： n/3/P/Cmax 四、作业排序方案的评价标准 1.工作流程时间 从工件可以开始加工至完工的时间，包括在各个机器 之间的移动时间、等待时间、加工时间以及由于机器 故障、部件无法得到等问题引起的延误

7、时间等。 2. 加工周期 完成一组工作所需的全部时间。它是从第一个工件在 第一台机器上开始加工时算起，到最后一个工件在最 后一台机器上完工时为止所经过的时间。 3.在制品库存（ WIP） 在制品是对介于原材料和成品之间的生产过程中 的产品的称谓。一个工件正从一个工作地移向另 一个，由于一些原因被拖延加工，正在被加工或 放置于零件库中，都可以看作在制品库存。 4.利用率 用一台机器或一个工人的有效生产时间占总工作 时间的百分比来表示。 五、优先调度规则 调度方法： 所谓调度方法，就是运用若干预先规定的优先顺 序规则，顺次决定下一个应被加工的工件的排序 方法。 一个工作地可选择的下一个工件会有很多

8、种，因 此，按什么样的准则来选择，对排序方案的优劣 有很大影响。 常用的优先顺序规则： FCFS规则 优先选择最早进入可排序集合的工件。 EDD规则 优先选择完工期限最紧的工作。 SPT规则 优先选择加工时间最短的工件。 SCR规则 优先选择临界比最小的工件。临界比为工作 允许停留时间和工件余下加工时间之比。 MWKR规则 优先选择余下加工时间最长的工件。 LWKR规则 优先选择余下加工时间最短的工件。 MOPNR规则 优先选择余下工序数最多的工件。 RANDOM规则 随机地挑选下一个工件。 一般作业排序的目标 满足顾客或下一道工序的交货期要求 流程时间最短 准备时间最短或成本最小化 在制品库

9、存最低 机器设备或劳动力利用最大化 例 一个加工车间负责加工发动机机壳，现在共有 5个机壳 等待加工。只有一名技工在岗，做此项工作。现在已经估算 出各个机壳的标准加工时间，顾客也已经明确提出了他们所 希望的完工时间。下表显示了周一上午的情况，顾客的取货 时间用从周一上午开始，还有多少工作小时来计算。 发动机机壳 所需标准加工时间 （包括机器调整） 预计顾客取货时间 （从现在开始算起的所需工作 时间） 机壳 1 8 10 机壳 2 6 12 机壳 3 15 20 机壳 4 3 18 机壳 5 12 22 机壳加 工次序 开始 工作 加工 时间 结束 工作 流程 时间 预计顾客 取货时间 顾客实际

10、 取货时间 提前 小时数 拖延 小时数 机壳 4 0 3 3 3 18 18 15 机壳 2 3 6 9 9 12 12 3 机壳 1 9 8 17 17 10 17 7 机壳 5 17 12 29 29 22 29 7 机壳 3 29 15 44 44 20 44 24 总数 102 120 18 38 平均数 20.4 3.6 7.6 平均在制品库存 =102/44=2.32个 平均总库存 =120/44=2.73个 SPT规则排序结果 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来 取货；如果有拖延发生，他们将在加工结束时马上取走。 流程时间 =等待时间 +加工时间 平均在制

11、品库存 =各工件流程时间之和 加工周期 平均总库存 =各工件实际取货时间之和 加工周期 机壳加 工次序 开始 工作 加工 时间 结束 工作 流程 时间 预计顾客 取货时间 顾客实际 取货时间 提前 小时数 拖延 小时数 机壳 1 0 8 8 8 10 10 2 机壳 2 8 6 14 14 12 14 2 机壳 4 14 3 17 17 18 18 1 机壳 3 17 15 32 32 20 32 12 机壳 5 32 12 44 44 22 44 22 总数 115 118 3 36 平均数 23.0 0.6 7.2 平均在制品库存 =115/44=2.61个 平均总库存 =118/44=2

12、.68个 EDD规则排序结果 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来 取货；如果有拖延发生，他们将在加工结束时马上取走。 比较 SPT规则和 EDD规则的排序结果，用 SPT规则排序，其平均流程 时间更短，在制品库存更少。用 EDD规则，可以给顾客提供更好的服务 （平均延迟时间较少），它也提供了更低的总库存水平。 优先调度法则 按 SPT法则可使工件的平均流程时间最短，从而减 少在制品量。 FCFS法则来自排队论，它对工件较公平。 EDD法则可使工件延误时间最小。 MWKR法则使不同工作量的工件的完工时间尽量接 近。 LWKR法则，使工作量小的工件尽快完成。 第二节 流水作

13、业排序问题 流水作业排序问题的基本特征是每个工件的加工 路线都一致。 加工路线一致，是指工件的流向一致，并不要求 每个工件必须经过加工路线上每台机器加工。 对于流水作业排序问题，工件在不同机器上的加 工顺序不尽一致。 排列排序问题：所有工件在各台机器上的加工顺 序都相同的情况。 一、最长流程时间 Fmax的计算 n/m/P/Fmax问题， n个零件要按相同的加工路线经 过 m台机器加工，目标是使这批零件的最长流程时 间最短。 最长流程时间 又称加工周期，它是从第一个零件 在第一台机器开始加工时算起，到最后一个零件 在最后一台机器上完成加工时为止所经过的时间。 例 有一个 6/4/P/Fmax问

14、题，其加工时间如下表所示。当 按顺序 S=（ 6， 1， 5， 2， 4， 3）加工时，求 Fmax。 i 1 2 3 4 5 6 4 2 3 1 4 2 4 5 6 7 4 5 5 8 7 5 5 5 4 2 4 3 3 1 1iP 2iP 3iP 4iP i pi 1 p i 2 p i 3 p i 4 6 1 5 2 4 3 2 5 5 1 4 4 5 4 4 4 5 3 2 5 8 2 1 7 5 3 3 6 7 4 2 6 10 12 13 16 7 11 15 20 27 33 12 17 22 30 35 42 13 21 25 32 38 46 二、两台机器排序问题 两个或更多

15、的作业必须在两台机器上以相同的工序进行加 工，要使加工周期最短，约翰逊于 1954年提出了一个有效 算法，那就是著名的 Johnson算法 。约翰逊算法包括以下 几个步骤： （ 1）列出每个作业在两台机器上的加工时间。 （ 2）选择最短的加工时间，如果有两个相同的值，则任 选一个。 （ 3）如果最短的加工时间来自第一台机器，那么先完成 这个作业；如果来自第二台机器，那么这个作业就放在最 后完成。然后从加工时间矩阵中划去已排序工件的加工时 间。 （ 4）对于剩余的作业重复第二步和第三步，直到整个排 序完成。 【 例 】 求如表所示的 6/2/F/Fmax问题的最优解。 i 1 2 3 4 5 6

16、 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4.5 将零件 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 【 例 题 】 有 5件任务都需要两步操作（先 1后 2）来完成，下表给出了相 应的时间： （ 1）根据 Johnson算法安排工作顺序； （ 2）计算加工周期。 任务 操作 1所需时间（小 时） 操作 2所需时间（小 时） A 3.0 1.2 B 2.0 2.5 C 1.0 1.6 D 3.0 3.0 E 3.5

17、1.5 任务 操作 1所需时间（小时） 操作 2所需时间（小时） A 3.0 1.2 B 2.0 2.5 C 1.0 1.6 D 3.0 3.0 E 3.5 1.5 A,3.0 E,3.5 D,3 B,2 C,1 1.0 3.0 6.0 9.5 12.5 0 操作 1 A, 1.2 E,1.5 D,3.0 B,2.5 C,1.6 2.6 5.5 9.0 11 13.7 操作 2 A,3.0 E,3.5 D,3 B,2 C,1 1.0 3.0 6.0 9.5 12.5 0 操作 1 A, 1.2 E,1.5 D,3.0 B,2.5 C,1.6 2.6 5.5 9.0 11 13.7 操作 2 i

18、 C B D E A 操作 1 操作 2 11 6.26.1 32 63 5.95.3 5.120.3 5.55.2 0.90.3 115.1 7.132.1 【 例 题 】 根据 Johnson算法求以下 8/2/F/Fmax问题的最优解。 任务 ai bi A 9 6 B 7 2 C 10 3 D 8 1 E F G H 2 1 5 4 5 8 7 4 1. 将所有 ai bi的工件按 ai值不减的顺序排 成一个序列 A； 2. 将 ai bi的工件按 bi值不增的顺序排成一个 序列 B； 3. 将 A放到 B之前，就构成了一个最优加工顺 序。 改进算法 工件号 1 2 3 4 5 6 a

19、i 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 1 4 8 13 18 26 3 11 15 22 26 28 ai bi 最优顺序下的加工周期为 28 练 习 某公司要生产 4种产品，需要两台机器 1和 2。其中，有 3种 产品需要先在机器 1上加工。下表给出了两台机器上加工 各产品所需的时间。 （ 1）安排生产顺序，使得在最短时间内完成生产。 （ 2）机器 1共需工作多长时间？ （ 3）机器 2应该在机器 1开始工作后多长时间开始运转？ 任务 在机器 1上加工所需时间 （小时） 在机器 2上加

20、工所需时间 （小时） A 3.2 2.10 B 2.5 1.25 C 1.7 3.00 D 2.1 0 任务 在机器 1上加工所需时 间（小时） 在机器 2上加工所需时 间（小时） A 3.2 2.10 B 2.5 1.25 C 1.7 3.00 D 2.1 0 9.5 B,1.25 A,2.10 C,3.00 D,2.1 B,2.5 A,3.2 C,1.7 1.7 4.9 7.4 4.7 6.8 8.65 机器 1 机器 2 三、一般 n/m/P/Fmax问题的启发式算法 启发式算法是一个基于直观或经验构造的算法，在可 接受的花费 (时间、占用空间等 )下给出待解决组合优 化问题的可行解 。

21、 启发式方法因其易于实现、计算复杂度低等原因，目 前应用得最为广泛。 （一） Palmer法 1965年， D S Palmer提出按 斜度指标 排列工件的启 发式算法，称之为 Palmer法。 工件的斜度指标可按下式计算： k=l， 2， ， m 式中， m为机器数； pik为工件 i在 Mk上的加工时间。 按照各工件 i不增 的顺序排列工件，可得出令人满意 的顺序。 ikm k i pmk 1 2/)1( m,2,1k2/)1( 1 ， m k iki pmk 31i3m ii pp 时，当 4321 5.15.05.05.14m iiiii pppp 时，当 54321 21025m i

22、iiiii ppppp 时，当 例 有一个 4/3/F/Fmax问题，其加工时间如下表所示，试用 帕尔默法求最优顺序。 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 解：对于本例， i = Pi1 Pi3 于是， 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) 和 (2， 1， 3， 4)，恰好这两个顺序都是最优顺序。如不是这 样，则从中挑选较优者。在最优顺序下， F max

23、=28。 321k2/)13( 1 ， ik m k i pk （二）关键零件法 步骤如下： （ 1）计算每个零件的总加工时间，找出加工时间最 长的零件 C，将其作为关键零件。 （ 2）对于余下的零件，若 pi1p im，则按 pi1不减 的顺 序排成一个序列 Sa；若 pi1p im，则按 pim不增 的顺序排 成一个序列 Sb。 （ 3）顺序（ Sa， C， Sb）即为所求顺序。 i 1 2 3 4 pi1 1 2 6 3 pi2 8 4 2 9 pi3 4 5 8 2 pi 13 11 16 14 例 有一个 4/3/F/Fmax问题，其加工时间如下表所示，试用 关键零件法求最优顺序。

24、解：总加工时间最长的为 3号零件， pi1p i3的零件为 1和 2， 按 pi1不减的顺序排成 Sa=（ 1， 2）； pi1 pi3的零件为 4号零 件， Sb=（ 4） ,这样得到的加工顺序为（ 1， 2， 3， 4）。 例 题 用关键工件法求解下表的 最优排序。 解：总加工时间最长的为 2 号零件， pi1p i4的零件为 1和 3，按 pi1不减的顺序排 成 sa=（ 1， 4）； pi1 pi4的 零件为 4号零件， sb=（ 3）， 这样得到的顺序为（ 1， 4， 2， 3）。 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6

25、 2 3 7 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6 2 3 7 pi 16 24 17 19 （三） CDS法 康坎贝尔 -杜德克 -史密斯三人提出了一个启发式算法，简 称 CDS法。 具体做法是，对加工时间 用 Johnson算法求（ m-1）次加工顺序，取其中最好的结果。 。，和 1m21p m l-1mk ik 1 lp l k ik 。，和 1m21p m l-1mk ik 1 lp l k ik m=2时， l=1,加工时间分别为 pi1和 pi2； m=3时， l=1,2,加工时间分别为 ： （ 1） l=1， pi

26、1和 pi3 （ 2） l=2,pi1+pi2和 pi2+pi3 m=4时， l=1， 2， 3，加工时间分别为： （ 1） l=1,pi1和 pi4 （ 2） l=2， pi1+pi2和 pi3+pi4 （ 3） l=3， pi1+pi2+pi3和 pi2+pi3+pi4 l A 加工时间 B 加工时间 1 t 1 t m 2 t 1 +t 2 t m-1 +t m 3 t 1 +t 2 +t 3 t m-2 +t m-1 +t m m-1 t 1 +t 2 + +t m-1 t 2 + +t m- 1 +t m i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4

27、 5 8 2 2)1(p m l-1mk ik 1 ，和 lp l k ik i 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1+pi2 9 6 8 12 pi2+pi3 12 9 10 11 i 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1+pi2 9 6 8 12 pi2+pi3 12 9 10 11 当 l=1时，按（ Johnson）算法得到加工顺序（ 1， 2， 3， 4）； 当 l=2时，得到加工顺序（ 2， 3， 1， 4）。 对于（ 2， 3， 1， 4），相应的 Fmax=29。 所以，取顺序（

28、 1， 2， 3， 4）。 用 Palmer法、关键工件法和 CDS法求以下 4/4/P/Fmax问题的 最优解，并比较三种方法的结果。 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6 2 3 7 四、相同零件、不同移动方式下加工周 期的计算 排序问题针对的是不同零件，如果 n个零件相同， 则没有排序问题。但零件在加工过程中采取的移 动方式不同，会导致一批零件的加工周期不同。 三种典型的移动方式 顺序移动方式 (串行工程 ) 平行移动方式（平行工程） 平行顺序移动方式 （一）顺序移动方式 分钟52 t 分钟153 t 加工周期 时间 工序

29、 1 2 3 4 顺序移动方式 一批零件在上道工序全部加工完毕后才整 批地转移到下道工序继续加工。 分钟101 t 分钟104 t 设零件批量为 n（件），工序数目为 m，一批零件不 计算工序间运输时间，只考虑加工时间，设其加工的 周期为 T（分钟），零件在 i道工序的单件工时为 ti （分钟 /件）， i=1.2 n。 则该批零件的加工周期为： 12 1 . mi m i T nt nt nt n t 已知 n=4， t1=10分钟， t2=5分钟， t3=15分钟， t4=10分钟，则 T顺 =4 （ 10+5+15+10） =160分钟 （二）平行移动方式 分钟101 t 分钟52 t

30、分钟153 t 工序 1 2 3 4 时间 加工周期 每个零件在前道工序加工完毕后，立即转移到 后道工序去继续加工，形成前后工序交叉作业。 分钟104 t 零件平行移动的加工周期 为： T平 。为最长的单件工序时间式中， 平 L Li t t)1n(t T 已知 n=4， t1=10分钟， t2=5分钟， t3=15分钟， t4=10分钟， 则 T平 =（ 10+5+15+10） +（ 4-1） 15=85分钟 （三）平行顺序移动方式 既要求每道工序连续进行加工，又要求各道工序尽可能平 行地加工。 时间 工序 1 2 3 4 加工 周期 （ 1）当 titi+1时，零 件按平行移动方式转移；

31、（ 2）当 tit i+1时，以 i工序最后一个零件的 完工时间为基准，往前 推移（ n-1） ti+1作为 零件在（ i+1）工序的 开始时间。 分钟104 t 分钟101 t 分钟52 t 分钟153 t 具体做法 （ 1）当 titi+1时，零件按平行移动方式转移； （ 2）当 tit i+1时，以 i工序最后一个零件的完工 时间为基准，往前推移（ n-1） ti+1作为零件在 （ i+1）工序的开始时间。 平行顺序移动加工周期计算 已知 n=4， t1=10分钟， t2=5分钟， t3=15分钟， t4=10 分钟，则 T平顺 =4 （ 10+5+15+10） -（ 4-1） （ 5+

32、5+10） =100 分钟 )tt(m i n)1n(tn 1j 1m 1j j m 1i i ，平顺T 例 已知 n=4， t1=10分钟， t2=5分钟， t3=15分钟， t4=10分 钟。求三种移动方式下的加工周期。 解： T顺 =4 （ 10+5+15+10） =160分钟 T平 =（ 10+5+15+10） +（ 4-1） 15=85分钟 T平顺 =4 （ 10+5+15+10） -（ 4-1） （ 5+5+10） =100分钟 比较项目 平行移动 平行顺序移动 顺序移动 生产周期 短 中 长 运输次数 多 中 少 设备利用 差 好 好 组织管理 中 复杂 简单 零件三种移动方式的

33、比较 已知 m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分 别求在顺序移动、平行移动和平行顺序移 动方式下，这批零件的加工周期。 第三节 单件作业排序问题 11.3.1 指派问题 11.3.2 单件作业排序问题的描述 11.3.3 两种作业计划的构成 11.3.4 求解一般 n/m/G/Fmax问题的启发 式方法 1、指派问题的形式表述 给定了一系列所要完成的任务（ tasks）以 及一系列完成任务的被指派者 （ assignees），所需要解决的问题就是要 确定出哪一个人被指派进行哪一项任务 2、指派问题的假设 被指派者的数量和任务的数量是 相同的 每一个被指派者只

34、完成 一项任务 每一项任务只能由 一 个被指派者 来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小 11.3.1 指派问题 设 n 个人被分配去做 n 件工作 ， 每人只能完成一项任 务 ， 每项任务只能由一人完成 。 已知第 i 个人去做第 j 件工 作的的效率为 Cij(i=1.2 n;j=1.2 n)并假设 Cij 0。 问应 如何分配才能使总效率 （ 时间或费用 ） 最高 ？ ).2.1,1(0 ).2.1( 1 ).2.1( 1 m i n 1 1 1 1 njix njx nix xcZ ij n i ij n j ij n i n j

35、 ijij 或 3、指派问题模型 （ The Model for Assignment Problem） 项任务个人取完成第不分配第 项任务个人取完成第分配第 ji0 ji1 ijx 典型问题 例 1：有一份说明书，要分别译成英、日、 德、俄四种文字，交与甲、乙、丙、丁四个 人去完成，因各人专长不同，他们完成翻译 不同文字所需要的时间（小时）如表所示。 规定每项工作只能交与其中的一个人完成， 每个人只能完成其中的一项工作。 问：如何分配，能使所需的总时间最少？ 甲 乙 丙 丁 工作 人 译英文 译日文 译德文 译俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13

36、 9 建立模 型 设 xij= 1 0 若第 i项工作交与第 j个人完成 若第 i项工作不交与第 j个人完成 4 1 4 1 m i n i j ijij xcf 译英文： x11+ x12 + x13 + x14 =1 译日文： x21+ x22 + x23 + x24 =1 译德文： x31+ x32 + x33 + x34 =1 译俄文： x41+ x42 + x43 + x44 =1 甲： x11+ x21 + x31 + x41 =1 乙： x12+ x22 + x32 + x42 =1 丙： x13+ x23 + x33 + x43 =1 丁： x14+ x24 + x34 + x

37、44 =1 xij =0或 1 (i=1,2,3,4; j=1,2,3,4) 甲 乙 丙 丁 工作 人 译英文 译日文 译德文 译俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 4、指派问题的匈牙利解法 91187 1316149 1514410 413152 2410 4750 111006 2111302 4 9 7 第 1步：变换指派问题的系数矩阵（ cij），使各行 各列中都出现 0元素 (1) 从（ cij）的每行元素都减去该行的最小元素； (2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。 4 2 0010 2350 9606 071

38、30 在变化后的效率矩阵中找尽可能多的独立 0元素，若 能找出 n个独立 0元素，就以这 n个独立 0元素对应解 矩阵 (xij)中的元素为 1，其余为 0，这就得到最优解。 第 2步：进行试指派，即确定独立零元素 （ 1）从有唯一的零元素的行或 列开始确定独立零元素，并用 表示，并划掉其所在行或列的 其他零。直到尽可能多的零元 素都被圈出和划掉为止。 0 （ 2）若 独立零元素 的数目 m等 于矩阵的阶数 n，那么这指派 问题的最优解已得到。若 m n, 则转入下一步。 0100 0001 0010 1000 ij x 91187 1316149 1514410 413152 0010 23

39、50 9606 07130 例 2 有 甲、乙、丙、丁 四个工人，要分别派他们 完成四项不同的任务，分别记作 A、 B、 C、 D。他们完成各 项任务所需时间如下表所示，问如何分派任务，可使总时 间最少？ 任务 人员 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 第 1步 ， 变换系数矩阵： 2 1 4 2 2895 41013 8954 21176 )( ij c 0673 3902 4510 0954 0173 3402 4010 0454 -5 第 2步，确定独立零元素 找到 3 个独立零元素， 但 m = 3 n = 4 求解过程如

40、下 第 3步，作最少的直线覆盖所有零元素： (5)对没有打 号的行画横线，有打 号的列画纵线，这就 得到覆盖所有零元素的最少直线数 (1)对没有独立零元素的行打 号； (2)对已打 号的行中所有含划掉零元素的列打 号； (3)再对打有 号的列中含独立零元素的行打 号； (4)重复 (2)， (3)直到得不出新的打 号的行、列为止； 第 4步：在没有被直线覆盖的所有元素中找出最小元素 ， 然后将所在行 （ 或列 ） 都减去这最小元素； 0173 3402 4010 0454 1062 3402 4010 1343 0062 4402 5010 0343 在出现负数的列 （或行） 都加上这最小元素

41、（以保证 系数矩阵中不出现负元素）。新系数矩阵的最优解和 原问题仍相同。转回第 2步。 2 1 4 2 2895 41013 8954 21176 )( ij c 0673 3902 4510 0954 0173 3402 4010 0454 -5 1062 3402 4010 1343 0062 4402 5010 0343 0100 0010 0001 1000 ij x 11.3.2 问题的描述 加工描述矩阵 D为 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 对于一般单件作业排序问题，每个工件都有其独特的 加工路线，工件没有一定的流向。 要描述一道工序，

42、需要用三个参数： 3个参数： i， j和 k。 i表示工件代号， j表示工序号， k表示完成工序 i的第 j道 工序的机器代号。 （ i， j， k）表示工件 i的第 j道工序在机器 k上进行。 11.3.3 两种作业计划的构成 各工序都按最早可能完工时间安排的作业计划称 为能动作业计划。 各工序都按最早可能开始时间安排的作业计划称 为无延迟作业计划。 无延迟作业计划是没有任何延迟出现的能动作业 计划。 符号说明 每安排一道工序称为一 “ 步 ” St:t步之前已排序工序构成的部分作业计 划； Ot:t步可排序工序的集合； Tk为 Ot中工序 Ok的最早可能开始时间； Tk为 Ot中工序 Ok

43、的最早可能完成时间。 （一）能动作业计划的构成步骤 （ 1）设 t=1,S1为空集， O1为各工件第一道工序的集合。 （ 2）求 T* = minTk,并求出 T*所出现的机器 M*。 如果 M*有 多台，则任选一台。 （ 3）从 Ot中选出满足以下两个条件的工序 Oj：需要 M*加 工，且 Tj T* 。 （ 4）将选定的工序 Oj放入 St,从 Ot中消去 Oj,并将 Oj的 紧后工序放入 Ot ，使 t=t+1. （ 5）若还有未安排的工序，转步骤（ 2）；否则，停止。 例 有一个 2/3/G/Fmax问题，其加工描述矩阵 D和加工时间 矩阵 T分别为： D= 1,1,1 1,2,3 1

44、,3,2 2,1,3 2,2,1 2,3,2 T= 2 4 1 3 4 5 试构成一个能动作业计划。 能动作业计划的构成 2,3,2 M2 13 13 8 2,3,2 6 1,3,2 M2 8 8 12 7 7 1,3,2 2,3,2 5 2,2,1 M1 7 8 7 7 3 1,3,2 2,2,1 4 1,2,3 M3 7 7 7 3 3 1,2,3 2,2,1 3 2,1,3 M3 3 6 3 2 0 1,2,3 2,1,3 2 1,1,1 M1 2 2 3 0 0 1,1,1 2,1,3 1 Oj M* T* Tk Tk Ot t 能动作业计划的甘特图 2,3,2 1,1,1 2,2,1

45、 1,3,2 2,1,3 1,2,3 3 7 7 8 13 2 3 7 0 时间 机 器 M1 M2 M3 （二）无延迟作业计划构成步骤 （ 1）设 t=1,S1为空集， O1为各工件第一道工序的集合。 （ 2）求 T* = minTk,并求出 T*所出现的机器 M*。 如果 M*有 多台，则任选一台。 （ 3）从 Ot中选出满足以下两个条件的工序 Oj：需要 M*加 工，且 Tj=T* 。 （ 4）将选定的工序 Oj放入 St,从 Ot中消去 Oj,并将 Oj的 紧后工序放入 Ot ，使 t=t+1。 （ 5）若还有未安排的工序，转步骤（ 2）；否则，停止。 无延迟作业计划的构成 1,3,2

46、 M2 12 13 12 1,3,2 6 2,3,2 M2 M2 7 7 8 12 7 7 1,3,2 2,3,2 5 2,2,1 M1 3 8 7 7 3 1,3,2 2,2,1 4 1,2,3 M3 M1 3 3 7 7 3 3 1,2,3 2,2,1 3 2,1,3 M3 0 6 3 2 0 1,2,3 2,1,3 2 1,1,1 M1 M3 0 0 2 3 0 0 1,1,1 2,1,3 1 Oj M* T* Tk Tk Ot t 无延迟作业计划的甘特图 2,3,2 1,1,1 2,2,1 2,1,3 1,2,3 3 7 7 12 13 2 3 7 0 时间 机 器 M1 M2 M3

47、1,3,2 能动作业计划和无延迟作业计划尽管不一定是最优作 业计划，但一般是较好的作业计划，特别是无延迟作 业计划能提供令人满意的解。 一般能动作业计划和无延迟作业计划都有多个。 一般来说，以构成无延迟作业计划的步骤为基础的启 发式算法比以构成能动作业计划的步骤为基础的启发 算法的效果要好。 练 习 1.南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车 交易所提供全部客户服务的合同。取得合同的主要要求 是快速交货。爱得说，如果南希厂可以在 24小时内将爱 得收到的 5辆车全部整修并且重新喷漆，合同就归该厂。 下面是这 5辆车在整修和喷漆车间各自需要的时间。假 定车子在重新喷漆前要经过重新整修的步

48、骤，南希厂可 以满足时间要求并且得到合同吗？ 汽车 整修时间（小时） 重新喷漆时间（小时） A 6 3 B 0 4 C 5 2 D 8 6 E 2 1 2.有一个 2/3/G/Fmax问题，其加工描述矩阵 D和加工时间 矩阵 T分别为： 试构成一个能动作业计划和无延迟作业计划。 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,2 2,3,1 T= 3 5 2 2 4 3 4， 1， 2 M2 0 6 0 4， 1， 2 0 4 0 3， 1， 1 11 8 2， 2， 1 12 5 1， 2， 2 3 0 6 0 4， 1， 2 0 4 0 3， 1， 1 11 8 2， 2，

49、1 1， 1， 1 M1 0 5 0 1， 1， 1 2 0 6 0 4， 1， 2 0 4 0 3， 1， 1 2， 1， 3 M3 0 8 0 2， 1， 3 0 5 0 1， 1， 1 1 Oj M* T* T k Tk Ot t 16 9 4， 3， 1 13 9 3， 2， 4 12 9 2， 2， 1 1， 2， 2 M2 6 13 6 1， 2， 2 6 4， 2， 4 M4 6 8 6 4， 2， 4 13 9 3， 2， 4 12 9 2， 2， 1 6 13 6 1， 2， 2 5 8 6 4， 2， 4 3， 1， 1 M1 5 9 5 3， 1， 1 11 8 2， 2

50、， 1 13 6 1， 2， 2 4 Oj M* T* T k Tk Ot t 4， 3， 1 M1 12 19 12 4， 3， 1 18 13 3， 3， 3 17 13 2， 3， 4 19 13 1， 3， 3 9 19 12 4， 3， 1 3， 2， 4 M4 9 13 9 3， 2， 4 16 12 2， 3， 4 19 13 1， 3， 3 8 9 16 9 4， 3， 1 9 13 9 3， 2， 4 2， 2， 1 M1 9 12 9 2， 2， 1 19 13 1， 3， 3 7 Oj M* T* T k Tk Ot t 22 19 4， 4， 3 18 19 18 3，

51、 4， 2 18 27 18 2， 4， 3 1， 3， 3 M3 18 24 18 1， 3， 3 12 22 19 4， 4， 3 3， 3， 3 M3 13 18 13 3， 3， 3 26 17 2， 4， 3 13 19 13 1， 3， 3 11 22 19 4， 4， 3 13 18 13 3， 3， 3 2， 3， 4 M4 13 17 13 2， 3， 4 13 19 13 1， 3， 3 10 Oj M* T* T k Tk Ot t 2， 4， 3 M3 27 36 27 2， 4， 3 4， 4， 3 M3 24 27 24 4， 4， 3 24 33 24 2， 4，

52、 3 24 27 24 4， 4， 3 24 33 24 2， 4， 3 1， 4， 4 M4 24 26 24 1， 4， 4 14 27 24 4， 4， 3 3， 4， 2 M2 18 19 18 3， 4， 2 33 24 2， 4， 3 26 24 1， 4， 4 13 Oj M* T* T k Tk Ot t 15 16 11.3.3 求解一般 n/m/G/Fmax问题的启发式方法 三类启发式算法： 优先调度法则 随机抽样法 概率调度法 1.优先调度法则 SPT（ Shortest processing time）法则 优先选择加工时间最短的工序 可使工件的平均流程时间最短，从而减

53、少在制品量 FCFS（ First come first served）法则 优先选择最早进入可排工序集合的工件 来自排队论，对工件较公平 EDD（ Earliest due date）法则 优先选择完工期限紧的工件 可使工件最大延误时间最小 MWKR（ Most work remaining）法则 优先选择余下加工时间最长的工件 不同工作量的工件的完工时间尽量接近 1.优先调度法则（续） LWKR（ Least work remaining）法则 优先选择余下加工时间最短的工件 使工作量小的工件尽快完成 MOPNR（ Most operations remaining）法则 优先选择余下工序

54、数最多的工件 与 MWKR法则类似，只不过考虑工件在不同机器上的 转运排队时间是主要的 SCR（ Smallest critical ratio）法则 优先选择临界比最小的工件（临界比：工件允许停留 时间与工件余下加工时间之比） 保证工件延误最少 RANDOM法则 随机地挑一个工件 2.随机抽样法 随机抽样法 实际上是对同一个问题多次运用 RANDOM法则 来决定要挑选的工序，从而得到多个作业计划 这种方法不一定能得到最优作业计划，但可以 得到较满意的作业计划 效果与样本大小有关。样本越大，获取较好解 的可能性越大 从无延迟作业计划母体中抽样所得到的结果比 从能动作业计划母体中抽样所得到的结果

55、要好 3. 概率调度法 给不同的工序按某一优先调度法则分配不同的挑 选概率，可以得到多个作业计划供比较。 例如，在构成无延迟作业计划的第（ 3）步 有 3道工序， A、 B和 C可挑选 3道工序所需的时间分别为 3， 4和 7 将这 3道工序按加工时间从小到大排列，然后给每道工序 从大到小分配一个被挑选的概率 比如 A、 B和 C的挑选概率分别为 6/14、 5/14和 3/14 既保证了 SPT法则起作用，又可产生多个作业计划供挑 选 生产作业控制是指在生产过程中，按既定 的政策、目标、计划和标准，通过监督和检 查生产活动的进展情况、实际成效，及时发 现偏差，找出原因，采取措施，以保证目标、

56、 计划的实现。 生产运作控制的受控客体是生产运作过程， 其预定目标是主生产计划与生产作业计划的 目标值。 11.4 生产作业控制 一 、 生产活动与作业计划产生偏差的原因 （ 1）加工时间估计不准确 （ 2）随机因素的影响 （ 3）加工路线的多样性 （ 4）企业环境的动态性 11.4 生产作业控制 二 、 生产作业控制的程序 制定生产作业监控体系 监控实际生产过程 评估偏差情况 采取纠偏措施 11.4 生产作业控制 三、生产作业控制的主要工具 实际生产中，有不少工具可以用来进行生产作业 控制，这些工具容易通过运用适当的软件来生成， 主要包括： 调度单 日报、月报 例外报告、异常报告 输入 /输

57、出 （ I/O） 报告 日常调度单 它告诉主管哪些工件要被加工，这些工件的优先 级以及加工时间。 开始日期 工件号 描述 运行时间 201 203 205 205 207 208 15131 15143 15145 15712 15340 15312 轴 铆钉 锭子 锭子 测量杆 轴 11.4 20.6 4.3 8.6 6.5 4.6 各种状态和异常报告 1、预计延期报告 2、废品报告 3、返工报告 4、作业总结报告 部件号 计划日期 新日期 延期原因 措施 17125 13044 17653 4/10 4/11 4/11 4/15 5/1 5/14 夹具损坏 送去镀金，镀金工 罢工 新孔未成

58、直线 工具室返还 4/15 新批量开始生产 工程部重新安装 钻模 漏斗模型 德国汉诺威大学的 Bechte和 Wiendall等 人于 20世纪 80年代 初在实施输入 /输出 控制时提出了漏斗模 型（ Funnel Model）。 漏斗模型 漏斗模型的基本原则：工作中心的输入永 远不能超过工作中心的输出。当工作中心 的输入超过输出，就会拖欠订单，结果将 会出现作业推迟、客户不满、下游作业或 相关作业的延期。 注：曲线图的垂直段表示到达或完成的工作量；水 平段表示相邻到达或完成的任务之间的时间间隔。 控制规则 在一段较长的时间内 (如数周 )内，若工况稳定， 输入输出两条曲线可以近似地用两条直线来表 示，其斜率 (平均生产率 )等于平均在制品库存 / 平均通过时间。 实际实践中，可以采用四个规则来调整输入、 输出、在制品库存和通过时间： 若希望保持在制品库存量稳定，就要使单位时间内 的平均输入等于平均输出。 若希望改变在制品库存量，可暂时增加或减少输入。 若希望平均通过时间在所控制的范围内，则适当调 整平均在制品库存与生产率的比例。 要使各个工件的平均通过时间稳定，可以采用 FIFO 规则来安排各工件的加工顺序。