制造业作业生产计划课件

第十一章制造业作业计划与控制§11.1排序问题的基本概念§11.2流水作业排序问题§11.3

单件作业排序问题§11.4生产作业控制精选课件第十一章制造业作业计划与控制§11.1排序问题的基本概1第一节排序的基本概念一、相关名词术语排序：确定工件在机器上的加工顺序。编制作业计划：不仅包括确定工件的加工顺序，还包括确定机器加工每个工件的开始时间和完成时间。我们习惯上不加区别地使用作业排序与作业计划。

派工：按照作业计划的要求，将具体的生产任务安排到具体的机床上加工。赶工：当实际进度落后于计划进度时采取的行动。加工线路：工件按照工艺过程进行加工的过程，一般用M1,M2,M3,M4来表示。加工顺序：表示每台机器加工n个工件的先后顺序，是排序要解决的问题。精选课件第一节排序的基本概念一、相关名词术语精选课件2二、排序问题的分类按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题;

按加工路线的特征，可分为单件作业排序问题和流水作业排序问题;

按工件到达工作中心（或车间）的情况不同可分为静态的排序问题（当进行排序时，所有工件都已到达，或准备就绪）和动态的排序问题（工件的到达是陆续的，要随时安排它们的加工顺序）;第一节排序的基本概念精选课件二、排序问题的分类按机器的种类和数量不同，可以分为单台机3二、排序问题的分类按目标函数不同，可分为流程最短问题与误工最少问题等；按目标函数的性质不同分为单目标排序问题与多目标排序问题;

按参数的性质，可以划分为确定型排序问题与随机型排序问题。第一节排序的基本概念精选课件二、排序问题的分类按目标函数不同，可分为流程最短问题与误4第一节排序的基本概念三、假设条件与符号说明（一）排序问题的假设条件一个工件不能同时在几台不同的机器上加工；工件在加工过程中采取平行移动方式；不允许中断；每道工序只在一台机器上完成；工件数、机器数和加工时间已知，加工时间与加工顺序无关；每台机器同时只能加工一个工件。精选课件第一节排序的基本概念三、假设条件与符号说明精选课件5第一节排序的基本概念三、假设条件与符号说明（二）有关符号说明精选课件第一节排序的基本概念三、假设条件与符号说明精选课件6四、排序问题的一般表示方法

4参数法：n/m/A/B

其中：n——工件数；

m——机器数；

A——工作车间类型；

B——目标函数，通常是使其最小

若A处为F代替，则表示流水作业排序问题；

若A处为P代替，则表示流水作业排列排序问题，即每个工件在各台机器上的加工顺序都相同；若m为1时，A为空白，即单台机器的排序，对于单台机器排序问题，无所谓加工路线问题。第一节排序的基本概念精选课件四、排序问题的一般表示方法第一节排序的基本概念精选课件7第二节流水作业排序问题流水作业排序问题的基本特征是每个工件的加工线路都一致。加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。本节要讨论的是所有工件在各台机器上的加工顺序相同的情况，就是排列排序问题n/m/P/B。精选课件第二节流水作业排序问题流水作业排序问题的基本特征是每个工件8第二节流水作业排序问题一、最长流程时间Fmax的计算P263[例11.1]有一个6/4/P/Fmax问题，其加工时间如表，当按顺序S=(6，1，5，2，4，3)加工时，求Fmax。表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331精选课件第二节流水作业排序问题一、最长流程时间Fmax的计算P269表11-2顺序下的加工时间矩阵P263[例11.1]有一个6/4/P/Fmax问题，其加工时间如表，当按顺序S=(6，1，5，2，4，3)加工时，求Fmax。表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446精选课件表11-2顺序下的加工时间矩阵P263[例11.1]有一10对于第1行第1列，只需把加工时间的数值作为完工时间标在加工时间的右上角;对于第1行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。对于从第2行到第m行，只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本列上一行的右上角数字中取较大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为Fmax。Fmax的标注完工时间的规则精选课件对于第1行第1列，只需把加工时间的数值作为完工时间标在加11第二节流水作业排序问题二、n/2/F/Fmax问题的最优算法对于n个工件1台机器的排序问题，既适用于流程作业,也适用于单件作业，在第三节单件作业排序讨论。对于n/2/F/Fmax问题，S.M.Johson于1954年给出了有效的算法，即著名的Johson算法。其目标是使从第一个工件开始到最后一个工件结束的总流程时间最短。精选课件第二节流水作业排序问题二、n/2/F/Fmax12

