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

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

2、落后于计划进度时采取的行动。动。加工线路：工件按照工艺过程进行加工的过程，加工线路：工件按照工艺过程进行加工的过程，一般用一般用M1,M2,M3,M4M1,M2,M3,M4来表示。来表示。加工顺序：表示每台机器加工加工顺序：表示每台机器加工n n个工件的先后个工件的先后顺序，是排序要解决的问题。顺序，是排序要解决的问题。二、排序问题的分类二、排序问题的分类n 按机器的种类和数量不同，可以分为单台机器按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题的排序问题和多台机器的排序问题; ; n 按加工路线的特征，可分为单件作业排序问题按加工路线的特征，可分为单件作业排序问题和流水

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

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

5、器数和加工时间已知，加工时间工件数、机器数和加工时间已知，加工时间与加工顺序无关；与加工顺序无关；每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。第一节第一节 排序的基本概念排序的基本概念三、假设条件与符号说明三、假设条件与符号说明（二有关符号说明（二有关符号说明maxmaxmaxmaxmaxmax,1,2,1,2,0ijijijiiiiiJi inMj jmpJMrJJCFFCrrFC工件机器 在上的加工时间工件 的到达时间，指 可以开始加工的最早时间最长完工时间最长流程时间，当时，最长流程时间是从第一个工件在第一台机器开始加工起，到最后一个工件在最后一台机器上加工完成为止的时间

6、。四、排序问题的一般表示方法四、排序问题的一般表示方法 4 4参数法：参数法：n/m/A/Bn/m/A/B 其中：其中：n n 工件数；工件数； m m机器数；机器数； A A工作车间类型；工作车间类型； B B目标函数，通常是使其最小目标函数，通常是使其最小 若若A A处为处为F F代替，则表示流水作业排序问题；代替，则表示流水作业排序问题； 若若A A处为处为P P代替，则表示流水作业排列排序问题，代替，则表示流水作业排列排序问题，即每个工件在各台机器上的加工顺序都相同；即每个工件在各台机器上的加工顺序都相同； 若若m m为为1 1时，时，A A为空白，即单台机器的排序，对于为空白，即单台

7、机器的排序，对于单台机器排序问题，无所谓加工路线问题。单台机器排序问题，无所谓加工路线问题。第一节第一节 排序的基本概念排序的基本概念第二节第二节 流水作业排序问题流水作业排序问题第二节第二节 流水作业排序问题流水作业排序问题uP263例例11.1 有一个有一个6/4/P/Fmax问题，其加工时间如表，问题，其加工时间如表，当按顺序当按顺序 S=(6，1，5，2，4，3)加工时，求加工时，求 Fmax。表表11-1 11-1 加工时间矩阵加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331表表11-2 11-2 顺序下的加工时间矩阵顺序下的加工时间

8、矩阵uP263P263例例11.1 11.1 有一个有一个6/4/P/Fmax6/4/P/Fmax问题，其加工时间如表，问题，其加工时间如表，当按顺序当按顺序 S=(6 S=(6，1 1，5 5，2 2，4 4，3)3)加工时，求加工时，求 Fmax Fmax。表表11-1 11-1 加工时间矩阵加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446u 对于第对于第1 1行第行

9、第1 1列，只需把加工时间的数值作为完列，只需把加工时间的数值作为完工时间标在加工时间的右上角工时间标在加工时间的右上角; ;对于第对于第1 1行的其它元素，行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。工时间，将结果填在计算列加工时间的右上角。u 对于从第对于从第2 2行到第行到第m m行，只要把上一行右上角的数行，只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右字和本行的加工时间相加，将结果填在加工时间的右上角；上角；u 从第从第2 2列到第列到第n n列，则要从本行前

10、一列右上角和本列，则要从本行前一列右上角和本列上一行的右上角数字中取较大者，再和本列加工时列上一行的右上角数字中取较大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为算下去，最后一行的最后一列右上角数字，即为FmaxFmax。 第二节第二节 流水作业排序问题流水作业排序问题 对于对于n n个工件个工件1 1台机器的排序问题，既适用于流程台机器的排序问题，既适用于流程作业作业, ,也适用于单件作业，在第三节单件作业排序也适用于单件作业，在第三节单件作业排序讨论。讨论。 对于对于n / 2 /

