制造业作业生产计划课件.ppt

第十一章第十一章 制造业作业计划与控制制造业作业计划与控制§11.1  排序问题的基本概念排序问题的基本概念 §11.2  流水作业排序问题流水作业排序问题§11.3 单件作业排序问题单件作业排序问题§11.4  生产作业控制生产作业控制第一节第一节 排序的基本概念排序的基本概念一、相关名词术语一、相关名词术语u排序：排序：确定工件在机器上的加工顺序确定工件在机器上的加工顺序u编制作业计划：编制作业计划：不仅包括确定工件的加工顺序不仅包括确定工件的加工顺序，还，还包括包括确定机器加工每个工件的开始时间和完成时间我们习惯上确定机器加工每个工件的开始时间和完成时间我们习惯上不加区别地使用作业排序与作业计划不加区别地使用作业排序与作业计划  u派工：派工：按照作业计划的要求，将具体的生产任务安排到具按照作业计划的要求，将具体的生产任务安排到具体的机床上加工体的机床上加工u赶工：赶工：当实际进度落后于计划进度时采取的行动当实际进度落后于计划进度时采取的行动u加工线路：加工线路：工件按照工艺过程进行加工的过程，一般用工件按照工艺过程进行加工的过程，一般用M M1 1,M,M2 2,M,M3 3,M,M4 4来表示。

来表示u加工顺序：加工顺序：表示每台机器加工表示每台机器加工n n个工件的先后顺序，是排个工件的先后顺序，是排序要解决的问题序要解决的问题二、排序问题的分类二、排序问题的分类n 按机器的种类和数量不同，可以分为单台机器按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题的排序问题和多台机器的排序问题; ; n 按加工路线的特征，可分为按加工路线的特征，可分为单件作业排序问题单件作业排序问题和流水作业排序问题和流水作业排序问题; ; n 按工件到达工作中心（或车间）的情况不同可按工件到达工作中心（或车间）的情况不同可分为分为静态的排序问题静态的排序问题（当进行排序时，所有工件都已到（当进行排序时，所有工件都已到达，或准备就绪）达，或准备就绪）和和动态的排序问题动态的排序问题（工件的到达是陆（工件的到达是陆续的，要随时安排它们的加工顺序）续的，要随时安排它们的加工顺序）; ; 第一节第一节 排序的基本概念排序的基本概念二、排序问题的分类二、排序问题的分类n 按目标函数不同，可分为流程最短问题与误工按目标函数不同，可分为流程最短问题与误工最少问题等；最少问题等；n 按目标函数的性质不同分为单目标排序问题与按目标函数的性质不同分为单目标排序问题与多目标排序问题多目标排序问题; ; n 按参数的性质，可以划分为确定型排序问题与按参数的性质，可以划分为确定型排序问题与随机型排序问题。

随机型排序问题 第一节第一节 排序的基本概念排序的基本概念第一节第一节 排序的基本概念排序的基本概念三、假设条件与符号说明三、假设条件与符号说明（一）排序问题的假设条件（一）排序问题的假设条件1.1.一个工件不能同时在几台不同的机器上加工；一个工件不能同时在几台不同的机器上加工；2.2.工件在加工过程中采取工件在加工过程中采取平行平行移动方式；移动方式；3.3.不允许中断；不允许中断；4.4.每道工序只在一台机器上完成；每道工序只在一台机器上完成；5.5.工件数、机器数和加工时间已知，加工时间与加工件数、机器数和加工时间已知，加工时间与加工顺序无关；工顺序无关；6.6.每台机器同时只能加工一个工件每台机器同时只能加工一个工件第一节第一节 排序的基本概念排序的基本概念三、假设条件与符号说明三、假设条件与符号说明（二）有关符号说明（二）有关符号说明四、排序问题的一般表示方法四、排序问题的一般表示方法 4 4参数法：参数法：n/m/A/Bn/m/A/B 其中：其中：n ——工件数；工件数； m——机器数；机器数； A——工作车间类型；工作车间类型； B——目标函数，通常是使其最小目标函数，通常是使其最小 u 若若A A处为处为F F代替，则表示流水作业排序问题；代替，则表示流水作业排序问题；u 若若A A处为处为P P代替，则表示流水作业代替，则表示流水作业排列排序排列排序问题，即每问题，即每个工件在各台机器上的加工顺序都相同；个工件在各台机器上的加工顺序都相同；u 若若m m为为1 1时，时，A A为空白，即单台机器的排序，对于单台机为空白，即单台机器的排序，对于单台机器排序问题，无所谓加工路线问题。