Johnson算法的步骤：列出所有工件在两台机器上的加工时间矩阵；从加工时间矩阵中找出最短的加工时间；若最短的加工时间出现在M1上，则对应的工件往前排；如果最短的加工时间出现在M2上，则对应的工件往后排；然后，划去已经排序的工件。若最短的加工时间有多个，则任选一个；当所有的工件都已排序，停止计算，转步骤①。二、n/2/F/Fmax问题的最优算法精选课件Johnson算法的步骤：二、n/2/F/F13

P264[例11.2]按Johnson法求下表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474表11-3加工时间矩阵最优加工顺序为S=（2，5，6，1，4，3）最优顺序下的Fmax=28精选课件P264[例11.2]i123456ai5185314Johnson算法的变形步骤：将所有ai≤bi的工件按照ai值不减（递升）的顺序排列成一个序列A；将所有ai＞bi的工件按bi值不增（递减）的顺序排列成一个序列B；将A放到B之前，就构成了最优加工顺序。精选课件Johnson算法的变形步骤：精选课件15

P264[例11.2]——Johnson算法的变形求下表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474表11-3加工时间矩阵序列A为（2,5,6,1），序列B为（4,3），则最优序列为S=（2,5,6,1,4,3），与Johnson算法的结果一致。精选课件P264[例11.2]——Johnson算法的变16n/m/P/Fmax问题的启发式算法启发式算法（试探法）是一种能在可接受的费用内寻找最好的解的技术，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式算法是解决NP问题（不确定性问题）的重要方法，由于其计算量都比较大，所以随着计算机技术的发展，启发式算法取得了巨大的成就。常见的启发式算法有贪婪法、局部搜索法、退火算法、蚁群算法等。

精选课件n/m/P/Fmax问题的启发式算法启发式算法（17经典算法与启发式算法驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后往山上开4.5公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路714

号。用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。精选课件经典算法与启发式算法驾驶汽车到达某人的家，写成算法是这样的：18

1965年，D·S·Palmer提出按斜度指标排列工件的启发式算法，这种算法称之为Palmer算法。其中工件斜度指标可按下式计算：算出λi后，按λi不增（递减）的顺序排列工件，可得出较满意的加工顺序。三、一般n/m/P/Fmax问题的启发式算法（一）Palmer（帕默）算法精选课件

1965年，D·S·Palmer提出按斜度指标19（一）Palmer

算法P266[例11.3]有一个4/3/F/Fmax问题，用Palmer算法求解最优加工顺序。加工时间矩阵为：三、一般n/m/P/Fmax问题的启发式算法i1234Pi11263Pi18429Pi14582精选课件（一）Palmer算法P266[例11.3]有一个4/320i1234Pi11263Pi18429Pi14582解：按照不增的顺序，得到最优加工顺序(1,2,3,4)和(2,1,3,4)精选课件i1234Pi11263Pi18429Pi14582解：按照21（二）关键工件法步骤如下：

1.计算每个工件的总加工时间Pi=∑pij，找出加工时间最长的工件C（j=m），将其作为关键工件。

2.对于余下的工件，若Pi1≤Pim，则按Pi1不减的顺序排列一个序列Sa；若Pi1>Pim，则按Pim不增的顺序排成一个序列Sb。

3.加工顺序（Sa，C，Sb）即为所求近优解。例11.3i1234Pi11263Pi18429Pi14582精选课件（二）关键工件法步骤如下：i1234Pi11263Pi18422三、一般n/m/P/Fmax问题的启发式算法（三）CDS算法

