第4讲-制造业作业计划与控制.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,生产运作管理,Production&Operations Management,青岛理工大学（临沂）,冯海侠,2016,年,5,月,2,第,4,章 制造业作业计划与控制,Scheduling and Controlling for Manufacturing,4.1,作业计划问题的基本概念,4.2,流水车间作业计划问题,4.3,单件车间作业计划问题,4.4,生产作业控制,3,4.1,作业计划问题的基本概念,4.1.1,生产作业计划概述,4.1.2,有关的名词术语,4.1.3,假设条件与符号说明,4.1.4,排序问题的分类和表示法,4,4.1.1,生产作业计划概述,生产作业计划是企业年度生产计划和,MRP,输出的具体执行计划。它根据年度生产计划的要求对每个生产单位（车间、工段、班组），在每个具体的时期（月、旬、周、日、轮班、小时等）内的生产任务作出详细的安排并规定实现的方法，从而保证企业按数量、品种、质量、交货期的要求全面完成生产计划。,5,生产作业计划的内容,生产作业计划的主要任务是将主生产计划或,MRP,中零部件的投入出产计划细化，他是,MRP,的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。,6,生产作业计划工作由,作业计划编制,与,作业计划控制,两部分组成。,作业计划编制：包括制定期量标准、开展生产运作能力核算与平衡、编制各种形式的生产作业计划等。,作业计划控制包括生产运作调度、生产运作作业统计与分析等内容。,7,生产作业计划的作用,保证主生产计划规定的生产运作任务的完成。,保证企业获取更好的经济效益。,8,4.1.2,有关的名词术语,排序：,就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力分配给不同工作任务，使预定目标最优化的问题。,派工,：,在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人。,赶工,：是在实际进度已经落后于计划进度时采取的行动。,调度,：,是作业计划编制以后，实行生产控制的一切行动。,9,4.1.2,有关的名词术语（续）,“,机器,”,，表示,“,服务者,”,.,可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。,“,零件,”,代表,“,服务对象,”,。零件可以是单个零件，也可以是一批相同的零件,“,加工路线,”,是零件加工的工艺过程决定的，它是零件加工在技术上的约束,“,加工顺序,”,则表示每台机器加工,n,个零件的先后顺序，是排序和编制作业计划要解决的问题,10,4.1.3,假设条件与符号说明,假设条件,一个零件不能同时在几台不同的机器上加工。,零件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。,不允许中断。当一个零件一旦开始加工，必须一直进行到完工，不得中途停止插入其它零件。,每道工序只在一台机器上完成。,零件数、机器数和加工时间已知。,每台机器同时只能加工一个零件。,11,4.1.3,假设条件与符号说明（续）,J,i,零件,i,，,i,1,2,n,。,M,j,机器,j,，,j,1,2,m,。,p,ij,一,J,i,在,M,j,上的加工时间，,J,i,的总加工时间为,P,i,p,ij,r,i,一,J,i,的到达时间，指,J,i,从外部进入车间，可以开始加工的最早时间。,d,i,一,J,i,的完工期限。,C,i,一,J,i,的完工时间,C,i,r,i,(w,ij+,p,ij,)=,r,i+,W,i,+P,i,.,C,max,最长完工时间,C,max,max C,i,.,12,F,i,一,J,i,的流程时间，即零件在车间的实际停留时间,F,i,C,i,-r,i,W,i,+P,i,.,F,max,最长流程时间，,F,max,max F,i,.,L,i,零件的延迟时间,L,i,=C,i,-d,i,当,L,i,0(,正延迟,),，说明,J,i,的实际完工时间超过了完工期限；当,L,i,0(,负延迟,),，说明,J,i,提前完工；当,L,i,0(,零延迟,),，,J,i,按期完工。,L,max,最长延迟时间，,L,max,max L,i,.,4.1.3,假设条件与符号说明（续）,13,4.1.4,排序问题的分类和表示法,按机器,单机排序问题和多机排序问题,多机：单件作业排序与流水作业排序,按工件到达情况,静态和动态,按目标函数,单目标排序问题和多目标排序问题,14,按参数的性质,确定型排序问题,（加工时间和其他有关参数是已知的确定量）,随机型排序问题,（加工时间和有关参数为随机变量）,四参数表示法（康韦（,Conway,）：,n/m/A/B,其中，,n,为零件数，,m,为机器数，,A,为车间类型，若标以,F,，则代表流水作业排序问题，若标以,P,，则代表流水作业排列排序问题，若标以,G,，则表示一般单件作业排序问题。,B,为目标函数，通常是使其值最小。,例如：,n/3/P/C,max,表示,n,个零件经,3,台机器加工的流水作业排列排序问题，目标函数是使最长完工时间,C,max,最短,。,15,4.2,流水作业排序问题,流水车间,(Flow shop):,工件的加工路线都一致，典型的如流水线,4.2.1,加工周期的计算,4.2.2,两台机器排序问题的最优算法,4.2.3,一般,n/m/p/F,max,排序问题的启发式算法,4.2.4,相同零件、不同移动方式下加工周期,Work,Center#1,Work Center,#2,Output,16,n,个不同的零件要按相同的加工路线经过,m,台机器加工，目标是使这批零件的加工周期最短,-n/m/P/F,max,加工周期,又称为最长流程时间，它是从第一个零件在第一台机器开始加工时起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。,假设所有零件的到达时间都为零,（,r,i,=0,i=1,2,n),，则,F,max,等于排在末位加工的零件在车间的停留时间，也等于一批零件的最长完工时间,C,max,4.2.1,加工周期的计算,17,设,n,个零件的加工顺序为,S=,（,S,1,，,S,2,，,S,n,），其中,S,i,为排第,i,位加工的零件的代号。以,C,kSi,表示零件,S,i,在机器,M,k,上的完工时间，,P,Si,k,表示零件,S,i,在,M,k,上的加工时间，,k=1,2,m;i=1,2,n,则,C,kSi,可按以下公式计算,C,1Si,=,C,1Si-1,+,P,Si,1,C,kSi,=max C,(k-1)Si,C,kSi-1,+,P,Si,k,k=2,3,m;i=1,2,n,C,mSn,即为最长流程时间,F,max,18,4.2.1,加工周期的计算,工件代号,i,1 2 3 4 5 6,P,i1,4 6 4 5 8 3,P,i2,3 5 3 9 7 1,P,i3,7 9 2 6 5 8,P,i4,5 4 9 6 2 3,有一个,6/4/P/F,max,问题，其加工时间如下表所示。当按顺序,S=,（,1,4,6,3,5,2,）加工时，求,F,max,19,4.2.1,加工周期的计算,工件代号,i,1 4 6 3 5 2,P,i1,4 5 3 4 8 6,P,i2,3 9 1 3 7 5,P,i3,7 6 8 2 5 9,P,i4,5 6 3 9 2 4,4 9 12 16 24 30,7 18 19 22 31 36,14 24 32 34 39 48,19 30 35 44 46 52,20,对于,n,个零件经过两台机器加工，要使加工周期最短的流水作业排序问题，即,n/2/F/F,max,问题，,约翰逊于,1954,年提出了一个最优算法，即著名的,Johnson,算法。,为叙述方便，以,a,i,表示零件,J,i,在机器,M,1,上的加工时间，以,b,i,表示零件,J,i,在机器,M,2,上的加工时间，每个零件都按,M,1,M,2,的,路线加工。,4.2.2,两台机器排序问题的最优算法,21,4.2.2,两台机器排序问题的最优算法,约翰逊法则,如果,Min(a,i,b,j,)p,im,则按,p,im,不增的顺序排成一个序列,S,b;,3.,顺序（,S,a,C,S,b,）即为所求顺序。,28,4.2.3,多台机器排序问题的 启发式算法（续）举例,工件,i 1 2 3 4,P,i1,2 1 6 3,P,i2,4 8 2 9,P,i3,5 4 8 2,11 13 16 14,C,S,a,(2,1),S,b,(4),所求顺序：,（,2,1,3,4,）,29,Palmer,（帕尔默）法,1965,年，帕尔默（,D.S.,Palmer),对流水作业排序问题提出了按斜度指标排列工件的启发式算法，该算法先定义工件的斜度指标，然后将各工件按其斜度指标不增进行排序。零件的斜度指标可按下式计算：,式中，,m,为机器数，,P,ik,为零件,i,在机器,M,k,上的加工时间。,按照各零件 不增的顺序排列零件，可得出令人满意的加工顺序。,30,例,3,：有一个,4/3/F/F,max,问题，其加工时间如下表所示，试用,Palmer,法求解。,工件,i 1 2 3 4,P,i1,1 2 6 3,P,i2,8 4 2 9,P,i3,4 5 8 2,31,CDS,法,坎贝尔（,Campbell,）、杜德克（,Dudek,）、史密斯（,Smith,）三人提出了一个启发式算法，简称,CDS,法。他们把,Johnson,算法用于一般的,n/m/F/F,max,问题，得到（,m-1,）个加工顺序，取其中的优者。,具体的做法是：对加工时间,注：当,取不同值，对每一组值，看成是分别在两个机器上的加工时间。,32,4.3,单件车间作业计划问题,4.3.1,任务分配问题,4.3.2,排序问题的描述,4.3.3,两种作业计划的构成,4.3.4,求解一般,n/m/G/F,max,问题的启发式方法,33,4.3.1,任务分配问题,把,n,项任务分给,n,台机器加工，有,n!,方案,匈牙利算法,(1),从加工时间,(,费用,),矩阵每一行所有元素减去该行最小的元素，使每行至少出现一个零元素。,(2),从实施第,(1),步得到的矩阵中的每一列所有元素减去该列最小的元素，使每列至少出现一个零元素。,(3),从实施第,(2),步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，如果线条数等于矩阵的行数，则已找到最优矩阵，转第,(6),步；否则，转第,(4),步。,(4),从矩阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个最小数加到直线交叉的元素上，其余元素不变。,(5),重复步骤,(3),和步骤,(4),，直到获得最优矩阵。,（,6,）从仅有一个零的行或列开始，找出零元素对应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素。零元素对应的就是最优分配方案。,例,4-3-1,有如下任务分配问题,:,34,求解过程如下表所示：,35,36,e,零件,1,由机器,M3,加工，零件,2,由机器,M2,加工，零件,3,由机器,M4,加工，零件,4,由机器,M1,加工，可使总加工时间最少。,37,38,对于一般单件作业排序问题，要描述一道工序，要用三个参数：,i,j,和,k,。,i,表示工件的代号，,j,表示工序，,k,表示完成工件,i,的第,j,道工序的机器的代号。用（,i,j,k,）表示工件,i,的第,j,道工序是在机器,k,上进行加工的。于是可以用加工描述矩阵的形式来描述所有工件的加工。,4.3.2,单件作业排序问题的描述,39,4.3.2,单件作业排序问题的描述,D,=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,T,=,2 4 1,3 4 5,加工描述矩阵,D,和加工时间矩阵,T,对应,40,两种作业计划的构成,半能动作业计划：,各工序都按最早可能开（完）工时间安排的作业计划；,能动作业计划,：,任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划；,无延迟作业计划,：,没有任何延迟出现的能动作业计划。,延迟：,指有工件等待加工时，机器出现空闲，既使这段空闲时间不足以完成一道工序。,4.3.3,一般,n/m/G/F,max,问题的启发式算法,41,4.3.3,两种作业计划的构成（续）,符号说明,每安排一道工序称为一,“,步,”,S,t,:t,步之前已排序工序构成的部分作业计划；,O,t,:t,步可排序工序的集合；,T,k,为,O,t,中工序,O,k,的最早可能开始时间；,T,k,为,O,t,中工序,O,k,的最早可能完成时间。,42,4.3.3,两种作业计划的构成（续）,能动作业计划的构成步骤,（,1,）设,t=1,S,1,为空集，,O,1,为各工件第一道工序的集合。,（,2,）求,T,*,=minT,k,并求出,T,*,所出现的机器,M,*,。,如果,M,*,有多台，则任选一台。,（,3,）,从,O,t,中选出满足以下两个条件的工序,O,j,：需要,M,*,加工，且,T,j,T,*,。,（,4,）,将选定的工序,O,j,放入,S,t,从,O,t,中消去,O,j,并将,O,j,的紧后工序放入,O,t,，使,t=t+1.,（,5,）若还有未安排的工序，转步骤（,2,）；否则，停止。,43,能动作业计划的构成,t,O,t,T,k,T,k,T*,M*,O,j,1,1,1,1,2,1,3,0,0,2,3,2,M,1,1,1,1,2,1,2,3,2,1,3,2,0,6,3,3,M,3,2,1,3,3,1,2,3,2,2,1,3,3,7,7,7,M,3,M,1,1,2,3,4,1,3,2,2,2,1,7,3,8,7,7,M,1,2,2,1,5,1,3,2,2,3,2,7,7,8,12,8,M,2,1,3,2,6,2,3,2,8,13,13,M,2,2,3,2,44,能动作业计划的甘特图,2,3,2,1,1,1 2,2,1,1,3,2,2,1,3 1,2,3,3 7,7 8 13,2 3 7,0,时间,机器,M,1,M,2,M,3,45,4.3.3,两种作业计划的构成（续）,无延迟作业计划的构成,（,1,）设,t=1,S,1,为空集，,O,1,为各工件第一道工序的集合。,（,2,）求,T,*,=min,T,k,并求出,T,*,所出现的机器,M,*,。,如果,M,*,有多台，则任选一台。,（,3,）,从,O,t,中选出满足以下两个条件的工序,O,j,：需要,M,*,加工，且,T,j,=,T,*,。,（,4,）,将选定的工序,O,j,放入,S,t,从,O,t,中消去,O,j,并将,O,j,的紧后工序放入,O,t,，使,t=t+1.,（,5,）若还有未安排的工序，转步骤（,2,）；否则，停止。,46,无延迟作业计划的构成,t,O,t,T,k,T,k,T*,M*,O,j,1,1,1,1,2,1,3,0,0,2,3,0,0,M,1,M,3,1,1,1,2,1,2,3,2,1,3,2,0,6,3,0,M,3,2,1,3,3,1,2,3,2,2,1,3,3,7,7,3,3,M,3,M,1,1,2,3,4,1,3,2,2,2,1,7,3,8,7,3,M,1,2,2,1,5,1,3,2,2,3,2,7,7,8,12,7,7,M,2,M,2,2,3,2,6,1,3,2,12,13,12,M,2,1,3,2,47,无延迟作业计划的甘特图,2,3,2,1,1,1 2,2,1,2,1,3 1,2,3,3 7,7 12,2 3 7,0,时间,机器,M,1,M,2,M,3,1,3,2,48,4.3.4,三类启发式算法,（,1,）优先调度法则,构成两种作业计划的第（,3,）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划,更能符合计划编制者的要求,计算量小,已经提出,100,多种优先调度法则,49,优先调度法则,FCFS,（,first come,first served,）优先选择最早进入可排序集合的工序,SPT,(shortest processing time,）优先选择加工时间最短的工序,EDD,（,earliest due date,）优先选择完工期限紧的工序,SCR,(smallest critical ratio),选择临界比最小的工件（,临界比：工件允许停留时间与工件余下加工时间之比,）,MWKR,(most work remaining),优先选择余下加工时间最长的工件,LWKR,(least work remaining),优先选择余下加工时间最短的工件,MOPNR,(most operations remaining),优先选择余下工序数最多的工件,50,按,SPT,法则，可使工件的平均流程时间最短，从而减少在制品库存量；,FCFS,法则来自排队论，它对工件较公平；,EDD,法则可使工件最大延误时间最小；,SCR,法则也是保证,工件延误最小的法则；,MWKR,与,MOPNR,法则类似使不同工作量的工件的完工时间尽量接近；,LWKR,法则使工作量小的工件尽快完成；,RANDOM,随机挑选一个工件,51,在应用优先调度法则时，只要将构成能动作业计划的第,3,步修改为：对,Ot,中需要,M,*,加工，且,Tj,T,*,的工序，按预定的优先调度法则确定一个进入,St,的工序。对于构成无延迟作业计划的,第,3,步修改为：对,Ot,中需要,M,*,加工，且,Tj,=,T,*,的工序，按预定的优先调度法则确定一个进入,St,的工序。,一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。,有时应用一个优先法则还不能惟一地确定一道应挑选的工序，需要多个优先调度法则的有序组合。譬如，,SPT+MWKR+RANDOM,52,4.3.3,三类启发式算法（续）,（,2,）随机抽样法,从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。,介于两个极端之间,效果与样本大小和母体有关,比用优先调度法则得到的结果一般要好一些，但计算量要大一些,从无延迟作业计划母体抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好,（,3,）概率调度法,将优先调度法则与随机抽样法结合,对不同工件按优先调度法则分配不同的挑选概率，效果较好,53,4.4,生产作业控制,4.4.1,实行生产作业控制的原因和条件,4.4.2,不同生产类型生产控制的特点,4.4.3,利用,“,漏斗模型,”,进行生产控制,54,4.4.1,实行生产作业控制的原因和条件,原因,加工时间估计不准确,随机因素的影响,加工路线的多样性,企业环境的动态性,条件,要有控制标准,取得实际进度偏离计划的信息,能够采取纠正行动,55,生产作业控制的程序,制定生产作业监控体系,监控实际生产过程,评估偏差情况,采取纠偏措施,56,生产作业控制的功能,为每个车间的工单指派优先级,维护车间在制品数量,将车间工单信息传送到相应办公室,提供实际产出数据来为能力控制服务,根据车间工单对机位的要求，为在制品库存管理提供数量信息,测量人员和设备的效率、利用率和产量。,57,4.4.2,不同生产类型生产控制的特点,特点,单件小批生产,大量大批生产,零件的流动,瓶颈,设备,调整准备费用,工人操作,工人工作的范围,工作节奏的控制,在制品库存,产品库存,供应商,作业计划编制,没有主要的流动路线,经常变动,通用设备，有柔性,低,多,宽,工人自己和工长,高,很少,经常变化,不确定性高，变化大,单一的流动路线,稳定,高效专用设备,高,少,窄,由机器和工艺过程,低,较高,稳定,不确定性低，变化小,不同生产类型的特点,58,4.4.2,不同生产类型生产控制的特点（续）,单件小批生产，,排队时间,是主要的，通过输入,/,输出控制排队队长,大量大批生产，控制问题较简单，主要是调整工作班次、工作时间和工人数量,移动 时间,排队 时间,调整准备时间,加工 时间,待运 时间,零件加工提前期的构成,59,生产作业控制的主要工具,实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：,调度单,日报、月报,例外报告、异常报告,输入,/,输出（,Input/output control,，,I/O,）报告,60,4.4.3,利用,“,漏斗模型,”,进行生产控制,德国汉诺威大学的贝克特（,Bechte,）和温道尔（,Wiendall,）等人于,20,世纪,80,年代初在实施输入,/,输出控制时提出了漏斗模型（,Funnel Model,）。,漏斗模型的基本原则：,工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。,61,在制品,到达的任务,计划能力,实际能力,完成的任务,62,注：曲线图的垂直段表示某天到达或完成的一个或多个工件之间所包含的工作量；水平段表示相邻两个到达或完成的任务之间的时间间隔。如果运输时间不变，输入曲线与上道工序的输出曲线相对应。,63,4.4.3,利用,“,漏斗模型,”,进行生产控制,(,续,),在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存,/,平均通过时间,实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：,若希望保持在制品库存稳定，就要使单位时间内的平均输入等于平均输出。,若希望改变在制品库存量，可暂时增加或减少输入。,若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。,要使各个工件的平均通过时间稳定，可以采用,FIFO,规则来安排各工件的加工顺序。,漏斗模型适合于多品种中小批量生产系统的控制。,64,本章习题：,思考题：,1,、作业计划解决什么问题？请举例说明。,2,、排序、编制作业计划、派工、赶工、调度、控制等术语的含义及其相互关系。,3,、解释加工路线和加工顺序。,4,、说明能动作业计划和无延迟作业计划的关系。,5,、漏斗模型的基本原理是什么？它在生产控制中的用途如何？,65,判断题：,1.,排序是指安排工件在机器上的加工顺序。,2.,按照,Johnson,法则可得到多个加工顺序，则应从中取最优者。,3.,派工属于通常所说的调度范围。,4,、流水车间排序问题是指所有工件的加工顺序都相同的排序问题。,5,、列车时刻表属于作业计划。,6,、,Johnson,算法应用于只存在一台机器或者一个加工工段的情形。,7,、,n/m/A/B,中,A,表示车间类型，,B,表示目标函数。,8,、确定加工路线是排序要解决的主要问题。,9,、排序与编制作业计划是同义词。,66,选择题,1,、下列哪项不是排序的优先调度法则？,A,优先选择余下加工时间最长的工件,B,优先选择加工时间最短的工件,C,优先选择临界比最小的工件,D,优先选择临界比最大的工件,67,2,、一个工件剩下,5,天加工时间，今天是这个月的,10,号。如果这个工件,14,号到期，临界比是多少？,A.0.2 B.4 C.1 D.0.8,3,、任务分配情况下，,5,个工件分派到,5,台机器上有多少种不同方法？,A.5 B.25 C.120 D.125,68,4.,下列哪项可将生产计划任务落实到操作工人身上？,A.,流程设计,B.,能力计划,C.,生产大纲,D.,排序和车间生产作业计划,5.,与流水车间排序不直接相关的是：,A.,加工描述矩阵,B.,加工时间矩阵,C.,加工顺序矩阵,D.,“,漏斗,”,模型,69,计算题,1.,有,5,件任务都需要两步操作（先,1,后,2,）来完成，下表给出了加工时间。,任务,操作,1,所需时间（小时）,操作,2,所需时间（小时）,A,B,C,D,E,3.0,2.0,1.0,3.0,3.5,1.2,2.5,1.6,3.0,1.5,根据,Johnson,算法安排工作顺序，并计算最短加工周期。,70,2,、有一个,4/4/P/F,max,问题，其加工时间如下表所示，用,Palmer,法求解。,i 1 2 3 4,P,i1,1 9 5 4,P,i2,5 7 6 3,P,i3,4 6 3 5,P,i4,6 2 3 7,3,、用关键工件法求解第,2,题的最优排序。,4,、用,CDS,启发式算法求解第,2,题的最优排序。,71,5,、有一个,2/3/G/F,max,问题，其加工描述矩阵,D,和加工时间矩阵,T,分别为：,试构成一个能动作业计划。,6,、求第,5,题中加工描述矩阵和加工时间矩阵构成的无延迟作业计划。,7,、求解第,5,题中加工描述矩阵和加工时间矩阵由,(1)FCFS,；,(2)SPT,法则决定的作业顺序。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,2 2,3,1,T=,3 5 2,2 4 3,