器排序问题，无所谓加工路线问题第一节第一节 排序的基本概念排序的基本概念第二节第二节 流水作业排序问题流水作业排序问题n n流水作业排序问题的基本特征是流水作业排序问题的基本特征是每个工件每个工件的加工线路都一致的加工线路都一致n n加工线路一致，是指工件的加工线路一致，是指工件的流向一致流向一致，并，并不是指每个工件必须经过加工线路上的每不是指每个工件必须经过加工线路上的每台机器加工台机器加工n n本节要讨论的是所有工件在各台机器上的本节要讨论的是所有工件在各台机器上的加工顺序相同的情况，就是加工顺序相同的情况，就是排列排序排列排序问题问题n/m/P/B第二节第二节 流水作业排序问题流水作业排序问题一、最长流程时间Fmax的计算uP263[例例11.1] 有一个有一个6/4/P/Fmax问题，其加工时间如表，问题，其加工时间如表，当按顺序当按顺序 S=(6，，1，，5，，2，，4，，3)加工时，求加工时，求 Fmax表表11-1 11-1 加工时间矩阵加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331表表11-2 11-2 顺序下的加工时间矩阵顺序下的加工时间矩阵uP263[P263[例例11.1] 11.1] 有一个有一个6/4/P/Fmax6/4/P/Fmax问题，其加工时间如表，问题，其加工时间如表，当按顺序当按顺序 S=(6S=(6，，1 1，，5 5，，2 2，，4 4，，3)3)加工时，求加工时，求 F Fmaxmax。

表表11-1 11-1 加工时间矩阵加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446u 对于对于第第1 1行第行第1 1列列，只需把加工时间的数值作为完，只需把加工时间的数值作为完工时间标在加工时间的右上角工时间标在加工时间的右上角; ;对于第对于第1 1行的其它元素，行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角工时间，将结果填在计算列加工时间的右上角u 对于从第对于从第2 2行到第行到第m m行，只要把行，只要把上一行右上角上一行右上角的数的数字和本行的加工时间相加，将结果填在加工时间的右字和本行的加工时间相加，将结果填在加工时间的右上角；上角；u 从第从第2 2列到第列到第n n列，则要从本行前一列右上角和本列，则要从本行前一列右上角和本列上一行的右上角数字中列上一行的右上角数字中取较大者取较大者，再和本列加工时，再和本列加工时间相加，将结果填在本列加工时间的右上角。

这样计间相加，将结果填在本列加工时间的右上角这样计算下去，最后一行的最后一列右上角数字，即为算下去，最后一行的最后一列右上角数字，即为F Fmaxmax Fmax的标注完工时间的规则 第二节第二节 流水作业排序问题流水作业排序问题二、n / 2 / F / Fmax 问题的最优算法 对于对于n n个工件个工件1 1台机器的排序问题，既适用于流程台机器的排序问题，既适用于流程作业作业, ,也适用于单件作业，在第三节单件作业排序也适用于单件作业，在第三节单件作业排序讨论 对于对于n / 2 / F / Fmax 问题，问题，S.M.Johson于于1954年年给出了有效的算法，即著名的给出了有效的算法，即著名的Johson算法其目标算法其目标是使从第一个工件开始到最后一个工件结束的是使从第一个工件开始到最后一个工件结束的总流总流程时间最短程时间最短 Johnson算法的步骤：算法的步骤：①① 列出所有工件在两台机器上的加工时间矩阵；列出所有工件在两台机器上的加工时间矩阵；②② 从加工时间矩阵中找出从加工时间矩阵中找出最短最短的加工时间；的加工时间；③③ 若最短的加工时间出现在若最短的加工时间出现在M M1 1上，则对应的工件上，则对应的工件往前排往前排；如果最短的加工时间出现在；如果最短的加工时间出现在M M2 2上，则对上，则对应的工件应的工件往后排往后排；然后，；然后，划去已经排序的工件划去已经排序的工件。