Campbell，Dudek，Smith三人提出了一个启发式算法，简称CDS算法。他们把Johnson算法用于一般n/m/P/Fmax问题，得到（m-1）个加工顺序，取其中优者。对加工时间，按下列公式求和，即：当l=1时,有两种排序方式,用Johnson方法排序得到一个最优排序；当l=2时，又有两种排序方法，用Johnson方法排序，得到又一个最优排序；当l=3,…，(m-1)，又可求出对应的每一种排序方法。最后比较取得最优解。精选课件三、一般n/m/P/Fmax问题的启发式算法（23本次课小结相关名次术语（排序、编制作业计划、派工、赶工、加工线路、加工顺序）最长流程时间的计算n/2/F/Fmax问题的最优算法（Johson算法）精选课件本次课小结相关名次术语（排序、编制作业计划、派工、赶工、24§11.3单件作业排序问题一、问题的描述特点：每个工件都有其独特的加工路线，工件没有固定的流向问题的描述：描述一道工序，要用3个参数(i,j,k)，表示工件i的第j道工序在机器k上进行。可以用加工描述矩阵来描述所有工件的加工精选课件§11.3单件作业排序问题特点：每个工件都有其独特的25§11.3单件作业排序问题一、问题的描述可以用加工描述矩阵来描述所有工件的加工例如，一个2/3/G/Fmax问题：工序1工序2工序3工件1工件2精选课件§11.3单件作业排序问题可以用加工描述矩阵来描述所26二、三种作业计划半能动作业计划（Semi-activeschedule）各工序都按最早可能开（完）工时间安排的作业计划能动作业计划（Activeschedule）任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划无延迟作业计划（Non-delayschedu1e）没有任何延迟出现的能动作业计划“延迟”：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序精选课件二、三种作业计划半能动作业计划（Semi-activesc27能动作业计划与无延迟作业计划的生成符号说明将每安排一道工序称作一“步”，设：｛St｝—第t步之前已排序工序构成的部分作业计划｛Ot｝—第t步可以排序的工序的集合

Tk—｛Ot｝中Ok的最早可能开工时间

T’k—｛Ot｝中Ok的最早可能完工时间精选课件能动作业计划与无延迟作业计划的生成符号说明精选课件28精选课件精选课件29P269例11.4

有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T已知，求一个能动作业计划。精选课件P269例11.4

有一个2/3/G/Fmax问题30精选课件精选课件31精选课件精选课件32精选课件精选课件33精选课件精选课件34精选课件精选课件35三、三类启发式算法优先调度法则随机抽样法概率调度法精选课件三、三类启发式算法优先调度法则精选课件361.优先调度法则SPT（Shortestprocessingtime）法则优先选择加工时间最短的工序可使工件的平均流程时间最短，从而减少在制品量FCFS（Firstcomefirstserved）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平EDD（Earliestduedate）法则优先选择完工期限紧的工件可使工件最大延误时间最小MWKR（Mostworkremaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近精选课件1.优先调度法则SPT（Shortestprocessin371.优先调度法则（续）LWKR（Leastworkremaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成MOPNR（Mostoperationsremaining）法则优先选择余下工序数最多的工件与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的SCR（Smallestcriticalratio）法则优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）保证工件延误最少RANDOM法则随机地挑一个工件精选课件1.优先调度法则（续）LWKR（Leastworkrem38精选课件精选课件392.随机抽样法随机抽样法•实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划•这种方法不一定能得到最优作业计划，但可以得到较满意的作业计划效果与样本大小有关。样本越大，获取较好解的可能性越大从无延迟作业计划母体中抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好精选课件2.随机抽样法随机抽样法精选课件403.概率调度法给不同的工序按某一优先调度法则分配不同的挑选概率，可以得到多个作业计划供比较。例如，在构成无延迟作业计划的第（3）步

•有3道工序，A、B和C可挑选

•3道工序所需的时间分别为3，4和7•将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率比如A、B和C的挑选概率分别为6/14、5/14和3/14既保证了SPT法则起作用，又可产生多个作业计划供挑选精选课件3.概率调度法给不同的工序按某一优先调度法则分配不同的挑选41生产作业控制是指在生产过程中，按既定的政策、目标、计划和标准，通过监督和检查生产活动的进展情况、实际成效，及时发现偏差，找出原因，采取措施，以保证目标、计划的实现。生产运作控制的受控客体是生产运作过程，其预定目标是主生产计划与生产作业计划的目标值。§11.4生产作业控制精选课件生产作业控制是指在生产过程中，按既定的政策、目标、计划和42一、生产活动与作业计划产生偏差的原因（1）加工时间估计不准确（2）随机因素的影响（3）加工路线的多样性（4）企业环境的动态性§11.4生产作业控制精选课件一、生产活动与作业计划产生偏差的原因§11.4生产作业控制43二、生产作业控制的程序制定生产作业监控体系监控实际生产过程评估偏差情况采取纠偏措施§11.4生产作业控制精选课件二、生产作业控制的程序§11.4生产作业控制精选课件44三、生产作业控制的主要工具实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：调度单日报、月报例外报告、异常报告输入/输出（I/O）报告精选课件三、生产作业控制的主要工具实际生产中，有不少工具可以用来进45漏斗模型德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（FunnelModel）。精选课件漏斗模型德国汉诺威大学的Bechte和Wiendall等人于46漏斗模型漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。