11、F / Fmax n / 2 / F / Fmax 问题，问题，S.M.JohsonS.M.Johson于于19541954年给出了有效的算法，即著名的年给出了有效的算法，即著名的JohsonJohson算法。算法。其目标是使从第一个工件开始到最后一个工件结束其目标是使从第一个工件开始到最后一个工件结束的总流程时间最短。的总流程时间最短。 Johnson算法的步骤：算法的步骤： 列出所有工件在两台机器上的加工时间矩列出所有工件在两台机器上的加工时间矩阵；阵； 从加工时间矩阵中找出最短的加工时间；从加工时间矩阵中找出最短的加工时间； 若最短的加工时间出现在若最短的加工时间出现在M1上，则对应的上

12、，则对应的工件往前排；如果最短的加工时间出现在工件往前排；如果最短的加工时间出现在M2上，则对应的工件往后排；然后，划去上，则对应的工件往后排；然后，划去已经排序的工件。若最短的加工时间有多已经排序的工件。若最短的加工时间有多个，则任选一个；个，则任选一个； 当所有的工件都已排序，停止计算，转步当所有的工件都已排序，停止计算，转步骤。骤。 P264例例11.2 按按Johnson法求下表所示的法求下表所示的6/2/F/Fmax问题的最优解。问题的最优解。i123456ai518534bi722474表表11-3 11-3 加工时间矩阵加工时间矩阵最优加工顺序为最优加工顺序为S=S=（2 2，5

13、 5，6 6，1 1，4 4，3 3）最优顺序下的最优顺序下的Fmax=28Fmax=28 P264例例11.2 Johnson算法的变形算法的变形求下表所示的求下表所示的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算法的结果一致。算法的结果一致。 1965年，年，DSPalmer提出按斜度指标排列工件的启发提出按斜度指标排列工件的启发式算法，这种算法称之为

14、式算法，这种算法称之为Palmer算法。算法。其中工件斜度指标可按下式计算：其中工件斜度指标可按下式计算： 算出算出i后，按后，按i不增递减的顺序排列工件，可得出较不增递减的顺序排列工件，可得出较满意的加工顺序。满意的加工顺序。1(1)/2,1,2,mimiikkikkmpknpk式中， 为机器数，为工件 在M 上的加工时间P266例例11.3 有一个有一个4/3/F/Fmax问题，用问题，用Palmer算法求解算法求解最优加工顺序。加工时间矩阵为：最优加工顺序。加工时间矩阵为：i1234Pi11263Pi18429Pi145821(1)/2,1,2,mimiikkikkmpknpk式中， 为

15、机器数，为工件 在M 上的加工时间i1234Pi11263Pi18429Pi145821(1)/2,1,2,mimiikkikkmpknpk式中， 为机器数，为工件 在M 上的加工时间解：解：i3i131pp. 3 , 2 , 1,2iikkikpk则，-123pp4286pp3352pp341pp434133312321213111依照依照 不增的顺序，不增的顺序，得到最优加工顺序得到最优加工顺序(1,2,3,4)(1,2,3,4)和和(2,1,3,4)(2,1,3,4)iu步骤如下：步骤如下：u 1. 计算每个工件的总加工时间计算每个工件的总加工时间Pi=pij，找出加工时，找出加工时间最

16、长的工件间最长的工件Cj=m），将其作为关键工件。），将其作为关键工件。u 2. 对于余下的工件，若对于余下的工件，若Pi1Pim，则按，则按Pi1不减的顺序不减的顺序排列一个序列排列一个序列Sa；若；若Pi1Pim，则按，则按Pim不增的顺序排成不增的顺序排成一个序列一个序列Sb。u 3. 加工顺序加工顺序Sa，C，Sb即为所求近优解。即为所求近优解。u例例11.3i1234Pi11263Pi18429Pi14582 当当l=1时时,有两种排序方式有两种排序方式,用用Johnson 方法排序得到一个最优方法排序得到一个最优排序；当排序；当l=2时，又有两种排序方法，用时，又有两种排序方法，用

17、Johnson方法排序，得方法排序，得到又一个最优排序；当到又一个最优排序；当l=3,，(m-1)，又可求出对应的每一种，又可求出对应的每一种排序方法。最后比较取得最优解。排序方法。最后比较取得最优解。11,1,2,1lmikikkk mlpplm 和u 特点：每个工件都有其独特的加工路线，工特点：每个工件都有其独特的加工路线，工件没有固定的流向件没有固定的流向u 问题的描述：描述一道工序，要用问题的描述：描述一道工序，要用3 3个参数个参数(i,j,k)(i,j,k)，表示工件，表示工件 i i 的第的第 j j 道工序在机器道工序在机器 k k 上进行。上进行。u 可以用加工描述矩阵来描述所有工件