若最短的加工时间有多个，则任选一个；若最短的加工时间有多个，则任选一个；④④ 当所有的工件都已排序，停止计算，转步骤当所有的工件都已排序，停止计算，转步骤①二、n / 2 / F / Fmax 问题的最优算法 P264[例例11.2] u按按Johnson法求下表所示的法求下表所示的6/2/F/Fmax问题的最优解问题的最优解i123456ai518534bi722474表表11-3 11-3 加工时间矩阵加工时间矩阵最优加工顺序为最优加工顺序为S=S=（（2 2，，5 5，，6 6，，1 1，，4 4，，3 3））最优顺序下的最优顺序下的F Fmaxmax=28=28Johnson算法的变形算法的变形n n步骤：步骤：①①将所有将所有ai≤bi的工件按照的工件按照ai值值不减不减（递升）（递升）的的顺序排列成一个序列顺序排列成一个序列A；；②②将所有将所有ai＞＞bi的工件按的工件按bi值值不增（递减）不增（递减）的的顺序排列成一个序列顺序排列成一个序列B；；③③将将A放到放到B之前，就构成了最优加工顺序之前，就构成了最优加工顺序 P264[例例11.2] ——Johnson算法的变形算法的变形u求下表所示的求下表所示的6/2/F/Fmax问题的最优解。

问题的最优解i123456ai518534bi722474表表11-3 11-3 加工时间矩阵加工时间矩阵序列序列A为（为（2,5,6,1），序列），序列B为（为（4,3），），则最优序列为则最优序列为S=（（2,5,6,1,4,3），），与与Johnson算法的结果一致算法的结果一致n / m / P / Fmax问题的启发式算法问题的启发式算法n n启发式算法（试探法）是一种能在可接受的费用启发式算法（试探法）是一种能在可接受的费用启发式算法（试探法）是一种能在可接受的费用启发式算法（试探法）是一种能在可接受的费用内寻找最好的解的技术，但不一定能保证所得解内寻找最好的解的技术，但不一定能保证所得解内寻找最好的解的技术，但不一定能保证所得解内寻找最好的解的技术，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐的可行性和最优性，甚至在多数情况下，无法阐的可行性和最优性，甚至在多数情况下，无法阐的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度述所得解同最优解的近似程度述所得解同最优解的近似程度述所得解同最优解的近似程度   n n启发式算法是解决启发式算法是解决启发式算法是解决启发式算法是解决NPNP问题（不确定性问题）的重问题（不确定性问题）的重问题（不确定性问题）的重问题（不确定性问题）的重要方法，由于其计算量都比较大，所以随着计算要方法，由于其计算量都比较大，所以随着计算要方法，由于其计算量都比较大，所以随着计算要方法，由于其计算量都比较大，所以随着计算机技术的发展，启发式算法取得了巨大的成就。

机技术的发展，启发式算法取得了巨大的成就机技术的发展，启发式算法取得了巨大的成就机技术的发展，启发式算法取得了巨大的成就n n常见的启发式算法有贪婪法、局部搜索法、退火常见的启发式算法有贪婪法、局部搜索法、退火常见的启发式算法有贪婪法、局部搜索法、退火常见的启发式算法有贪婪法、局部搜索法、退火算法、蚁群算法等算法、蚁群算法等算法、蚁群算法等算法、蚁群算法等 经典算法与启发式算法经典算法与启发式算法n n驾驶汽车到达某人的家，写成算法是这样的：沿驾驶汽车到达某人的家，写成算法是这样的：沿驾驶汽车到达某人的家，写成算法是这样的：沿驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后长张高速公路北行至太子庙；从西北出口出来后长张高速公路北行至太子庙；从西北出口出来后长张高速公路北行至太子庙；从西北出口出来后往山上开往山上开往山上开往山上开4.54.5公里；在一个杂货店旁边的红绿灯路公里；在一个杂货店旁边的红绿灯路公里；在一个杂货店旁边的红绿灯路公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大口右转，接着在第一个路口左转；从左边褐色大口右转，接着在第一个路口左转；从左边褐色大口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路房子的车道进去，就是桃源路房子的车道进去，就是桃源路房子的车道进去，就是桃源路714 714 号。