精选课件漏斗模型精选课件47注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔。精选课件注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达48控制规则在一段较长的时间内(如数周)内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率(平均生产率)等于平均在制品库存/平均通过时间。实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：若希望保持在制品库存量，可暂时增加或减少输入。若希望改变在制品库存量，可暂时增加或减少输入。若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。精选课件控制规则在一段较长的时间内(如数周)内，若工况稳定，输入输出49本章小结§11.1排序问题的基本概念§11.2流水作业排序问题§11.3

单件作业排序问题§11.4生产作业控制精选课件本章小结§11.1排序问题的基本概念精选课件50第十一章制造业作业计划与控制§11.1排序问题的基本概念§11.2流水作业排序问题§11.3

单件作业排序问题§11.4生产作业控制精选课件第十一章制造业作业计划与控制§11.1排序问题的基本概51第一节排序的基本概念一、相关名词术语排序：确定工件在机器上的加工顺序。编制作业计划：不仅包括确定工件的加工顺序，还包括确定机器加工每个工件的开始时间和完成时间。我们习惯上不加区别地使用作业排序与作业计划。

派工：按照作业计划的要求，将具体的生产任务安排到具体的机床上加工。赶工：当实际进度落后于计划进度时采取的行动。加工线路：工件按照工艺过程进行加工的过程，一般用M1,M2,M3,M4来表示。加工顺序：表示每台机器加工n个工件的先后顺序，是排序要解决的问题。精选课件第一节排序的基本概念一、相关名词术语精选课件52二、排序问题的分类按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题;

按加工路线的特征，可分为单件作业排序问题和流水作业排序问题;

按工件到达工作中心（或车间）的情况不同可分为静态的排序问题（当进行排序时，所有工件都已到达，或准备就绪）和动态的排序问题（工件的到达是陆续的，要随时安排它们的加工顺序）;第一节排序的基本概念精选课件二、排序问题的分类按机器的种类和数量不同，可以分为单台机53二、排序问题的分类按目标函数不同，可分为流程最短问题与误工最少问题等；按目标函数的性质不同分为单目标排序问题与多目标排序问题;

按参数的性质，可以划分为确定型排序问题与随机型排序问题。第一节排序的基本概念精选课件二、排序问题的分类按目标函数不同，可分为流程最短问题与误54第一节排序的基本概念三、假设条件与符号说明（一）排序问题的假设条件一个工件不能同时在几台不同的机器上加工；工件在加工过程中采取平行移动方式；不允许中断；每道工序只在一台机器上完成；工件数、机器数和加工时间已知，加工时间与加工顺序无关；每台机器同时只能加工一个工件。精选课件第一节排序的基本概念三、假设条件与符号说明精选课件55第一节排序的基本概念三、假设条件与符号说明（二）有关符号说明精选课件第一节排序的基本概念三、假设条件与符号说明精选课件56四、排序问题的一般表示方法

4参数法：n/m/A/B

其中：n——工件数；

m——机器数；

A——工作车间类型；

B——目标函数，通常是使其最小

若A处为F代替，则表示流水作业排序问题；

