制造业作业生产计划.ppt

第十一章 制造业作业计划与控制,11.1 排序问题的基本概念 11.2 流水作业排序问题 11.3 单件作业排序问题 11.4 生产作业控制,第一节 排序的基本概念,一、相关名词术语 排序：确定工件在机器上的加工顺序。 编制作业计划：不仅包括确定工件的加工顺序，还包括确定机器加工每个工件的开始时间和完成时间。我们习惯上不加区别地使用作业排序与作业计划。 派工：按照作业计划的要求，将具体的生产任务安排到具体的机床上加工。 赶工：当实际进度落后于计划进度时采取的行动。 加工线路：工件按照工艺过程进行加工的过程，一般用M1,M2,M3,M4来表示。 加工顺序：表示每台机器加工n个工件的先后顺序，是排序要解决的问题。,二、排序问题的分类,按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题; 按加工路线的特征，可分为单件作业排序问题和流水作业排序问题; 按工件到达工作中心（或车间）的情况不同可分为静态的排序问题（当进行排序时，所有工件都已到达，或准备就绪）和动态的排序问题（工件的到达是陆续的，要随时安排它们的加工顺序）;,第一节 排序的基本概念,二、排序问题的分类,按目标函数不同，可分为流程最短问题与误工最少问题等； 按目标函数的性质不同分为单目标排序问题与多目标排序问题; 按参数的性质，可以划分为确定型排序问题与随机型排序问题。,第一节 排序的基本概念,第一节 排序的基本概念,三、假设条件与符号说明 （一）排序问题的假设条件 一个工件不能同时在几台不同的机器上加工； 工件在加工过程中采取平行移动方式； 不允许中断； 每道工序只在一台机器上完成； 工件数、机器数和加工时间已知，加工时间与加工顺序无关； 每台机器同时只能加工一个工件。,第一节 排序的基本概念,三、假设条件与符号说明 （二）有关符号说明,四、排序问题的一般表示方法 4参数法：n/m/A/B 其中：n 工件数； m机器数； A工作车间类型； B目标函数，通常是使其最小 若A处为F代替，则表示流水作业排序问题； 若A处为P代替，则表示流水作业排列排序问题，即每个工件在各台机器上的加工顺序都相同； 若m为1时，A为空白，即单台机器的排序，对于单台机器排序问题，无所谓加工路线问题。,第一节 排序的基本概念,第二节 流水作业排序问题,流水作业排序问题的基本特征是每个工件的加工线路都一致。 加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。 本节要讨论的是所有工件在各台机器上的加工顺序相同的情况，就是排列排序问题n/m/P/B。,第二节 流水作业排序问题,一、最长流程时间Fmax的计算,P263例11.1 有一个6/4/P/Fmax问题，其加工时间如表，当按顺序 S=(6，1，5，2，4，3)加工时，求 Fmax。,表11-1 加工时间矩阵,表11-2 顺序下的加工时间矩阵,P263例11.1 有一个6/4/P/Fmax问题，其加工时间如表，当按顺序 S=(6，1，5，2，4，3)加工时，求 Fmax。,表11-1 加工时间矩阵,对于第1行第1列，只需把加工时间的数值作为完工时间标在加工时间的右上角;对于第1行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。 对于从第2行到第m行，只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右上角； 从第2列到第n列，则要从本行前一列右上角和本列上一行的右上角数字中取较大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为Fmax。,Fmax的标注完工时间的规则,第二节 流水作业排序问题,二、n / 2 / F / Fmax 问题的最优算法,对于n个工件1台机器的排序问题，既适用于流程作业,也适用于单件作业，在第三节单件作业排序讨论。 对于n / 2 / F / Fmax 问题，S.M.Johson于1954年给出了有效的算法，即著名的Johson算法。其目标是使从第一个工件开始到最后一个工件结束的总流程时间最短。,Johnson算法的步骤： 列出所有工件在两台机器上的加工时间矩阵； 从加工时间矩阵中找出最短的加工时间； 若最短的加工时间出现在M1上，则对应的工件往前排；如果最短的加工时间出现在M2上，则对应的工件往后排；然后，划去已经排序的工件。若最短的加工时间有多个，则任选一个； 当所有的工件都已排序，停止计算，转步骤。,二、n / 2 / F / Fmax 问题的最优算法,P264例11.2 按Johnson法求下表所示的6/2/F/Fmax问题的最优解。,表11-3 加工时间矩阵,最优加工顺序为S=（2，5，6，1，4，3） 最优顺序下的Fmax=28,Johnson算法的变形,步骤： 将所有aibi的工件按照ai值不减（递升）的顺序排列成一个序列A； 将所有aibi的工件按bi值不增（递减）的顺序排列成一个序列B； 将A放到B之前，就构成了最优加工顺序。,P264例11.2 Johnson算法的变形 求下表所示的6/2/F/Fmax问题的最优解。,表11-3 加工时间矩阵,序列A为（2,5,6,1），序列B为（4,3）， 则最优序列为S=（2,5,6,1,4,3）， 与Johnson算法的结果一致。,n / m / P / Fmax问题的启发式算法,启发式算法（试探法）是一种能在可接受的费用内寻找最好的解的技术，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度 。 启发式算法是解决NP问题（不确定性问题）的重要方法，由于其计算量都比较大，所以随着计算机技术的发展，启发式算法取得了巨大的成就。 常见的启发式算法有贪婪法、局部搜索法、退火算法、蚁群算法等。,经典算法与启发式算法,驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后往山上开4.5公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路714 号。 用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。,1965年，DSPalmer提出按斜度指标排列工件的启发式算法，这种算法称之为Palmer算法。 其中工件斜度指标可按下式计算：,算出i后，按i不增（递减）的顺序排列工件，可得出较满意的加工顺序。,三、一般n / m / P / Fmax问题的启发式算法,（一）Palmer（帕默） 算法,（一）Palmer 算法,P266例11.3 有一个4/3/F/Fmax问题，用Palmer算法求解最优加工顺序。加工时间矩阵为：,三、一般n / m / P / Fmax问题的启发式算法,解：,按照 不增的顺序， 得到最优加工顺序 (1,2,3,4)和(2,1,3,4),（二）关键工件法,步骤如下： 1. 计算每个工件的总加工时间Pi=pij，找出加工时间最长的工件C（j=m），将其作为关键工件。 2. 对于余下的工件，若Pi1Pim，则按Pi1不减的顺序排列一个序列Sa；若Pi1Pim，则按Pim不增的顺序排成一个序列Sb。 3. 加工顺序（Sa，C，Sb）即为所求近优解。 例11.3,三、一般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/2/F/Fmax问题的最优算法（ Johson算法）,11.3 单件作业排序问题 一、问题的描述,特点：每个工件都有其独特的加工路线，工件没有固定的流向 问题的描述：描述一道工序，要用3个参数(i,j,k)，表示工件 i 的第 j 道工序在机器 k 上进行。 可以用加工描述矩阵来描述所有工件的加工,11.3 单件作业排序问题 一、问题的描述,可以用加工描述矩阵来描述所有工件的加工 例如，一个2/3/G/Fmax问题：,工序1,工序2,工序3,工件1,工件2,二、三种作业计划,半能动作业计划（Semi-active schedule） 各工序都按最早可能开（完）工时间安排的作业计划 能动作业计划（Active schedule） 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划 无延迟作业计划（Non-delay schedu1e） 没有任何延迟出现的能动作业计划 “延迟”：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序,能动作业计划与无延迟作业计划的生成,符号说明 将每安排一道工序称作一“步”，设： St第t 步之前已排序工序构成的部分作业计划 Ot第t 步可以排序的工序的集合 TkOt中Ok的最早可能开工时间 TkOt中Ok的最早可能完工时间,P269 例11.4 有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T已知，求一个能动作业计划。,三、三类启发式算法,优先调度法则 随机抽样法 概率调度法,1.优先调度法则,SPT（Shortest processing time）法则 优先选择加工时间最短的工序 可使工件的平均流程时间最短，从而减少在制品量 FCFS（First come first served）法则 优先选择最早进入可排工序集合的工件 来自排队论，对工件较公平 EDD（Earliest due date）法则 优先选择完工期限紧的工件 可使工件最大延误时间最小 MWKR（Most work remaining）法则 优先选择余下加工时间最长的工件 不同工作量的工件的完工时间尽量接近,1.优先调度法则（续）,LWKR（Least work remaining）法则 优先选择余下加工时间最短的工件 使工作量小的工件尽快完成 MOPNR（Most operations remaining）法则 优先选择余下工序数最多的工件 与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的 SCR（Smallest critical ratio）法则 优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比） 保证工件延误最少 RANDOM法则 随机地挑一个工件,2.随机抽样法,随机抽样法 实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划 这种方法不一定能得到最优作业计划，但可以得到较满意的作业计划 效果与样本大小有关。样本越大，获取较好解的可能性越大 从无延迟作业计划母体中抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好,3. 概率调度法,给不同的工序按某一优先调度法则分配不同的挑选概率，可以得到多个作业计划供比较。 例如，在构成无延迟作业计划的第（3）步 有3道工序，A、B和C可挑选 3道工序所需的时间分别为3，4和7 将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率 比如A、B和C的挑选概率分别为6/14、5/14和3/14 既保证了SPT法则起作用，又可产生多个作业计划供挑选,生产作业控制是指在生产过程中，按既定的政策、目标、计划和标准，通过监督和检查生产活动的进展情况、实际成效，及时发现偏差，找出原因，采取措施，以保证目标、计划的实现。 生产运作控制的受控客体是生产运作过程，其预定目标是主生产计划与生产作业计划的目标值。,11.4 生产作业控制,一、生产活动与作业计划产生偏差的原因 （1）加工时间估计不准确 （2）随机因素的影响 （3）加工路线的多样性 （4）企业环境的动态性,11.4 生产作业控制,二、生产作业控制的程序 制定生产作业监控体系 监控实际生产过程 评估偏差情况 采取纠偏措施,11.4 生产作业控制,三、生产作业控制的主要工具,实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括： 调度单 日报、月报 例外报告、异常报告 输入/输出（I/O）报告,漏斗模型,德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。,漏斗模型,漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。,注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔。,控制规则,在一段较