生产与运作管理 第11章 制造业作业计划与控制

生产与运作管理第11章制造业作业计划与控制生产与运作管理PRODUCTIONOPERATIONSMANAGEMENT华中科技大学管理学院THESCHOOLOFMANAGEMENT，HUST陈荣秋马士华RONGQIUCHENANDSHIHUAMA华中科大管理学院陈荣秋马士华第11章制造业作业计划与控制SCHEDULINGANDCONTROLLINGFORMANUFACTURING111作业计划问题的基本概念112流水作业排序问题113单件作业的排序问题114生产作业控制华中科大管理学院陈荣秋马士华编制作业计划要解决的问题工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。华中科大管理学院陈荣秋马士华111作业计划问题的基本概念编制作业计划要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。华中科大管理学院陈荣秋马士华111作业计划问题的基本概念（续）有关的名词术语编制作业计划或日程安排SCHEDULING排序SEQUENCING派工DISPATCHING控制CONTROLLING赶工EXPEDITING“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动华中科大管理学院陈荣秋马士华111作业计划问题的基本概念（续）“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束“加工顺序”则表示每台机器加工N个零件的先后顺序，是排序和编制作业计划要解决的问题华中科大管理学院陈荣秋马士华常用的符号华中科大管理学院陈荣秋马士华排序问题的分类华中科大管理学院陈荣秋马士华排序问题的分类FLOWSHOP华中科大管理学院陈荣秋马士华排序问题的分类JOBSHOPJOBAJOBB华中科大管理学院陈荣秋马士华排序问题的表示方法华中科大管理学院陈荣秋马士华112流水作业排序问题流水车间FLOWSHOP工件的加工路线都一致，典型的如流水线1121最长流程时间的计算1122两台机器排序问题的最优算法1123多台机器排序问题的启发式算法WORKCENTER1WORKCENTER2OUTPUT华中科大管理学院陈荣秋马士华1121最长流程时间的计算（练习）工件代号I123456PI1464583PI2353971PI3792658PI45496236/4/P/FMAX，加工顺序为1,4,6,3,5,2，求FMAX华中科大管理学院陈荣秋马士华1121最长流程时间的计算工件代号I146352PI1453486PI2391375PI3768259PI4563924491216243071819223136142432343948193035444652华中科大管理学院陈荣秋马士华1122两台机器排序问题的最优算法约翰森法则如果MINAI,BJMINAJ,BI,则工件I应该排在工件J之前。约翰森算法（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。华中科大管理学院陈荣秋马士华1122两台机器排序问题的最优算法（续）然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤（1）。华中科大管理学院陈荣秋马士华将工件2排在第1位2将工件3排在第6位23将工件5排在第2位253将工件6排在第3位2563将工件4排在第5位25643将工件1排在第4位256143最优加工顺序为S2,5,6,1,4,3,FMAX28I123456AI518534BI7224741122两台机器排序问题的最优算法（续）华中科大管理学院陈荣秋马士华1122两台机器排序问题的最优算法（续）举例工件号123456AI518534BI722474工件最优顺序2561431345582747424813182631115222628AIBI最优顺序下的加工周期为28华中科大管理学院陈荣秋马士华有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的加工时间12251630153020103035ABCDE操作2所需时间（小时）操作1所需时间（小时）任务（1）根据JOHNSON算法安排工作顺序（2）用甘特图表示出任务的进行情况华中科大管理学院陈荣秋马士华1123多台机器排序问题的启发式算法关键工件法1计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；2对于余下的工件，若PI1PIM则按PI1不减的顺序排成一个序列SA,若PI1PIM则按PIM不增的顺序排成一个序列SB3顺序（SA,C,SB）即为所求顺序。华中科大管理学院陈荣秋马士华1123多台机器排序问题的启发式算法（续）举例工件I1234PI12163PI24829PI3548211131614CSA2,1SB4所求顺序（2,1,3,4）华中科大管理学院陈荣秋马士华一般N/M/P/FMAX问题的启发式算法PALMER法CDS法华中科大管理学院陈荣秋马士华练习书345346页，第2、3、4题华中科大管理学院陈荣秋马士华1124相同零件不同移动方式下加工周期的计算当N个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型的移动方式顺序移动方式一批零件全部加工完成后，整批移动到下道工序加工平行移动方式单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式两者混合华中科大管理学院陈荣秋马士华顺序移动方式加工周期时间工序1234顺序移动方式华中科大管理学院陈荣秋马士华平行移动方式工序1234时间加工周期华中科大管理学院陈荣秋马士华平行顺序移动方式特点既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示时间工序1234加工周期华中科大管理学院陈荣秋马士华113单件作业排序问题1131任务分配问题1132单件作业排序问题的描述1133优先派工准则1134求解一般N/M/G/FMAX问题的启发式方法华中科大管理学院陈荣秋马士华1131任务分配问题在生产运作管理工作中，管理人员经常面临的一个问题是如何根据有限的资源人力、物力、财力等，进行工作任务分配，以达到降低成本或提高经济效益的目的。如有A、B、C、D四门课程，上课的老师可以从甲、乙、丙、丁四名老师中选择，不同的老师上不同的课程，其费用是不同的，并且规定，每人只讲一门课程，每门课程只需要一人讲授。问如何安排，才能使总的上课费用最低又如运输任务的分配问题。有N条航线的运输任务指派给N艘船去完成，不同的船完成不同的航线其运输成本不同。要求每条船完成一条航线，并且一条航线只能由一条船去完成。如何分配任务，才能使总的费用最小。这类问题是常见的任务分配问题，也叫指派问题，它的目标是如何进行合理的任务分配，使总的费用最小。华中科大管理学院陈荣秋马士华任务分配问题任务分配问题可以用一般的整数规划求解方法进行求解。但是，整数规划问题的求解也是非常困难的，到目前为止，还缺乏统一的求解方法。本课程采用匈牙利法求解任务分配问题。华中科大管理学院陈荣秋马士华匈牙利法求解任务分配问题可以证明，对于分配问题，在其费用矩阵CIJ中，各行、各列均减去一个常数，CIJ改变以后的最优解，仍为原问题的最优解。利用这个性质，通过对CIJ的行、列进行加减常数的计算，把一些矩阵元素变为0，在CIJ为0的元素上进行分解，就可得到原问题的最优解。该方法应用了匈牙利数学家KONIG矩阵性质定理，因此这种方法被称为匈牙利法。华中科大管理学院陈荣秋马士华匈牙利法求解任务分配问题第一步将原分配问题的效率矩阵进行变换得使各行各列中都出现0元素,其方法如下率矩阵的每行元素中减去该行的最小元素，从所得效率矩阵的每列中减去该列的最小元素。第二步进行试分配,求初始分配方案,做法如下只有一个0元素的行或列开始,给这个元素加圈，记为然后划去该0元所在列或行的其他0元,记为，有一个0元素的列或行中0元素加圈，记为，然后划去该0元所在行或列的其他0元,记为，进行,两步,直到所有0元素都被或为止，元素的数目M等于矩阵的阶数N,那么这个分配问题的最优解已得到,此时只要令处的变量XIJ1,其余XIJ为0,即为所求的最优解,否则,若MN,则转入第三步。华中科大管理学院陈荣秋马士华匈牙利法求解任务分配问题第三步寻找覆盖所有0元素的最少直线,以确定该矩阵中能找到的最多的独立0元素的个数为此，我们按以下步骤进行对没有的行打号，对已经有号的行中所有含的列打号，再对打有号的列中含有元素的行打号，重复,直到得不出新的打号的行,列为止，对没有打号的行画横线,有打的列画纵线,就得到覆盖所有0元素的最少直线数。令这些直线数为L,若LN,说明必须再变换当前的矩阵,才能找到N个独立0元素则转第四步华中科大管理学院陈荣秋马士华第四步调整,使之增加一些0元素,具体做法如下在没有被直线段覆盖的元素中,找出最小元素在没有被直线段覆盖的元素中,减去最小元素横线和纵线交叉处的元素加上这个最小元素被一条直线覆盖横线或纵线的元素不变。得新的缩减矩阵,再转第二步华中科大管理学院陈荣秋马士华练习求如下系数矩阵所对应的任务分配问题华中科大管理学院陈荣秋马士华答案最优任务分配方案为X13X22X34X411，最优值为48。华中科大管理学院陈荣秋马士华1132单件作业排序问题的描述D1,1,11,2,31,3,22,1,32,2,12,3,2T241345加工描述矩阵D和加工时间矩阵T对应华中科大管理学院陈荣秋马士华1133优先派工准则按什么样的法则来选择可安排的工序，对作业计划的优劣有很大影响。迄今，人们已提出了100多个优先派工法则，下面列出4个进行比较FCFSFIRSTCOMEFIRSTSERVED法则优先选择最早进入可排工序集合的工件。SPTSHORTESTPROCESSINGTIME法则优先选择加工时间最短的工序。EDDEARLIESTDUEDATE法则优先选择完工期限紧的工件。LPTLONGESTPROCESSINGTIME法则优先选择加工时间最长的工件。华中科大管理学院陈荣秋马士华1133优先派工准则（续）例有6项任务A，B，C，D，E，F要完成。每项任务所需时间和完工期限如下表所示。分别按（1）FCFS，（2）SPT，（3）EDD和（4）LPT法则，来确定完成任务的先后次序及相应的指标。716417151828410512ABCDEF完工期限（天）所需时间（天）任务华中科大管理学院陈荣秋马士华1133优先派工准则（续）如果任务下达的顺序是ABCDEF，按FCFS法则，任务的流程时间就是每件任务的等待时间加上加工时间。5412041累计00107142371641715182101424294128410512ABCDEF延迟时间完工期限流程时间加工时间任务次序华中科大管理学院陈荣秋马士华1133优先派工准则（续）按照FCFS法则，可以得到下列结果平均流程时间累计流程时间/任务数120/620天利用率累计加工时间/累计流程时间41/120342系统中平均在制品数量累计流程时间/累计加工时间120/41293件任务平均延迟时间延迟时间总和/任务数54/69天华中科大管理学院陈荣秋马士华1133优先派工准则（续）按SPT法则，处理任务的的流程时间就是每件任务的等待时间加上加工时间。4010841累计020312237415161718261119294124581012ACEBDF延迟时间完工期限流程时间加工时间任务次序华中科大管理学院陈荣秋马士华1133优先派工准则（续）按照SPT法则，得到下列结果平均流程时间108/618天利用率41/10838系统中平均在制品数量108/41263件任务平均延迟时间40/6667天华中科大管理学院陈荣秋马士华1133优先派工准则（续）按EDD法则，处理任务的先后次序是CAEBDF，如下表所示。3811041累计000312234715161718461119294142581012CAEBDF延迟时间完工期限流程时间加工时间任务次序华中科大管理学院陈荣秋马士华1133优先派工准则（续）按照EDD法则，得到下列结果平均流程时间110/6183天利用率41/110373系统中平均在制品数量110/41268件任务任务平均延迟时间38/6633天华中科大管理学院陈荣秋马士华1133优先派工准则（续）按LPT法则，处理任务的先后次序是FDBECA，如下表所示。10817941累计0514203534181716154712223035394112108542FDBECA延迟时间完工期限流程时间加工时间任务次序华中科大管理学院陈荣秋马士华1133优先派工准则（续）按照LPT法则，得到下列结果平均流程时间179/6298天利用率41/179229系统中平均在制品数量179/41437件任务任务平均延迟时间108/618天华中科大管理学院陈荣秋马士华1133优先派工准则（续）966763318293263268437342383732292018183298FCFSSPTEDDLPT平均延迟时间（天）平均在制品数利用率（）平均流程时间（天）方法（1）按照LPT法则进行作业排序，各项指标最差。（2）按SPT法则可使工件的平均流程时间最短，使平均在制品数量最少。（3）FCFS法则对工件较公平，这一点在对顾客服务中尤其重要，但在多数情况下都不具有优势。（4）EDD法则可使工件的平均延迟时间最小，其它指标也不错。华中科大管理学院陈荣秋马士华1134求解一般N/M/G/FMAX问题的启发式方法（1）两种作业计划的构成能动作业计划无延迟作业计划（2）三类启发式算法运用优先派工法则随即抽样法概率调度法华中科大管理学院陈荣秋马士华（1）两种作业计划的构成符号说明每安排一道工序称为一“步”STT步之前已排序工序构成的部分作业计划；OTT步可排序工序的集合；TK为OT中工序OK的最早可能开始时间；TK为OT中工序OK的最早可能完成时间。华中科大管理学院陈荣秋马士华（1）两种作业计划的构成（续）能动作业计划的构成（1）设T1,S1为空集，O1为各工件第一道工序的集合。（2）求TMINTK,并求出T所出现的机器M。如果M有多台，则任选一台。（3）从OT中选出满足以下两个条件的工序OJ需要M加工，且TJT。（4）将选定的工序OJ放入ST,从OT中消去OJ,并将OJ的紧后工序放入OT，使TT1（5）若还有未安排的工序，转步骤（2）；否则，停止。华中科大管理学院陈荣秋马士华能动作业计划的构成2,3,2M2131382,3,261,3,2M28812771,3,22,3,252,2,1M1787731,3,22,2,141,2,3M3M1777331,2,32,2,132,1,3M3363201,2,32,1,321,1,1M1223001,1,12,1,31OJMTTKTKOTT华中科大管理学院陈荣秋马士华能动作业计划的甘特图2,3,21,1,12,2,11,3,22,1,31,2,33778132370时间机器M1M2M3华中科大管理学院陈荣秋马士华1132两种作业计划的构成（续）无延迟作业计划的构成（1）设T1,S1为空集，O1为各工件第一道工序的集合。（2）求TMINTK,并求出T所出现的机器M。如果M有多台，则任选一台。（3）从OT中选出满足以下两个条件的工序OJ需要M加工，且TJT。（4）将选定的工序OJ放入ST,从OT中消去OJ,并将OJ的紧后工序放入OT，使TT1（5）若还有未安排的工序，转步骤（2）；否则，停止。华中科大管理学院陈荣秋马士华无延迟作业计划的构成1,3,2M21213121,3,262,3,2M2M277812771,3,22,3,252,2,1M1387731,3,22,2,141,2,3M3M13377331,2,32,2,132,1,3M3063201,2,32,1,321,1,1M1M30023001,1,12,1,31OJMTTKTKOTT华中科大管理学院陈荣秋马士华无延迟作业计划的甘特图2,3,21,1,12,2,12,1,31,2,337712132370时间机器M1M2M31,3,2华中科大管理学院陈荣秋马士华练习有一个2/3/G/FMAX的问题，其加工描述矩阵D和加工时间矩阵T分别如下所示，请构成一个能动作业计划和无延迟作业计划。D1,1,11,2,31,3,22,1,32,2,22,3,1T352243华中科大管理学院陈荣秋马士华（2）三类启发式算法优先调度法则构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划计算量小已经提出100多种优先调度法则华中科大管理学院陈荣秋马士华优先调度法则FCFS（FIRSTCOME,FIRSTSERVED）选择最早进入可排序集合的工序SPTSHORTESTPROCESSINGTIME）选择加工时间最短的工序EDD（EARLIESTDUEDATE）选择完工期限最紧的工序SCRSMALLESTCRITICALRATIO选择临界比最小的工件MWKRMOSTWORKREMAINING选择余下加工时间最长的工件LWKRLEASTWORKREMAINING选择余下加工时间最短的工件MOPNRMOSTOPERATIONSREMAINING选择余下工序数最多的工件RANDOM随机挑选一个工件RUSHTOPPRIORITY华中科大管理学院陈荣秋马士华（2）三类启发式算法（续）随机抽样法从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。概率调度法将优先调度法则与随机抽样法结合对不同工件将优先调度法则分配不同的挑选概率，效果较好华中科大管理学院陈荣秋马士华实行生产作业控制的原因生产计划和生产作业计划在实施过程中由于以下原因，往往造成实施情况与计划要求偏离加工时间估计不准确。随机因素的影响。加工路线的多样性。企业环境的动态性。华中科大管理学院陈荣秋马士华实行生产作业控制的条件要有一个标准。标准就是生产计划和生产作业计划。要取得实际生产进度与计划偏离的信息。要能采取纠正偏差的行动。华中科大管理学院陈荣秋马士华不同生产类型生产控制的特点单件小批生产对于单件小批生产，排队时间是主要的，它大约占工件加工提前期的8095。排队时间越长，在制品库存就越高。如果能够控制排队时间，也就控制了工件在车间的停留时间。要控制排