号n n用启发式方法来描述则可能是这样：找出上一次用启发式方法来描述则可能是这样：找出上一次用启发式方法来描述则可能是这样：找出上一次用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到我们寄给你的信，照着信上面的寄出地址开车到我们寄给你的信，照着信上面的寄出地址开车到我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里这个镇；到了之后你问一下我们的房子在哪里这个镇；到了之后你问一下我们的房子在哪里这个镇；到了之后你问一下我们的房子在哪里这里每个人都认识我们这里每个人都认识我们这里每个人都认识我们这里每个人都认识我们————肯定有人会很愿意帮肯定有人会很愿意帮肯定有人会很愿意帮肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共亭助你的；如果你找不到人，那就找个公共亭助你的；如果你找不到人，那就找个公共亭助你的；如果你找不到人，那就找个公共亭给我们打，我们会出来接你给我们打，我们会出来接你给我们打，我们会出来接你给我们打，我们会出来接你 1965年，年，D·S·Palmer提出按提出按斜度指标斜度指标排列工件的启发排列工件的启发式算法，这种算法称之为式算法，这种算法称之为PalmerPalmer算法。

算法其中其中工件斜度指标工件斜度指标可按下式计算：可按下式计算： 算出算出λi后，按后，按λi不增（递减）不增（递减）的顺序排列工件，可得出较的顺序排列工件，可得出较满意的加工顺序满意的加工顺序三、一般n / m / P / Fmax问题的启发式算法（一）Palmer（帕默） 算法（一）Palmer 算法P266[例例11.3] 有一个有一个4/3/F/Fmax问题，用问题，用Palmer算法求解算法求解最优加工顺序加工时间矩阵为：最优加工顺序加工时间矩阵为：三、一般n / m / P / Fmax问题的启发式算法i1234Pi11263Pi18429Pi14582i1234Pi11263Pi18429Pi14582解：解：按照按照 不增的顺序，不增的顺序，得到最优加工顺序得到最优加工顺序(1,2,3,4)和和(2,1,3,4)（二）关键工件法u步骤如下：步骤如下： 1. 计算每个工件的总加工时间计算每个工件的总加工时间Pi=∑pij，找出加工时间最，找出加工时间最长的工件长的工件C（（j=m），将其作为），将其作为关键工件关键工件 2. 对于余下的工件，若对于余下的工件，若Pi1≤Pim，则按，则按Pi1不减不减的顺序排列的顺序排列一个序列一个序列Sa；若；若Pi1>Pim，则按，则按Pim不增的顺序排成一个序列不增的顺序排成一个序列Sb。

3. 加工顺序（加工顺序（Sa，，C，，Sb）即为所求近优解即为所求近优解例例11.3i1234Pi11263Pi18429Pi14582三、一般n / m / P / Fmax问题的启发式算法 （三）CDS算法u Campbell，Dudek，Smith三人提出了一个启发式算法，简称CDS算法他们把Johnson 算法用于一般 n / m / P /Fmax问题，得到（m-1）个加工顺序，取其中优者对加工时间，按下列公式求和，即： 当当l=1时时,有两种排序方式有两种排序方式,用用Johnson 方法排序得到一个最优方法排序得到一个最优排序；当排序；当l=2时，又有两种排序方法，用时，又有两种排序方法，用Johnson方法排序，得方法排序，得到又一个最优排序；当到又一个最优排序；当l=3,…，，(m-1)，又可求出对应的每一种，又可求出对应的每一种排序方法最后比较取得最优解排序方法最后比较取得最优解本次课小结本次课小结 n n相关名次术语相关名次术语（排序、编制作业计划、（排序、编制作业计划、（排序、编制作业计划、（排序、编制作业计划、   派工、派工、派工、派工、赶工、加工线路、加工顺序）赶工、加工线路、加工顺序）赶工、加工线路、加工顺序）赶工、加工线路、加工顺序）uu最长流程时间的计算最长流程时间的计算uun/2/F/Fmax问题的最优算法问题的最优算法（（（（   JohsonJohson算法）算法）算法）算法）§11.3 单件作业排序问题单件作业排序问题一、问题的描述一、问题的描述u 特点：每个工件都有其独特的加工路线，工特点：每个工件都有其独特的加工路线，工件件没有固定没有固定的流向的流向u 问题的描述：描述一道工序，要用问题的描述：描述一道工序，要用3个参数个参数(i,j,k)，表示工件，表示工件 i 的第的第 j 道工序在机器道工序在机器 k 上进行。