若A处为P代替，则表示流水作业排列排序问题，即每个工件在各台机器上的加工顺序都相同；若m为1时，A为空白，即单台机器的排序，对于单台机器排序问题，无所谓加工路线问题。第一节排序的基本概念精选课件四、排序问题的一般表示方法第一节排序的基本概念精选课件57第二节流水作业排序问题流水作业排序问题的基本特征是每个工件的加工线路都一致。加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。本节要讨论的是所有工件在各台机器上的加工顺序相同的情况，就是排列排序问题n/m/P/B。精选课件第二节流水作业排序问题流水作业排序问题的基本特征是每个工件58第二节流水作业排序问题一、最长流程时间Fmax的计算P263[例11.1]有一个6/4/P/Fmax问题，其加工时间如表，当按顺序S=(6，1，5，2，4，3)加工时，求Fmax。表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331精选课件第二节流水作业排序问题一、最长流程时间Fmax的计算P2659表11-2顺序下的加工时间矩阵P263[例11.1]有一个6/4/P/Fmax问题，其加工时间如表，当按顺序S=(6，1，5，2，4，3)加工时，求Fmax。表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446精选课件表11-2顺序下的加工时间矩阵P263[例11.1]有一60对于第1行第1列，只需把加工时间的数值作为完工时间标在加工时间的右上角;对于第1行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。对于从第2行到第m行，只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本列上一行的右上角数字中取较大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为Fmax。Fmax的标注完工时间的规则精选课件对于第1行第1列，只需把加工时间的数值作为完工时间标在加61第二节流水作业排序问题二、n/2/F/Fmax问题的最优算法对于n个工件1台机器的排序问题，既适用于流程作业,也适用于单件作业，在第三节单件作业排序讨论。对于n/2/F/Fmax问题，S.M.Johson于1954年给出了有效的算法，即著名的Johson算法。其目标是使从第一个工件开始到最后一个工件结束的总流程时间最短。精选课件第二节流水作业排序问题二、n/2/F/Fmax62

Johnson算法的步骤：列出所有工件在两台机器上的加工时间矩阵；从加工时间矩阵中找出最短的加工时间；若最短的加工时间出现在M1上，则对应的工件往前排；如果最短的加工时间出现在M2上，则对应的工件往后排；然后，划去已经排序的工件。若最短的加工时间有多个，则任选一个；当所有的工件都已排序，停止计算，转步骤①。二、n/2/F/Fmax问题的最优算法精选课件Johnson算法的步骤：二、n/2/F/F63

P264[例11.2]按Johnson法求下表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474表11-3加工时间矩阵最优加工顺序为S=（2，5，6，1，4，3）最优顺序下的Fmax=28精选课件P264[例11.2]i123456ai5185364Johnson算法的变形步骤：将所有ai≤bi的工件按照ai值不减（递升）的顺序排列成一个序列A；将所有ai＞bi的工件按bi值不增（递减）的顺序排列成一个序列B；将A放到B之前，就构成了最优加工顺序。精选课件Johnson算法的变形步骤：精选课件65

P264[例11.2]——Johnson算法的变形求下表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474表11-3加工时间矩阵序列A为（2,5,6,1），序列B为（4,3），则最优序列为S=（2,5,6,1,4,3），与Johnson算法的结果一致。精选课件P264[例11.2]——Johnson算法的变66n/m/P/Fmax问题的启发式算法启发式算法（试探法）是一种能在可接受的费用内寻找最好的解的技术，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式算法是解决NP问题（不确定性问题）的重要方法，由于其计算量都比较大，所以随着计算机技术的发展，启发式算法取得了巨大的成就。常见的启发式算法有贪婪法、局部搜索法、退火算法、蚁群算法等。

精选课件n/m/P/Fmax问题的启发式算法启发式算法（67经典算法与启发式算法驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后往山上开4.5公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路714

号。用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。精选课件经典算法与启发式算法驾驶汽车到达某人的家，写成算法是这样的：68

1965年，D·S·Palmer提出按斜度指标排列工件的启发式算法，这种算法称之为Palmer算法。其中工件斜度指标可按下式计算：算出λi后，按λi不增（递减）的顺序排列工件，可得出较满意的加工顺序。三、一般n/m/P/Fmax问题的启发式算法（一）Palmer（帕默）算法精选课件

1965年，D·S·Palmer提出按斜度指标69（一）Palmer

