运营管理制造业作业计划与控制

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,流水作业排序问题,单件作业排序问题,重点,内容,排序问题的基本概念,流水作业排序问题,单件作业排序问题,生产作业控制,第,11,章 制造业作业计划与控制,生产作业计划的主要任务是将主生产计划或,MRP,中的零部件投入出产计划细化，是,MRP,的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。,生产作业计划的内容,作业计划与控制的关系,作业计划：,给生产活动制定详细时间表,生产控制：,以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标。,第一节 排序问题的基本概念,一、名词术语,生产管理,“,（编制）作业计划”（,Scheduling,）,“排序”（,Sequencing,）,“派工”（,Dispatching,）,“控制”（,Controlling,）,“赶工”（,Expediting,）,排序,工件在机器上的加工顺序,（编制）作业计划,工件的加工顺序,加工工件的开始时间,加工工件的完成时间,作业计划的主要问题是确定各台机器上工件的加工顺序,通常情况下都是按最早可能开（完）工时间来编排作业计划的,当工件的加工顺序确定之后，作业计划也就确定了,派工,赶工,属于“调度”范围,“,编制作业计划”加工制造发生之前的活动,“,调度”是在加工制造发生之后的活动，是发现实生产进度已经偏离预定计划而采取的调配资源的行动,调度的依据是作业计划,描述排序问题的术语,“,机器” “工件” “工序” “加工时间”,n,个工件经过,m,台机器加工,“,加工路线”,工件加工的工艺过程决定,一般用,M,1,，,M,2,，,来表示,“,加工顺序”,每台机器加工,n,个工件的先后顺序,排序问题的复杂性,确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。,例如，考虑,32,项任务（工件），有,32,！,2.6,10,35,种方案,假定计算机每秒钟可以检查,1 billion,个顺序,全部检验完毕需要,8.4,10,15,个世纪。,如果只有,16,个工件,同样按每秒钟可以检查,1 billion,个顺序计算,也需要,2/3,年。,以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。,所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,二、假设条件与符号说明,假设条件,l.,一个工件不能同时在几台不同的机器上加工,2.,工件在加工过程中采取平行移动方式,3.,不允许中断,4.,每道工序只在一台机器上完成,5.,工件数、机器数和加工时间已知，加工时间与加工顺序无关,6.,每台机器同时只能加工一个工件,符号,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,符号,F,i,J,i,的流程时间，即工件在车间的实际停留时间，,F,i,C,i,-,r,i,=W,i,+P,i,F,max,最长流程时间，,F,max,=,max,F,i,L,i,工件的延迟时间,W,ij,J,i,在,M,j,上加工之前的等待时间,W,i,J,i,在加工过程中总的等待时间,a,i,J,i,的允许停留时间,符号,L,i,=C,i,-,d,i,=,r,i,+P,i,+W,i,-,d,i,=(P,i,+W,i,)-(,d,i,-,r,i,)=F,i,-,a,i,当,L,i,0,（正延迟），说明,J,i,的实际完工时间超过了完工期限,当,L,i,0,（负延迟），说明,J,i,提前完工,当,L,i,=0,（零延迟），,J,i,按期,完工,L,max,最长延迟时间，,L,max,=max,L,i,三、排序问题的分类和表示法,分类方法,机器 工件 目标函数,机器,单台机器的排序问题,多台机器的排序问题,工件加工路线,单件作业（,Job-Shop,）排序问题,流水作业（,Flow-shop,）排序问题,单件车间排序问题的基本特征：,每个工件都有其独特的加工路线，工件没有一定的流向。,流水车间排序问题的基本特征：,每个工件的加工路线都一样。如车,铣,磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车,磨，有的为铣,磨。,不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为,排列排序（同顺序排序）,。如工件排序为：,J,1,J,3,J,2,，则表示所有机器都是先加工,J,1,，然后加工,J,3,，最后加工,J,2,。,静态的排序问题,动态的排序问题,单目标排序问题,多目标排序问题,确定型排序问题,随机型排序问题,Conway,表示方法,4,参数表示法,n,m,A,B,n,工件数,m,机器数,A,车间类型,F,代表流水作业排序问题,P,表示流水作业排列排序问题,G,表示一般单件作业排序问题,m,1 A,空白,B,目标函数,第二节 流水作业排序问题,基本特征,工件的加工路线都一致,工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工,对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致,流水作业排列排序问题,“,同顺序”排序问题,所有工件在各台机器上的加工顺序都相同,排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解,对于仅有,2,台和,3,台,机器的特殊情况，排列排序问题下的最优解一定是相应流水作业排序问题的最优解,一、最长流程时间,F,max,的计算,n,m,P,F,max,目标函数,最长流程时间最短,最长流程时间,加工周期,从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间,F,max,等于排在末位的工件在车间的停留时间，等于一批工件的最长完工时间,C,max,设,n,个工件的加工顺序为,S=,（,S,1,，,S,2,，,，,S,n,）,S,i,排第,i,位加工的工件,的代号,表示工件,S,i,在机器,M,k,上的完工时间,表示工件,S,i,在,M,k,上的加工时间,k,=1,，,2,，,，,m,i,=1,，,2,，,，,n,按以下公式计算,(11.1),k,=1,2,m,;,i,=1,2,n,当,r,i,=0,，,i,=1,2,n,时,F,max,=,例,11.1,有一个,6,4,P,F,max,问题，其加工时间如表,11,1,所示。当按顺序,S=(6,1,5,2,4,3),加工时，求,F,max,。,i,1,2,3,4,5,6,p,i,1,4,2,3,1,4,2,p,i,2,4,5,6,7,4,5,p,i,3,5,8,7,5,5,5,p,i,4,4,2,4,3,3,1,表,11-l,加工时间矩阵,i,6,1,5,2,4,3,p,i,1,2,2,4,6,4,10,2,12,1,13,3,16,p,i,2,5,7,4,11,4,15,5,20,7,27,6,33,p,i,3,5,12,5,17,5,22,8,30,5,35,7,42,p,i,4,1,13,4,21,3,25,2,32,3,38,4,46,表,11,2,顺序,S,下的加工时间矩阵,二、,n/2/F/ F,max,问题的最优算法,n,项任务在两台机器的排序问题,Scheduling n Jobs on Two Machines,n,个工件都必须经过机器,1,和机器,2,的加工，即工艺路线是一致的。,机器,1,到达系统工件的集合,离开系统（机器）,J,1,J,2,J,3,J,n,机器,2,两台机器排序问题的目标,两台机器排序的目标是使最大完成时间（总加工周期）,F,max,最短。,F,max,的含义见如下的甘特图,(Gantt Chart),。,多台机器排序的目标一般也是使最大完成时间（总加工周期）,F,max,最短。,F,max,时间,机器,A,B,在机器,A,上的作业时间,总加工周期,1954,年,Johnson,提出,用,a,i,表示,J,i,在,M,1,上的加工时间，用,b,i,表示,J,i,在,M,2,上的加工时间。每个工件都按,M,1,M,2,的路线加工。,Johnson,指出，若,min(,a,i,b,j,)=max B,i,or min C,i,= max B,i,定义：,A,i,= A,i,+ B,i, B,i,= B,i,+C,i,例,:,考虑以下问题,. 5,个工件由,3,台机器加工,作业时间见下表,.,求,:,总加工周期最短的作业顺序。,1 2 3 4 5,机器,A,4,4,9,13,8,21,6,27,5,32,机器,B,5,9,6,19,2,23,3,30,4,36,机器,C,8,17,10,29,6,35,7,42,11,53,解,:,检查上表,发现,:,min A,i,= 4,max B,i,= 6,min C,i,= 6,因此,满足以上条件,建立两台机器的作业时间表,:,1 2 3 4 5,机器,A,9 15 10 9 9,机器,B,13 16 8 10 15,1 4 5 2 3,机器,A,4,4,6,10,5,15,9,24,8,32,机器,B,5,9,3,13,4,19,6,30,2,34,机器,C,8,17,7,24,11,35,10,45,6,51,应用,Johnson,法则，得出：,总加工周期为：,三、,n,/,m,/P/F,max,问题的启发式算法,对于,3,台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法,对于一般的流水车间排列排序问题,分支定界法,启发式算法,求一般,n,m,P,F,max,问题近优解（,Near optimal solution,）的启发式算法,（一）,Palmer,法,按斜度指标排列工件的启发式算法,工件斜度指标,k,=1,2,n,m,为机器数；,p,ik,为工件,i,在,M,k,上的加工时间,按照各工件 不增的顺序排列工件，可得出令人满意的顺序,(11.4),例,11.3,有一个,4,3,F,F,max,问题，其加工时间如表,11,5,所示，用,Palmer,法求解,i,1,2,3,4,p,i1,1,2,6,3,p,i2,8,4,2,9,p,i3,4,5,8,2,表,115,加工时间矩阵,解：对于本例，式（,11,4,）变成,k,=1,2,3,=-,p,k1,+,p,k3,=-,p,11,+,p,13,=-1+4=3,=-,p,21,+,p,23,=-2+5=3,=-,p,31,+,p,33,=-6+8=2,=-,p,41,+,p,43,=-3+2=-1,按 不增的顺序排列工件，得到加工顺序,（,l,2,3,4,）和（,2,l,3,4,）,这两个顺序都是最优顺序,F,max,28,（二）关键工件法,步骤,（,1,）计算每个工件的总加工时间,P,i,=,p,ij,，找出加工时间最长的工件,C,（,j,=,m,），将其作为关键工件。,（,2,）对于余下的工件，若,p,i,1,p,im,，则按,p,i,1,不减的顺序排成一个序列,S,a,；若,p,i,1,p,im,，则按,p,im,不增的顺序排列成一个序列,S,b,。,（,3,）顺序（,S,a,，,C,，,S,b,）即为所求顺序。,i,1,2,3,4,p,i1,1,2,6,3,p,i2,8,4,2,9,p,i3,4,5,8,2,p,i,13,11,16,14,表,11-6,用关键工件法求解,总加工时间最长的为,3,号工件,（三）,CDS,法,把,Johnson,算法用于一般的,n,m,P,F,max,问题，得到（,m,-1,）个加工顺序，取其中优者。,具体做法,按,和,合并组成新的“机器”,l,=1,2,m,-1,合并,(,m,-1,),次，得到,(,m,-1),个,n,/2/F/F,max,问题,用,Johnson,算法求（,m,-1,）次加工顺序，取其中最好的结果,L,1,，按,Johnson,算法得到加工顺序,(1,，,2,，,3,，,4),，,F,max,28,L,2,，按,Johnson,算法得到加工顺序,(2,，,3,，,1,，,4),，,F,max,29,取顺序,(1,，,2,，,3,，,4,）为最优顺序。,四、相同零件不同移动方式下加工周期的计算,排序问题针对的是不同的零件，如果,n,个零件相同，则没有排序问题。,零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。,零件在加工过程中可以采用三种典型的移动方式：,顺序移动,平行移动,平行顺序移动,第三节 单件作业排序问题,每个工件都有其独特的加工路线，工件没有一定的流向,单件作业的排序问题是最一般的排序问题，也是最复杂的一种排序问题,R.w.Conway,作业计划理论,（,Theory of Scheduling,）,一、问题的描述,对于一般单件作业排序问题,描述一道工序，要用,3,个参数：,i,j,和,k,i,表示工件代号,j,表示工序号,k,表示完成工件,i,的第,j,道工序的机器的代号,用,（,i,j,k,）来表示工件,i,的第,j,道工序是在机器,k,上进行,的这样一件事,用加工描述矩阵描述所有工件的加工要求。,加工描述矩阵,D,加工描述矩阵,D,的每一行描述一个工件的加工,每一列的工序序号相同,行表示不同的工件；列表示不同的工序。,单件作业排序问题,(,n,/,m,/,G,/,F,max,),D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,T=,4 6 3,5 7 4,加工描述矩阵,D,：每一行描述一个工件的加工，每一列的工序序号相同。,加工时间矩阵,T,：与,D,相对应。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,单件作业排序问题,(,n,/,m,/,G,/,F,max,),加工顺序矩阵,S,：每一行与机器相对应，每一列与工件相对应。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,T=,4 6 3,5 7 4,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,单件作业排序问题,(,n,/,m,/,G,/,F,max,),用方块图表示：,二、一般,n,/,m,/G/F,max,问题的启发式算法,对于一般的,n,/,m,/G/F,max,排序问题,分支定界法或整数规划法,是无效算法,启发式算法是求解一般单件车间排序问题使用最多的方法,（一）两种作业计划的构成,半能动作业计划（,Semi-active schedule,）,各工序都按最早可能开（完）工时间安排的作业计划,能动作业计划（,Active schedule,）,任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业划,无延迟作业计划（,Non-delay schedule,）,没有任何延迟出现的能动作业计划,延迟,有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序,能动作业计划和无延迟作业计划的生成方法,将每安排一道工序称作一“步”,设,S,t,t,步之前已排序工序构成的部分作业计划,O,t,第,t,步可以排序的工序的集合,T,k,O,t,中工序,O,k,的最早可能开工时间,T,k,O,t,中工序,O,k,的最早可能完工时间,1.,能动作业计划的构成步骤,（,1,）设,t,=l,，,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,）；否则，停止,得到加工顺序矩阵,：,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,8,13,2.,无延迟作业计划的构成步骤,（,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,）若还有未安排的工序，转步骤；否则，停止,得到加工顺序矩阵,：,S=,1,1,1 2,2,1,2,3,2 1,3,2,2,1,3 1,2,3,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,12,13,（二）三类启发式算法,能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。,一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。,一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。,1.,优选调度法则,能动作业计划与无延迟作业什划的构成步骤时，其中第,（,3,）,步的两个条件一般都有多个工序可以满足。,按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响,优先调度法则,1.,优选调度法则,SPT(Shortest Processing Time),法则：优先选择加工时间最短的工序。,FCFS(First Come First Served),法则：优先选择最早进入可排工序集合的工件。,EDD(Earliest Due Date),法则：优先选择完工期限紧的工件。,MWKR(Most Work Remaining),法则：优先选择余下加工时间最长的工件。,LWKR(Least Work Remaining),法则：优先选择余下加工时间最短的工件。,MOPNR(Most Operations Remaining),法则：优先选择余下工序数最多的工件。,1.,优选调度法则,按,SPT,法则可使工件的平均流程时间最短，从而减少在制品量。,FCFS,法则来自排队论，它对工件较公平。,EDD,法则可使工件最大延误时间最小。,SCR,也是保证工件延误最少的法则。,MWKR,法则使不同工作量的工件的完工时间尽量接近。,LWKR,法则，使工作量小的工件尽快完成。,MOPNR,法则与,MWKR,法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的。,2.,随机抽样法,从全部能动作业计划或无延迟作业计划中抽样；然后在样本中选优,3.,概率调度法,对不同的工序按某一优先调度法则分配不同的调度概率，以改善对样本选择的效果,第五节 生产作业控制,