制造业作业生计划

1、第一节第一节 排序的基本概念排序的基本概念一、相关名词术语一、相关名词术语u排序：排序：确定工件在机器上的加工顺序。确定工件在机器上的加工顺序。u编制作业计划：编制作业计划：不仅包括确定工件的加工顺序不仅包括确定工件的加工顺序，还，还包括包括确定机器加工每个工件的开始时间和完成时间。我们习惯上确定机器加工每个工件的开始时间和完成时间。我们习惯上不加区别地使用作业排序与作业计划。不加区别地使用作业排序与作业计划。 u派工：派工：按照作业计划的要求，将具体的生产任务安排到具按照作业计划的要求，将具体的生产任务安排到具体的机床上加工。体的机床上加工。u赶工：赶工：当实际进度落后于计划进度时采取的行动

2、。当实际进度落后于计划进度时采取的行动。u加工线路：加工线路：工件按照工艺过程进行加工的过程，一般用工件按照工艺过程进行加工的过程，一般用m m1 1,m,m2 2,m,m3 3,m,m4 4来表示。来表示。u加工顺序：加工顺序：表示每台机器加工表示每台机器加工n n个工件的先后顺序，是排个工件的先后顺序，是排序要解决的问题。序要解决的问题。二、排序问题的分类二、排序问题的分类n 按机器的种类和数量不同，可以分为单台机器按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题的排序问题和多台机器的排序问题; ; n 按加工路线的特征，可分为按加工路线的特征，可分为单件作业排序问题

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

4、目标函数的性质不同分为单目标排序问题与按目标函数的性质不同分为单目标排序问题与多目标排序问题多目标排序问题; ; n 按参数的性质，可以划分为确定型排序问题与按参数的性质，可以划分为确定型排序问题与随机型排序问题。随机型排序问题。 第一节第一节 排序的基本概念排序的基本概念第一节第一节 排序的基本概念排序的基本概念三、假设条件与符号说明三、假设条件与符号说明（一）排序问题的假设条件（一）排序问题的假设条件1.1.一个工件不能同时在几台不同的机器上加工；一个工件不能同时在几台不同的机器上加工；2.2.工件在加工过程中采取工件在加工过程中采取平行平行移动方式；移动方式；3.3.不允许中断；不允许中

5、断；4.4.每道工序只在一台机器上完成；每道工序只在一台机器上完成；5.5.工件数、机器数和加工时间已知，加工时间与加工件数、机器数和加工时间已知，加工时间与加工顺序无关；工顺序无关；6.6.每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。第一节第一节 排序的基本概念排序的基本概念三、假设条件与符号说明三、假设条件与符号说明（二）有关符号说明（二）有关符号说明maxmaxmaxmaxmaxmax,1,2,1,2,0ijijijiiiiiji inmj jmpjmrjjcffcrrfc工件机器 在上的加工时间工件 的到达时间，指 可以开始加工的最早时间最长完工时间最长流程时间，当时，

6、最长流程时间是从第一个工件在第一台机器开始加工起，到最后一个工件在最后一台机器上加工完成为止的时间。四、排序问题的一般表示方法四、排序问题的一般表示方法 4 4参数法：参数法：n/m/a/bn/m/a/b 其中：其中：n 工件数；工件数； m机器数；机器数； a工作车间类型；工作车间类型； b目标函数，通常是使其最小目标函数，通常是使其最小 u 若若a a处为处为f f代替，则表示流水作业排序问题；代替，则表示流水作业排序问题；u 若若a a处为处为p p代替，则表示流水作业代替，则表示流水作业排列排序排列排序问题，即每问题，即每个工件在各台机器上的加工顺序都相同；个工件在各台机器上的加工顺序

7、都相同；u 若若m m为为1 1时，时，a a为空白，即单台机器的排序，对于单台机为空白，即单台机器的排序，对于单台机器排序问题，无所谓加工路线问题。器排序问题，无所谓加工路线问题。第一节第一节 排序的基本概念排序的基本概念第二节第二节 流水作业排序问题流水作业排序问题n流水作业排序问题的基本特征是流水作业排序问题的基本特征是每个工件每个工件的加工线路都一致的加工线路都一致。n加工线路一致，是指工件的加工线路一致，是指工件的流向一致流向一致，并，并不是指每个工件必须经过加工线路上的每不是指每个工件必须经过加工线路上的每台机器加工。台机器加工。n本节要讨论的是所有工件在各台机器上的本节要讨论的是

8、所有工件在各台机器上的加工顺序相同的情况，就是加工顺序相同的情况，就是排列排序排列排序问题问题n/m/p/b。第二节第二节 流水作业排序问题流水作业排序问题maxup263例例11.1 有一个有一个6/4/p/fmax问题，其加工时间如表，问题，其加工时间如表，当按顺序当按顺序 s=(6，1，5，2，4，3)加工时，求加工时，求 fmax。表表11-1 11-1 加工时间矩阵加工时间矩阵i1i2i3i4表表11-2 11-2 顺序下的加工时间矩阵顺序下的加工时间矩阵up263p263例例11.1 11.1 有一个有一个6/4/p/fmax6/4/p/fmax问题，其加工时间如表，问题，其加工时

