生产运作管理-制造业作业计划与控制.ppt

第十一章 制造业作业计划与控制,引言通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。,11.1 作业计划问题的基本概念11.2 流水作业排序问题11.3 单件作业的排序问题11.4 生产作业控制,11 收入、费用和利润,要求掌握：最长流程时间的计算2.约翰逊算法 3.一般流水作业排序问题的3种启发式算法4.相同零件的3种移动方式下机器加工周期的计算方法,学习目的与要求,重点 最长流程时间的计算 约翰逊算法 相同零件的3种移动方式下机器加工周期的计算方法 难点 一般流水作业排序问题的启发式算法,教学重点与难点,生产任务的最终落实,MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。将任务安排到工作地，牵涉到作业计划。,编制作业计划要解决的问题,由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间例如;医院要安排病人手术，为此要安排手术室，配备手术器械、手术医师和护士。,第一节 排序问题的基本概念,一、名词术语排序：确定工件在机器上的加工顺序。作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。赶工：实际进度已落后于计划进度时采取的行动。,“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题,二、假设条件和符号说明,假设条件：1.一个工件不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。4.每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件,有关符号,Ji：工件i，i=1，2，nMj：机器j，j=1，2，npij为Ji在Mj上的加工时间ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最早时间di为Ji的完工期限Ci为Ji的完工时间Cmax为最长完工时间Fi为Ji的流程时间，即工件在车间的实际停留时间Fmax为最长流程时间Li为工件的延迟时间Lmax为最长延迟时间,三、排序问题的分类,根据机器数的多少单台机器的排序问题多台机器的排序问题对于多台机器排序问题，根据加工路线的特征，分成单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。,根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序,4参数法,n/m/A/B其中，n为工件数m为机器数A车间类型。在A的位置若标以标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。当m=1，则A处为空白。B为目标函数，通常是使其值最小例如：n/3/P/Cmax,四、作业排序方案的评价标准,1.工作流程时间从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。2.加工周期完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。,3.在制品库存（WIP）在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。4.利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。,五、优先调度规则,调度方法：所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。,常用的优先顺序规则：,FCFS规则 优先选择最早进入可排序集合的工件。EDD规则 优先选择完工期限最紧的工作。SPT规则 优先选择加工时间最短的工件。SCR规则 优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。MWKR规则 优先选择余下加工时间最长的工件。LWKR规则 优先选择余下加工时间最短的工件。MOPNR规则 优先选择余下工序数最多的工件。RANDOM规则 随机地挑选下一个工件。,一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化,例 一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。,SPT规则排序结果,顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。,流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和加工周期平均总库存=各工件实际取货时间之和加工周期,EDD规则排序结果,顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。,比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。,优先调度法则,按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件延误时间最小。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。,第二节 流水作业排序问题,流水作业排序问题的基本特征是每个工件的加工路线都一致。加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。,一、最长流程时间Fmax的计算,n/m/P/Fmax问题，n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。,例 有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。,i,pi1,pi2,pi3,pi4,6,1,5,2,4,3,2,5,5,1,4,4,5,4,4,4,5,3,2,5,8,2,1,7,5,3,3,6,7,4,2,6,10,12,13,16,7,11,15,20,27,33,12,17,22,30,35,42,13,21,25,32,38,46,二、两台机器排序问题,两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤：（1）列出每个作业在两台机器上的加工时间。（2）选择最短的加工时间，如果有两个相同的值，则任选一个。（3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。,【例】求如表所示的6/2/F/Fmax问题的最优解。,将零件2排第1位 2将零件3排第6位 2 3将零件5排第2位 2 5 3将零件6排第3位 2 5 6 3将零件4排第5位 2 5 6 4 3将零件1排第4位 2 5 6 1 4 3,【例 题】,有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间：（1）根据Johnson算法安排工作顺序；（2）计算加工周期。,【例 题】,根据Johnson算法求以下8/2/F/Fmax问题的最优解。,1.将所有ai bi的工件按ai值不减的顺序排成一个序列A；2.将aibi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。,改进算法,练 习,某公司要生产4种产品，需要两台机器1和2。其中，有3种产品需要先在机器1上加工。下表给出了两台机器上加工各产品所需的时间。（1）安排生产顺序，使得在最短时间内完成生产。（2）机器1共需工作多长时间？（3）机器2应该在机器1开始工作后多长时间开始运转？,9.5,三、一般n/m/P/Fmax问题的启发式算法,启发式算法是一个基于直观或经验构造的算法，在可接受的花费(时间、占用空间等)下给出待解决组合优化问题的可行解。启发式方法因其易于实现、计算复杂度低等原因，目前应用得最为广泛。,（一）Palmer法,1965年，DSPalmer提出按斜度指标排列工件的启发式算法，称之为 Palmer法。工件的斜度指标可按下式计算：k=l，2，m 式中，m为机器数；pik为工件i在Mk上的加工时间。按照各工件i不增的顺序排列工件，可得出令人满意的顺序。,例 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用帕尔默法求最优顺序。,解：对于本例，i=Pi1Pi3于是，1=P11P13=14=3 2=P21P23=25=3 3=P31P33=68=2 4=P41P43=32=1 按i 不增的顺序排列工件，得到加工顺序(1，2，3，4)和(2，1，3，4)，恰好这两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下，F max=28。,（二）关键零件法,步骤如下：（1）计算每个零件的总加工时间，找出加工时间最长的零件C，将其作为关键零件。（2）对于余下的零件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。,例 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用关键零件法求最优顺序。解：总加工时间最长的为3号零件，pi1pi3的零件为1和2，按pi1不减的顺序排成Sa=（1，2）；pi1pi3的零件为4号零件，Sb=（4）,这样得到的加工顺序为（1，2，3，4）。,例 题,用关键工件法求解下表的最优排序。解：总加工时间最长的为2号零件，pi1pi4的零件为1和3，按pi1不减的顺序排成sa=（1，4）；pi1pi4的零件为4号零件，sb=（3），这样得到的顺序为（1，4，2，3）。,（三）CDS法,康坎贝尔-杜德克-史密斯三人提出了一个启发式算法，简称CDS法。具体做法是，对加工时间用Johnson算法求（m-1）次加工顺序，取其中最好的结果。,m=2时，l=1,加工时间分别为pi1和pi2；m=3时，l=1,2,加工时间分别为：（1）l=1，pi1和pi3（2）l=2,pi1+pi2和pi2+pi3m=4时，l=1，2，3，加工时间分别为：（1）l=1,pi1和pi4（2）l=2，pi1+pi2和pi3+pi4（3）l=3，pi1+pi2+pi3和pi2+pi3+pi4,l,A,加工时间,B,加工时间,1,t,1,t,m,2,t,1,+t,2,t,m-1,+t,m,3,t,1,+t,2,+t,3,t,m-2,+t,m-1,+t,m,m-1,t,1,+t,2,+,+t,m-1,t,2,+,+t,m-,1,+t,m,当l=1时，按（Johnson）算法得到加工顺序（1，2，3，4）；当l=2时，得到加工顺序（2，3，1，4）。对于（2，3，1，4），相应的Fmax=29。所以，取顺序（1，2，3，4）。,用Palmer法、关键工件法和CDS法求以下4/4/P/Fmax问题的最优解，并比较三种方法的结果。,四、相同零件、不同移动方式下加工周期的计算,排序问题针对的是不同零件，如果n个零件相同，则没有排序问题。但零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。三种典型的移动方式顺序移动方式(串行工程)平行移动方式（平行工程）平行顺序移动方式,（一）顺序移动方式,一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。,设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 ti（分钟/件），i=1.2n。则该批零件的加工周期为：,已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T顺=4（10+5+15+10）=160分钟,（二）平行移动方式,每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。,零件平行移动的加工周期 为：,已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平=（10+5+15+10）+（4-1）15=85分钟,（三）平行顺序移动方式,既要求每道工序连续进行加工，又要求各道工序尽可能平行地加工。,（1）当titi+1时，零件按平行移动方式转移；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。,具体做法,（1）当titi+1时，零件按平行移动方式转移；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。,平行顺序移动加工周期计算,已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平顺=4（10+5+15+10）-（4-1）（5+5+10）=100分钟,例已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟。求三种移动方式下的加工周期。解：T顺=4（10+5+15+10）=160分钟T平=（10+5+15+10）+（4-1）15=85分钟T平顺=4（10+5+15+10）-（4-1）（5+5+10）=100分钟,零件三种移动方式的比较,已知m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分别求在顺序移动、平行移动和平行顺序移动方式下，这批零件的加工周期。,第三节 单件作业排序问题,11.3.1 指派问题11.3.2 单件作业排序问题的描述11.3.3 两种作业计划的构成11.3.4 求解一般n/m/G/Fmax问题的启发式方法,1、指派问题的形式表述给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务,2、指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务 每一项任务只能由一个被指派者来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小,11.3.1 指派问题,设n 个人被分配去做n 件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i 个人去做第j 件工作的的效率为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率（时间或费用）最高？,3、指派问题模型（The Model for Assignment Problem）,典型问题,例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。,问：如何分配，能使所需的总时间最少？,建立模型,设 xij=,1,0,若第i项工作交与第j个人完成,若第i项工作不交与第j个人完成,译英文：,x11+x12+x13+x14=1,译日文：,x21+x22+x23+x24=1,译德文：,x31+x32+x33+x34=1,译俄文：,x41+x42+x43+x44=1,甲：,x11+x21+x31+x41=1,乙：,x12+x22+x32+x42=1,丙：,x13+x23+x33+x43=1,丁：,x14+x24+x34+x44=1,xij=0或1(i=1,2,3,4;j=1,2,3,4),4、指派问题的匈牙利解法,2,4,9,7,第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素,(1)从（cij）的每行元素都减去该行的最小元素；,(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。,4,2,在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。,第2步：进行试指派，即确定独立零元素,（2）若独立零元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n,则转入下一步。,例2 有甲、乙、丙、丁四个工人，要分别派他们完成四项不同的任务，分别记作A、B、C、D。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？,第1步，变换系数矩阵：,-5,第2步，确定独立零元素,找到 3 个独立零元素，但 m=3 n=4,求解过程如下,第3步，作最少的直线覆盖所有零元素：,(5)对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有零元素的最少直线数,(1)对没有独立零元素的行打号；,(2)对已打号的行中所有含划掉零元素的列打号；,(3)再对打有号的列中含独立零元素的行打号；,(4)重复(2)，(3)直到得不出新的打号的行、列为止；,第4步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行（或列）都减去这最小元素；,在出现负数的列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第2步。,-5,11.3.2 问题的描述,加工描述矩阵D为,D=,1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2,对于一般单件作业排序问题，每个工件都有其独特的加工路线，工件没有一定的流向。要描述一道工序，需要用三个参数：3个参数：i，j和k。i表示工件代号，j表示工序号，k表示完成工序i的第j道工序的机器代号。（i，j，k）表示工件i的第j道工序在机器k上进行。,11.3.3 两种作业计划的构成,各工序都按最早可能完工时间安排的作业计划称为能动作业计划。各工序都按最早可能开始时间安排的作业计划称为无延迟作业计划。无延迟作业计划是没有任何延迟出现的能动作业计划。,符号说明每安排一道工序称为一“步”St:t步之前已排序工序构成的部分作业计划；Ot:t步可排序工序的集合；Tk为Ot中工序Ok的最早可能开始时间；Tk为Ot中工序Ok的最早可能完成时间。,（一）能动作业计划的构成步骤,（1）设t=1,S1为空集，O1为各工件第一道工序的集合。（2）求T*=minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj T*。（4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。,例 有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：,D=,1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2,T=,2 4 13 4 5,试构成一个能动作业计划。,能动作业计划的构成,2,3,2,M2,13,13,8,2,3,2,6,1,3,2,M2,8,812,77,1,3,22,3,2,5,2,2,1,M1,7,87,73,1,3,22,2,1,4,1,2,3,M3,7,77,33,1,2,32,2,1,3,2,1,3,M3,3,63,20,1,2,32,1,3,2,1,1,1,M1,2,23,00,1,1,12,1,3,1,Oj,M*,T*,Tk,Tk,Ot,t,能动作业计划的甘特图,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,时间,机器,M1,M2,M3,（二）无延迟作业计划构成步骤,（1）设t=1,S1为空集，O1为各工件第一道工序的集合。（2）求T*=minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T*。（4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot，使t=t+1。（5）若还有未安排的工序，转步骤（2）；否则，停止。,无延迟作业计划的构成,1,3,2,M2,12,13,12,1,3,2,6,2,3,2,M2M2,77,812,77,1,3,22,3,2,5,2,2,1,M1,3,87,73,1,3,22,2,1,4,1,2,3,M3M1,33,77,33,1,2,32,2,1,3,2,1,3,M3,0,63,20,1,2,32,1,3,2,1,1,1,M1M3,00,23,00,1,1,12,1,3,1,Oj,M*,T*,Tk,Tk,Ot,t,无延迟作业计划的甘特图,2,3,2,1,1,1 2,2,1,2,1,3 1,2,3,3 7,7 12 13,2 3 7,0,时间,机器,M1,M2,M3,1,3,2,能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。,练 习,1.南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交易所提供全部客户服务的合同。取得合同的主要要求是快速交货。爱得说，如果南希厂可以在24小时内将爱得收到的5辆车全部整修并且重新喷漆，合同就归该厂。下面是这5辆车在整修和喷漆车间各自需要的时间。假定车子在重新喷漆前要经过重新整修的步骤，南希厂可以满足时间要求并且得到合同吗？,2.有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：试构成一个能动作业计划和无延迟作业计划。,D=,1,1,1 1,2,3 1,3,22,1,3 2,2,2 2,3,1,T=,3 5 22 4 3,4，1，2,M2,0,6,0,4，1，2,0,4,0,3，1，1,11,8,2，2，1,12,5,1，2，2,3,0,6,0,4，1，2,0,4,0,3，1，1,11,8,2，2，1,1，1，1,M1,0,5,0,1，1，1,2,0,6,0,4，1，2,0,4,0,3，1，1,2，1，3,M3,0,8,0,2，1，3,0,5,0,1，1，1,1,Oj,M*,T*,T k,Tk,Ot,t,16,9,4，3，1,13,9,3，2，4,12,9,2，2，1,1，2，2,M2,6,13,6,1，2，2,6,4，2，4,M4,6,8,6,4，2，4,13,9,3，2，4,12,9,2，2，1,6,13,6,1，2，2,5,8,6,4，2，4,3，1，1,M1,5,9,5,3，1，1,11,8,2，2，1,13,6,1，2，2,4,Oj,M*,T*,T k,Tk,Ot,t,4，3，1,M1,12,19,12,4，3，1,18,13,3，3，3,17,13,2，3，4,19,13,1，3，3,9,19,12,4，3，1,3，2，4,M4,9,13,9,3，2，4,16,12,2，3，4,19,13,1，3，3,8,9,16,9,4，3，1,9,13,9,3，2，4,2，2，1,M1,9,12,9,2，2，1,19,13,1，3，3,7,Oj,M*,T*,T k,Tk,Ot,t,22,19,4，4，3,18,19,18,3，4，2,18,27,18,2，4，3,1，3，3,M3,18,24,18,1，3，3,12,22,19,4，4，3,3，3，3,M3,13,18,13,3，3，3,26,17,2，4，3,13,19,13,1，3，3,11,22,19,4，4，3,13,18,13,3，3，3,2，3，4,M4,13,17,13,2，3，4,13,19,13,1，3，3,10,Oj,M*,T*,T k,Tk,Ot,t,2，4，3,M3,27,36,27,2，4，3,4，4，3,M3,24,27,24,4，4，3,24,33,24,2，4，3,24,27,24,4，4，3,24,33,24,2，4，3,1，4，4,M4,24,26,24,1，4，4,14,27,24,4，4，3,3，4，2,M2,18,19,18,3，4，2,33,24,2，4，3,26,24,1，4，4,13,Oj,M*,T*,T k,Tk,Ot,t,15,16,11.3.3 求解一般n/m/G/Fmax问题的启发式方法,三类启发式算法：优先调度法则随机抽样法概率调度法,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）报告,日常调度单,它告诉主管哪些工件要被加工，这些工件的优先级以及加工时间。,各种状态和异常报告,1、预计延期报告2、废品报告3、返工报告4、作业总结报告,漏斗模型,德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。,漏斗模型,漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。,注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔。,控制规则,在一段较长的时间内(如数周)内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率(平均生产率)等于平均在制品库存/平均通过时间。实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：若希望保持在制品库存量稳定，就要使单位时间内的平均输入等于平均输出。若希望改变在制品库存量，可暂时增加或减少输入。若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。,