上进行u 可以用可以用加工描述矩阵加工描述矩阵来描述所有工件的加工来描述所有工件的加工§11.3 单件作业排序问题单件作业排序问题一、问题的描述一、问题的描述u 可以用可以用加工描述矩阵加工描述矩阵来描述所有工件的加工来描述所有工件的加工 例如，一个例如，一个2/3/G/Fmax问题：问题：工序工序1工序工序2工序工序3工件工件1工件工件2二、三种作业计划二、三种作业计划1.半能动作业计划（半能动作业计划（半能动作业计划（半能动作业计划（Semi-active scheduleSemi-active schedule））））• •各工序都按最早可能开（完）工时间安排的作业计划各工序都按最早可能开（完）工时间安排的作业计划各工序都按最早可能开（完）工时间安排的作业计划各工序都按最早可能开（完）工时间安排的作业计划2.能动作业计划（能动作业计划（能动作业计划（能动作业计划（Active scheduleActive schedule））））• •任何一台机器的每段空闲时间都不足以加工一道可加任何一台机器的每段空闲时间都不足以加工一道可加任何一台机器的每段空闲时间都不足以加工一道可加任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划工工序的半能动作业计划工工序的半能动作业计划工工序的半能动作业计划3.无延迟作业计划（无延迟作业计划（无延迟作业计划（无延迟作业计划（Non-delay schedu1eNon-delay schedu1e））））• •没有任何延迟出现的能动作业计划没有任何延迟出现的能动作业计划没有任何延迟出现的能动作业计划没有任何延迟出现的能动作业计划• •“ “延迟延迟延迟延迟” ”：有工件等待加工时，机器出现空闲，即使：有工件等待加工时，机器出现空闲，即使：有工件等待加工时，机器出现空闲，即使：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序这段空闲时间不足以完成一道工序这段空闲时间不足以完成一道工序这段空闲时间不足以完成一道工序能动作业计划与无延迟作业计划的生成能动作业计划与无延迟作业计划的生成符号说明符号说明将每安排一道工序称作一将每安排一道工序称作一将每安排一道工序称作一将每安排一道工序称作一“ “步步步步” ”，设：，设：，设：，设：uu｛｛｛｛S St t｝｝｝｝——第第第第t t 步之前已排序工序构成的部分作业计划步之前已排序工序构成的部分作业计划步之前已排序工序构成的部分作业计划步之前已排序工序构成的部分作业计划uu｛｛｛｛O Ot t｝｝｝｝——第第第第t t 步可以排序的工序的集合步可以排序的工序的集合步可以排序的工序的集合步可以排序的工序的集合uu T Tk k——｛｛｛｛O Ot t｝中｝中｝中｝中O Ok k的最早可能的最早可能的最早可能的最早可能开工开工开工开工时间时间时间时间uu T’T’k k——｛｛｛｛O Ot t｝中｝中｝中｝中O Ok k的最早可能的最早可能的最早可能的最早可能完工完工完工完工时间时间时间时间P269 例例11.4 有一个有一个2/3/G/Fmax问题，其加工描述问题，其加工描述矩阵矩阵D和加工时间矩阵和加工时间矩阵T已知，求一个能已知，求一个能动作业计划。