9、间如表，当按顺序当按顺序 s=(6s=(6，1 1，5 5，2 2，4 4，3)3)加工时，求加工时，求 f fmaxmax。表表11-1 11-1 加工时间矩阵加工时间矩阵i1i2i3i4i1i2i3i4u 对于对于第第1 1行第行第1 1列列，只需把加工时间的数值作为完，只需把加工时间的数值作为完工时间标在加工时间的右上角工时间标在加工时间的右上角; ;对于第对于第1 1行的其它元素，行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。工时间，将结果填在计算列加工时间的右上角。u 对于从第对于从

10、第2 2行到第行到第m m行，只要把行，只要把上一行右上角上一行右上角的数的数字和本行的加工时间相加，将结果填在加工时间的右字和本行的加工时间相加，将结果填在加工时间的右上角；上角；u 从第从第2 2列到第列到第n n列，则要从本行前一列右上角和本列，则要从本行前一列右上角和本列上一行的右上角数字中列上一行的右上角数字中取较大者取较大者，再和本列加工时，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为算下去，最后一行的最后一列右上角数字，即为f fmaxmax。 maxmax第二节第二节 流水作

11、业排序问题流水作业排序问题max 问题的最优算法问题的最优算法 对于对于n n个工件个工件1 1台机器的排序问题，既适用于流程台机器的排序问题，既适用于流程作业作业, ,也适用于单件作业，在第三节单件作业排序也适用于单件作业，在第三节单件作业排序讨论。讨论。 对于对于n / 2 / f / fmax 问题，问题，s.m.johson于于1954年年给出了有效的算法，即著名的给出了有效的算法，即著名的johson算法。其目标算法。其目标是使从第一个工件开始到最后一个工件结束的是使从第一个工件开始到最后一个工件结束的总流总流程时间最短。程时间最短。 johnson算法的步骤：算法的步骤： 列出所有

12、工件在两台机器上的加工时间矩阵；列出所有工件在两台机器上的加工时间矩阵； 从加工时间矩阵中找出从加工时间矩阵中找出最短最短的加工时间；的加工时间； 若最短的加工时间出现在若最短的加工时间出现在m m1 1上，则对应的工件上，则对应的工件往前排往前排；如果最短的加工时间出现在；如果最短的加工时间出现在m m2 2上，则对上，则对应的工件应的工件往后排往后排；然后，；然后，划去已经排序的工件划去已经排序的工件。若最短的加工时间有多个，则任选一个；若最短的加工时间有多个，则任选一个； 当所有的工件都已排序，停止计算，转步骤当所有的工件都已排序，停止计算，转步骤。max 问题的最优算法问题的最优算法

13、p264例例11.2 u按按johnson法求下表所示的法求下表所示的6/2/f/fmax问题的最优解。问题的最优解。表表11-3 11-3 加工时间矩阵加工时间矩阵最优加工顺序为最优加工顺序为s=s=（2 2，5 5，6 6，1 1，4 4，3 3）最优顺序下的最优顺序下的f fmaxmax=28=28johnson算法的变形算法的变形n步骤：步骤：将所有将所有aibi的工件按照的工件按照ai值值不减（递升）不减（递升）的的顺序排列成一个序列顺序排列成一个序列a；将所有将所有aibi的工件按的工件按bi值值不增（递减）不增（递减）的的顺序排列成一个序列顺序排列成一个序列b；将将a放到放到b之

14、前，就构成了最优加工顺序。之前，就构成了最优加工顺序。 p264例例11.2 johnson算法的变形算法的变形u求下表所示的求下表所示的6/2/f/fmax问题的最优解。问题的最优解。表表11-3 11-3 加工时间矩阵加工时间矩阵序列序列a为（为（2,5,6,1），序列），序列b为（为（4,3），），则最优序列为则最优序列为s=（2,5,6,1,4,3），），与与johnson算法的结果一致。算法的结果一致。 1965年，年，dspalmer提出按提出按斜度指标斜度指标排列工件的启发排列工件的启发式算法，这种算法称之为式算法，这种算法称之为palmerpalmer算法。算法。其中其中工件斜

15、度指标工件斜度指标可按下式计算：可按下式计算： 算出算出i后，按后，按i不增（递减）不增（递减）的的顺序排列工件，可得出较顺序排列工件，可得出较满意的加工顺序。满意的加工顺序。1(1)/2,1,2,mimiikkikkmpknpk式中， 为机器数，为工件 在m 上的加工时间p266例例11.3 有一个有一个4/3/f/fmax问题，用问题，用palmer算法求解算法求解最优加工顺序。加工时间矩阵为：最优加工顺序。加工时间矩阵为：i1i1i11(1)/2,1,2,mimiikkikkmpknpk式中， 为机器数，为工件 在m 上的加工时间i1i1i11(1)/2,1,2,mimiikkikkmp

