制造业作业生产计划.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十一章 制造业作业计划与控制,11.1,排序问题的基本概念,11.2,流水作业排序问题,11.3,单件作业排序问题,11.4,生产作业控制,第一节 排序的基本概念,一、相关名词术语,排序：,确定工件在机器上的加工顺序。,编制作业计划：,不仅包括确定工件的加工顺序,，还,包括确定机器加工每个工件的开始时间和完成时间。我们习惯上不加区别地使用作业排序与作业计划。,派工：,按照作业计划的要求，将具体的生产任务安排到具体的机床上加工。,赶工：,当实际进度落后于计划进度时采取的行动。,加工线路：,工件按照工艺过程进行加工的过程，一般用,M,1,M,2,M,3,M,4,来表示。,加工顺序：,表示每台机器加工,n,个工件的先后顺序，是排序要解决的问题。,二、排序问题的分类,按机器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题,;,按加工路线的特征，可分为,单件作业排序问题和流水作业排序问题,;,按工件到达工作中心（或车间）的情况不同可分为,静态的排序问题,（当进行排序时，所有工件都已到达，或准备就绪）,和,动态的排序问题,（工件的到达是陆续的，要随时安排它们的加工顺序）,;,第一节 排序的基本概念,二、排序问题的分类,按目标函数不同，可分为流程最短问题与误工最少问题等；,按目标函数的性质不同分为单目标排序问题与多目标排序问题,;,按参数的性质，可以划分为确定型排序问题与随机型排序问题。,第一节 排序的基本概念,第一节 排序的基本概念,三、假设条件与符号说明,（一）排序问题的假设条件,一个工件不能同时在几台不同的机器上加工；,工件在加工过程中采取,平行,移动方式；,不允许中断；,每道工序只在一台机器上完成；,工件数、机器数和加工时间已知，加工时间与加工顺序无关；,每台机器同时只能加工一个工件。,第二节 流水作业排序问题,流水作业排序问题的基本特征是,每个工件的加工线路都一致,。,加工线路一致，是指工件的,流向一致,，并不是指每个工件必须经过加工线路上的每台机器加工。,本节要讨论的是所有工件在各台机器上的加工顺序相同的情况，就是,排列排序,问题,n/m/P/B,。,第二节 流水作业排序问题,一、最长流程时间,F,max,的计算,P263,例,11.1,有一个,6/4/P/Fmax,问题，其加工时间如表，当按顺序,S=(6,，,1,，,5,，,2,，,4,，,3),加工时，求,F,max,。,表,11-1,加工时间矩阵,i,1,2,3,4,5,6,P,i1,4,2,3,1,4,2,P,i2,4,5,6,7,4,5,P,i3,5,8,7,5,5,5,P,i4,4,2,4,3,3,1,表,11-2,顺序下的加工时间矩阵,P263,例,11.1,有一个,6/4/P/Fmax,问题，其加工时间如表，当按顺序,S=(6,，,1,，,5,，,2,，,4,，,3),加工时，求,F,max,。,表,11-1,加工时间矩阵,i,1,2,3,4,5,6,P,i1,4,2,3,1,4,2,P,i2,4,5,6,7,4,5,P,i3,5,8,7,5,5,5,P,i4,4,2,4,3,3,1,i,6,1,5,2,4,3,P,i1,2,2,4,6,4,10,2,12,1,13,3,16,P,i2,5,7,4,11,4,15,5,20,7,27,6,33,P,i3,5,12,5,17,5,22,8,30,5,35,7,42,P,i4,1,13,4,21,3,25,2,32,3,38,4,46,对于,第,1,行第,1,列,，只需把加工时间的数值作为完工时间标在加工时间的右上角,;,对于第,1,行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。,对于从第,2,行到第,m,行，只要把,上一行右上角,的数字和本行的加工时间相加，将结果填在加工时间的右上角；,从第,2,列到第,n,列，则要从本行前一列右上角和本列上一行的右上角数字中,取较大者,，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为,F,max,。,F,max,的标注完工时间的规则,第二节 流水作业排序问题,二、,n/2/F/F,max,问题的最优算法,对于,n,个工件,1,台机器的排序问题，既适用于流程作业,也适用于单件作业，在第三节单件作业排序讨论。,对于,n/2/F/Fmax,问题，,S.M.Johson,于,1954,年给出了有效的算法，即著名的,Johson,算法。其目标是使从第一个工件开始到最后一个工件结束的,总流程时间最短。,Johnson,算法的步骤：,列出所有工件在两台机器上的加工时间矩阵；,从加工时间矩阵中找出,最短,的加工时间；,若最短的加工时间出现在,M,1,上，则对应的工件,往前排,；如果最短的加工时间出现在,M,2,上，则对应的工件,往后排,；然后，,划去已经排序的工件,。若最短的加工时间有多个，则任选一个；,当所有的工件都已排序，停止计算，转步骤,。,二、,n/2/F/F,max,问题的最优算法,P264,例,11.2,按,Johnson,法求下表所示的,6/2/F/F,max,问题的最优解。,i,1,2,3,4,5,6,a,i,5,1,8,5,3,4,b,i,7,2,2,4,7,4,表,11-3,加工时间矩阵,最优加工顺序为,S=,（,2,，,5,，,6,，,1,，,4,，,3,）,最优顺序下的,F,max,=28,Johnson,算法的变形,步骤：,将所有a,i,b,i,的工件按照ai,值,不减,（递升）,的顺序排列成一个序列,A；,将所有a,i,b,i,的工件按bi,值,不增（递减）,的顺序排列成一个序列,B；,将A放到B之前，就构成了最优加工顺序。,P264,例,11.2 Johnson,算法的变形,求下表所示的,6/2/F/F,max,问题的最优解。,i,1,2,3,4,5,6,a,i,5,1,8,5,3,4,b,i,7,2,2,4,7,4,表,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,问题的启发式算法,i,1,2,3,4,P,i1,1,2,6,3,P,i1,8,4,2,9,P,i1,4,5,8,2,i,1,2,3,4,P,i1,1,2,6,3,P,i1,8,4,2,9,P,i1,4,5,8,2,解：,按照 不增的顺序，,得到最优加工顺序,(1,2,3,4),和,(2,1,3,4),（二）关键工件法,步骤如下：,1.,计算每个工件的总加工时间,P,i,=,p,ij,，找出加工时间最长的工件,C,（,j=m,），将其作为,关键工件,。,2.,对于余下的工件，若,P,i1,P,im,，则按,P,i1,不减,的顺序排列一个序列,S,a,；若,P,i1,P,im,，则按,P,im,不增的顺序排成一个序列,S,b,。,3.,加工顺序（,S,a,，,C,，,S,b,）即为所求近优解。,例,11.3,i,1,2,3,4,P,i1,1,2,6,3,P,i1,8,4,2,9,P,i1,4,5,8,2,三、一般,n/m/P/Fmax,问题的启发式算法,（三）,CDS,算法,Campbell,，,Dudek,，,Smith,三人提出了一个启发式算法，简称,CDS,算法。他们把,Johnson,算法用于一般,n/m/P/F,max,问题，得到（,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/F,max,问题：,工序,1,工序,2,工序,3,工件,1,工件,2,二、三种作业计划,半能动作业计划（,Semi-active schedule,）,各工序都按最早可能开（完）工时间安排的作业计划,能动作业计划（,Active schedule,）,任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划,无延迟作业计划（,Non-delay schedu1e,）,没有任何延迟出现的能动作业计划,“延迟”：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序,能动作业计划与无延迟作业计划的生成,符号说明,将每安排一道工序称作一“步”，设：,S,t,第,t,步之前已排序工序构成的部分作业计划,O,t,第,t,步可以排序的工序的集合,T,k,O,t,中,O,k,的最早可能,开工,时间,T,k,O,t,中,O,k,的最早可能,完工,时间,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）。,漏斗模型,漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。,注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔。,控制规则,在一段较长的时间内,(,如数周,),内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率,(,平均生产率,),等于平均在制品库存,/,平均通过时间。,实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：,若希望保持在制品库存量，可暂时增加或减少输入。,若希望改变在制品库存量，可暂时增加或减少输入。,若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。,要使各个工件的平均通过时间稳定，可以采用,FIFO,规则来安排各工件的加工顺序。,本章小结,11.1,排序问题的基本概念,11.2,流水作业排序问题,11.3,单件作业排序问题,11.4,生产作业控制,