动作业计划三、三类启发式算法三、三类启发式算法1.优先调度法则优先调度法则2.随机抽样法随机抽样法3.概率调度法概率调度法1.优先调度法则优先调度法则n nSPTSPT（（（（Shortest processing timeShortest processing time）法则）法则）法则）法则• •优先选择加工时间最短的工序优先选择加工时间最短的工序优先选择加工时间最短的工序优先选择加工时间最短的工序• •可使工件的平均流程时间最短，从而减少在制品量可使工件的平均流程时间最短，从而减少在制品量可使工件的平均流程时间最短，从而减少在制品量可使工件的平均流程时间最短，从而减少在制品量n nFCFSFCFS（（（（First come first servedFirst come first served）法则）法则）法则）法则• •优先选择最早进入可排工序集合的工件优先选择最早进入可排工序集合的工件优先选择最早进入可排工序集合的工件优先选择最早进入可排工序集合的工件• •来自排队论，对工件较公平来自排队论，对工件较公平来自排队论，对工件较公平来自排队论，对工件较公平n nEDDEDD（（（（Earliest due dateEarliest due date）法则）法则）法则）法则• •优先选择完工期限紧的工件优先选择完工期限紧的工件优先选择完工期限紧的工件优先选择完工期限紧的工件• •可使工件最大延误时间最小可使工件最大延误时间最小可使工件最大延误时间最小可使工件最大延误时间最小n nMWKRMWKR（（（（Most work remainingMost work remaining）法则）法则）法则）法则• •优先选择余下加工时间最长的工件优先选择余下加工时间最长的工件优先选择余下加工时间最长的工件优先选择余下加工时间最长的工件• •不同工作量的工件的完工时间尽量接近不同工作量的工件的完工时间尽量接近不同工作量的工件的完工时间尽量接近不同工作量的工件的完工时间尽量接近1.优先调度法则（续）优先调度法则（续）n nLWKRLWKR（（（（Least work remainingLeast work remaining）法则）法则）法则）法则• •优先选择余下加工时间最短的工件优先选择余下加工时间最短的工件优先选择余下加工时间最短的工件优先选择余下加工时间最短的工件• •使工作量小的工件尽快完成使工作量小的工件尽快完成使工作量小的工件尽快完成使工作量小的工件尽快完成n nMOPNRMOPNR（（（（Most operations remainingMost operations remaining）法则）法则）法则）法则• •优先选择余下工序数最多的工件优先选择余下工序数最多的工件优先选择余下工序数最多的工件优先选择余下工序数最多的工件• •与与与与MWKRMWKR法则类似，只不过考虑工件在不同机器上的法则类似，只不过考虑工件在不同机器上的法则类似，只不过考虑工件在不同机器上的法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的转运排队时间是主要的转运排队时间是主要的转运排队时间是主要的n nSCRSCR（（（（Smallest critical ratioSmallest critical ratio）法则）法则）法则）法则• •优先选择临界比最小的工件（临界比：工件允许停留优先选择临界比最小的工件（临界比：工件允许停留优先选择临界比最小的工件（临界比：工件允许停留优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）时间与工件余下加工时间之比）时间与工件余下加工时间之比）时间与工件余下加工时间之比）• •保证工件延误最少保证工件延误最少保证工件延误最少保证工件延误最少n nRANDOMRANDOM法则法则法则法则• •随机地挑一个工件随机地挑一个工件随机地挑一个工件随机地挑一个工件2.随机抽样法随机抽样法n n随机抽样法随机抽样法• •实际上是对同一个问题多次运用实际上是对同一个问题多次运用实际上是对同一个问题多次运用实际上是对同一个问题多次运用RANDOMRANDOM法则法则法则法则来决定要挑选的工序，从而得到多个作业计划来决定要挑选的工序，从而得到多个作业计划来决定要挑选的工序，从而得到多个作业计划来决定要挑选的工序，从而得到多个作业计划• •这种方法不一定能得到最优作业计划，但可以这种方法不一定能得到最优作业计划，但可以这种方法不一定能得到最优作业计划，但可以这种方法不一定能得到最优作业计划，但可以得到较满意的作业计划得到较满意的作业计划得到较满意的作业计划得到较满意的作业计划n n效果与样本大小有关。

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