16、knpk式中， 为机器数，为工件 在m 上的加工时间解：解：i3i131pp. 3 , 2 , 1,2iikkikpk则，-123pp4286pp3352pp341pp434133312321213111按照按照 不增的顺序，不增的顺序，得到最优加工顺序得到最优加工顺序(1,2,3,4)和和(2,1,3,4)iu步骤如下：步骤如下： 1. 计算每个工件的总加工时间计算每个工件的总加工时间pi=pij，找出加工时间最，找出加工时间最长的工件长的工件c（j=m），将其作为），将其作为关键工件关键工件。 2. 对于余下的工件，若对于余下的工件，若pi1pim，则按，则按pi1不减不减的顺序排的顺序排

17、列一个序列列一个序列sa；若；若pi1pim，则按，则按pim不增的顺序排成一个序不增的顺序排成一个序列列sb。 3. 加工顺序（加工顺序（sa，c，sb）即为所求近优解。）即为所求近优解。例例11.3i1i1i1 当当l=1时时,有两种排序方式有两种排序方式,用用johnson 方法排序得到一个最优方法排序得到一个最优排序；当排序；当l=2时，又有两种排序方法，用时，又有两种排序方法，用johnson方法排序，得方法排序，得到又一个最优排序；当到又一个最优排序；当l=3,，(m-1)，又可求出对应的每一种，又可求出对应的每一种排序方法。最后比较取得最优解。排序方法。最后比较取得最优解。11,

18、1,2,1lmikikkk mlpplm 和单件作业排序问题单件作业排序问题一、问题的描述一、问题的描述u 特点：每个工件都有其独特的加工路线，工特点：每个工件都有其独特的加工路线，工件件没有固定没有固定的流向的流向u 问题的描述：描述一道工序，要用问题的描述：描述一道工序，要用3个参数个参数(i,j,k)，表示工件，表示工件 i 的第的第 j 道工序在机器道工序在机器 k 上进行。上进行。u 可以用可以用加工描述矩阵加工描述矩阵来描述所有工件的加工来描述所有工件的加工单件作业排序问题单件作业排序问题一、问题的描述一、问题的描述u 可以用可以用加工描述矩阵加工描述矩阵来描述所有工件的加工来描述

19、所有工件的加工 例如，一个例如，一个2/3/g/fmax问题：问题：2 , 3 , 22 , 3 , 11 , 2 , 23 , 2 , 13 , 1 , 21 , 1 , 1d工序工序1工序工序2工序工序3工件工件1工件工件2二、三种作业计划二、三种作业计划1.半能动作业计划（半能动作业计划（semi-active schedule）各工序都按最早可能开（完）工时间安排的作业计划各工序都按最早可能开（完）工时间安排的作业计划2.能动作业计划（能动作业计划（active schedule）任何一台机器的每段空闲时间都不足以加工一道可加任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动

20、作业计划工工序的半能动作业计划3.无延迟作业计划（无延迟作业计划（non-delay schedu1e）没有任何延迟出现的能动作业计划没有任何延迟出现的能动作业计划“延迟延迟”：有工件等待加工时，机器出现空闲，即使：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序这段空闲时间不足以完成一道工序能动作业计划与无延迟作业计划的生成能动作业计划与无延迟作业计划的生成符号说明符号说明将每安排一道工序称作一将每安排一道工序称作一“步步”，设：，设：ust第第t 步之前已排序工序构成的部分作业计划步之前已排序工序构成的部分作业计划uot第第t 步可以排序的工序的集合步可以排序的工序的集合

21、u tkot中中ok的最早可能的最早可能开工开工时间时间u tkot中中ok的最早可能的最早可能完工完工时间时间1.优先调度法则优先调度法则nspt（shortest processing time）法则）法则优先选择加工时间最短的工序优先选择加工时间最短的工序可使工件的平均流程时间最短，从而减少在制品量可使工件的平均流程时间最短，从而减少在制品量nfcfs（first come first served）法则）法则优先选择最早进入可排工序集合的工件优先选择最早进入可排工序集合的工件来自排队论，对工件较公平来自排队论，对工件较公平nedd（earliest due date）法则）法则优先选择

22、完工期限紧的工件优先选择完工期限紧的工件可使工件最大延误时间最小可使工件最大延误时间最小nmwkr（most work remaining）法则）法则优先选择余下加工时间最长的工件优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近不同工作量的工件的完工时间尽量接近1.优先调度法则（续）优先调度法则（续）nlwkr（least work remaining）法则）法则优先选择余下加工时间最短的工件优先选择余下加工时间最短的工件使工作量小的工件尽快完成使工作量小的工件尽快完成nmopnr（most operations remaining）法则）法则优先选择余下工序数最多的工件优先选择余下工序数最多的工件与与mwkr法则类似，只不过考虑工件在不同机器上的法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的转运排队时间是主要的nscr（smallest critical ratio）法则）法则优先选择临界比最小的工件（临界比：工件允许停留优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）时间与工件余下加工时间之比）保证工件延误最少保证工件延误最少nrandom法则法则随机地挑一个工件随机地挑一个工件2.随机抽样法随机抽样法n随