算法P266[例11.3]有一个4/3/F/Fmax问题，用Palmer算法求解最优加工顺序。加工时间矩阵为：三、一般n/m/P/Fmax问题的启发式算法i1234Pi11263Pi18429Pi14582精选课件（一）Palmer算法P266[例11.3]有一个4/370i1234Pi11263Pi18429Pi14582解：按照不增的顺序，得到最优加工顺序(1,2,3,4)和(2,1,3,4)精选课件i1234Pi11263Pi18429Pi14582解：按照71（二）关键工件法步骤如下：

1.计算每个工件的总加工时间Pi=∑pij，找出加工时间最长的工件C（j=m），将其作为关键工件。

2.对于余下的工件，若Pi1≤Pim，则按Pi1不减的顺序排列一个序列Sa；若Pi1>Pim，则按Pim不增的顺序排成一个序列Sb。

3.加工顺序（Sa，C，Sb）即为所求近优解。例11.3i1234Pi11263Pi18429Pi14582精选课件（二）关键工件法步骤如下：i1234Pi11263Pi18472三、一般n/m/P/Fmax问题的启发式算法（三）CDS算法

Campbell，Dudek，Smith三人提出了一个启发式算法，简称CDS算法。他们把Johnson算法用于一般n/m/P/Fmax问题，得到（m-1）个加工顺序，取其中优者。对加工时间，按下列公式求和，即：当l=1时,有两种排序方式,用Johnson方法排序得到一个最优排序；当l=2时，又有两种排序方法，用Johnson方法排序，得到又一个最优排序；当l=3,…，(m-1)，又可求出对应的每一种排序方法。最后比较取得最优解。精选课件三、一般n/m/P/Fmax问题的启发式算法（73本次课小结相关名次术语（排序、编制作业计划、派工、赶工、加工线路、加工顺序）最长流程时间的计算n/2/F/Fmax问题的最优算法（Johson算法）精选课件本次课小结相关名次术语（排序、编制作业计划、派工、赶工、74§11.3单件作业排序问题一、问题的描述特点：每个工件都有其独特的加工路线，工件没有固定的流向问题的描述：描述一道工序，要用3个参数(i,j,k)，表示工件i的第j道工序在机器k上进行。可以用加工描述矩阵来描述所有工件的加工精选课件§11.3单件作业排序问题特点：每个工件都有其独特的75§11.3单件作业排序问题一、问题的描述可以用加工描述矩阵来描述所有工件的加工例如，一个2/3/G/Fmax问题：工序1工序2工序3工件1工件2精选课件§11.3单件作业排序问题可以用加工描述矩阵来描述所76二、三种作业计划半能动作业计划（Semi-activeschedule）各工序都按最早可能开（完）工时间安排的作业计划能动作业计划（Activeschedule）任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划无延迟作业计划（Non-delayschedu1e）没有任何延迟出现的能动作业计划“延迟”：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序精选课件二、三种作业计划半能动作业计划（Semi-activesc77能动作业计划与无延迟作业计划的生成符号说明将每安排一道工序称作一“步”，设：｛St｝—第t步之前已排序工序构成的部分作业计划｛Ot｝—第t步可以排序的工序的集合

Tk—｛Ot｝中Ok的最早可能开工时间

T’k—｛Ot｝中Ok的最早可能完工时间精选课件能动作业计划与无延迟作业计划的生成符号说明精选课件78精选课件精选课件79P269例11.4

有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T已知，求一个能动作业计划。精选课件P269例11.4

有一个2/3/G/Fmax问题80精选课件精选课件81精选课件精选课件82精选课件精选课件83精选课件精选课件84精选课件精选课件85三、三类启发式算法优先调度法则随机抽样法概率调度法精选课件三、三类启发式算法优先调度法则精选课件861.优先调度法则SPT（Shortestprocessingtime）法则优先选择加工时间最短的工序可使工件的平均流程时间最短，从而减少在制品量FCFS（Firstcomefirstserved）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平EDD（Earliestduedate）法则优先选择完工期限紧的工件可使工件最大延误时间最小MWKR（Mostworkremaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近精选课件1.优先调度法则SPT（Shortestprocessin871.优先调度法则（续）LWKR（Leastworkremaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成MOPNR（Mostoperationsremaining）法则优先选择余下工序数最多的工件与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的SCR（Smallestcriticalratio）法则优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）保证工件延误最少RANDOM法则随机地挑一个工件精选课件1.优先调度法则（续）LWKR（Leas