计划的实现uu 生产运作控制的受控客体是生产运作过程，生产运作控制的受控客体是生产运作过程，其预定目标是主生产计划与生产作业计划的其预定目标是主生产计划与生产作业计划的目标值§11.4 生产作业控制生产作业控制一、生产活动与作业计划产生偏差的原因一、生产活动与作业计划产生偏差的原因（（1 1）加工时间估计不准确）加工时间估计不准确（（2 2）随机因素的影响）随机因素的影响（（3 3）加工路线的多样性）加工路线的多样性（（4 4）企业环境的动态性）企业环境的动态性§11.4 生产作业控制生产作业控制二、生产作业控制的程序二、生产作业控制的程序üü 制定生产作业监控体系制定生产作业监控体系üü 监控实际生产过程监控实际生产过程üü 评估偏差情况评估偏差情况üü 采取纠偏措施采取纠偏措施§11.4 生产作业控制生产作业控制三、生产作业控制的主要工具三、生产作业控制的主要工具n n   实际生产中，有不少工具可以用来进行生产作业实际生产中，有不少工具可以用来进行生产作业实际生产中，有不少工具可以用来进行生产作业实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，控制，这些工具容易通过运用适当的软件来生成，控制，这些工具容易通过运用适当的软件来生成，控制，这些工具容易通过运用适当的软件来生成，主要包括：主要包括：主要包括：主要包括：üü   调度单调度单调度单调度单üü   日报、月报日报、月报日报、月报日报、月报üü   例外报告、异常报告例外报告、异常报告例外报告、异常报告例外报告、异常报告üü   输入输入输入输入/ /输出输出输出输出（（（（I/OI/O））））报告报告报告报告漏斗模型漏斗模型n n德国汉诺威大学的德国汉诺威大学的Bechte和和Wiendall等人于等人于20世纪世纪80年年代初在实施输入代初在实施输入/输输出控制时提出了漏斗出控制时提出了漏斗模型（模型（Funnel Model）。

漏斗模型漏斗模型n n 漏斗模型的基本原则：工作中心的输入永漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出当工作中心远不能超过工作中心的输出当工作中心的输入超过输出，就会拖欠订单，结果将的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或会出现作业推迟、客户不满、下游作业或相关作业的延期相关作业的延期    注：曲线图的垂直段表示到达或完成的工作量；水注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔平段表示相邻到达或完成的任务之间的时间间隔控制规则控制规则n n在一段较长的时间内在一段较长的时间内在一段较长的时间内在一段较长的时间内( (如数周如数周如数周如数周) )内，若工况稳定，内，若工况稳定，内，若工况稳定，内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表输入输出两条曲线可以近似地用两条直线来表输入输出两条曲线可以近似地用两条直线来表输入输出两条曲线可以近似地用两条直线来表示，其斜率示，其斜率示，其斜率示，其斜率( (平均生产率平均生产率平均生产率平均生产率) )等于平均在制品库存等于平均在制品库存等于平均在制品库存等于平均在制品库存/ /平均通过时间。

平均通过时间平均通过时间平均通过时间n n实际实践中，可以采用四个规则来调整输入、实际实践中，可以采用四个规则来调整输入、实际实践中，可以采用四个规则来调整输入、实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：输出、在制品库存和通过时间：输出、在制品库存和通过时间：输出、在制品库存和通过时间：①①   若希望保持在制品库存量，可暂时增加或减少输入若希望保持在制品库存量，可暂时增加或减少输入若希望保持在制品库存量，可暂时增加或减少输入若希望保持在制品库存量，可暂时增加或减少输入②②   若希望改变在制品库存量，可暂时增加或减少输入若希望改变在制品库存量，可暂时增加或减少输入若希望改变在制品库存量，可暂时增加或减少输入若希望改变在制品库存量，可暂时增加或减少输入③③   若希望平均通过时间在所控制的范围内，则适当调若希望平均通过时间在所控制的范围内，则适当调若希望平均通过时间在所控制的范围内，则适当调若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例整平均在制品库存与生产率的比例整平均在制品库存与生产率的比例整平均在制品库存与生产率的比例④④   要使各个工件的平均通过时间稳定，可以采用要使各个工件的平均通过时间稳定，可以采用要使各个工件的平均通过时间稳定，可以采用要使各个工件的平均通过时间稳定，可以采用FIFOFIFO规则来安排各工件的加工顺序。

规则来安排各工件的加工顺序规则来安排各工件的加工顺序规则来安排各工件的加工顺序本章小结本章小结 §11.1  排序问题的基本概念排序问题的基本概念 §11.2  流水作业排序问题流水作业排序问题§11.3 单件作业排序问题单件作业排序问题§11.4  生产作业控制生产作业控制。