第11章_制造业作业计划与控制.ppt

1,第十一章制造业作业计划与控制,11.1作业计划问题的基本概念11.2单台机器的排序问题11.3两台（或多台机器）的流水作业的排序问题11.4生产作业控制,2,视频：中国古典民乐欣赏大浪淘沙思考：学习的心境与人生的成长，我们需要什么？上善若水，水善利万物而不争。即：最高境界的善行就像水的品性一样，泽被万物而不争名利。“上善若水”语出老子,3,11收入、费用和利润,掌握：最长流程时间的计算2.约翰逊算法3.相同零件的3种移动方式下机器加工周期的计算方法,学习目的与要求,4,重难点最长流程时间的计算约翰逊算法,教学重点与难点,5,通过确定了各车间零部件的投入出产计划，将全厂性的生产计划变成了各车间的生产任务。各车间要完成既定的生产任务，还必须将零部件投入出产计划转变为车间生产作业计划，即：将车间的生产任务变成各个工段、班组、工作地的任务。将任务安排到工作地，就涉及到任务分配和作业排序等问题。,6,由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间,7,排序与编制作业计划的差别在编制作业计划过程中,有一个问题需要注意，即投入生产过程的作业顺序的安排.作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。作业排序实质上是要解决如何按时间的先后，将有限的资源分配给不同的工作任务使预定的目标最优化的问题。所以，编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。,8,确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪.如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年.以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,9,单件车间制定作业计划示意图,10,11,11.1排序问题的基本概念,11.1.1名词术语作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划编制作业计划（日程安排）：分配加工任务，确定加工顺序。排序：确定零件在机器上的加工顺序。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。调度：是作业计划编制后实施生产控制所采取的行动，而编制作业计划是加工制造发生之前的活动。赶工：实际进度已落后于计划进度时采取的行动。,12,机器可以是工厂里的各种机床，也可以是维修工人，表示“服务者”。零件代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件。加工路线零件加工的工艺过程所决定的路线（加工过程在技术上的约束）。加工顺序表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题。,13,11.1.2假设条件和符号说明,假设条件：一个零件不能同时在几台不同的机器上加工，每台机器同时只能加工一个零件；零件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工；不允许中断，零件一旦开始加工，须一直进行到完工，不得中途停止插入其它零件；每道工序只在一台机器上完成；零件数、机器数和加工时间已知。,14,符号说明,15,11.1.3排序问题的分类,（1）按机器的种类和数量不同单台机器的排序问题多台机器的排序问题对于多台机器排序问题，根据加工路线的特征，分成单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。,16,（2）按工件到达工作中心（或车间）的情况不同静态排序：当进行排序时，所有工件都已到达，或准备就绪动态排序：工件的到达是陆续的，要随时安排它们的加工顺序（3）按加工路线的特征-单件作业排序问题-流水作业排序问题;（4）按目标函数不同，可分为流程最短问题与误工最少问题等；（5）按目标函数的性质不同分为单目标排序问题与多目标排序问题;（6）按参数的性质，可以划分为确定型排序问题与随机型排序问题。,17,11.1.4排序问题的一般表示方法排序问题常用四个符号来描述:n/m/A/B其中：n工件数；m机器数；A工作车间类型；B目标函数，通常是使其最小若A处为F代替，则表示流水作业排序问题；若A处为P代替，则表示流水作业排列排序问题，即每个工件在各台机器上的加工顺序都相同；G单件作业若m为1时，A为空白，即单台机器的排序，对于单台机器排序问题，无所谓加工路线问题。B为目标函数，通常是使其值最小，如Cmax最长完工时间最短Fmax最长流程时间最短例如：4/2/P/Fmax表示4项工作在2台机器上流水作业时以最长流程时间最短为目标的排序。,18,小知识：甘特图,甘特图是作业排序中最常用的一种工具，最早由亨利.甘特于1917年提出。这种方法是基于作业排序的目的，将活动与时间联系起来的最早尝试之一。甘特图内在思想简单，即以图示的方式通过活动列表和时间刻度形象地表示出任何特定项目的活动顺序与持续时间。基本是一条线条图，横轴表示时间，纵轴表示活动（项目），线条表示在整个期间上计划和实际的活动完成情况。它直观地表明任务计划在什么时候进行，及实际进展与计划要求的对比。管理者由此可便利地弄清一项任务（项目）还剩下哪些工作要做，并可评估工作进度。,19,例如，假设一个汽车制造公司有三项工作在进行中，它们分别是加工汽车零件A、B和C。这些工作的预定计划和现在的完成情况如图所示：在当前日期（以记号标出的4月21日），这张甘特图显示出，A的完成情况滞后于计划，B在按计划完成，C的完成情况则超前于计划。假设截止到4月26日，需要零件A的公司还不能收到订货，其装配线就要停产，那么这种情况就需要新的作业计划并更新甘特图。,20,它描述不同工作在每一台机器上的工作次序，可被用来管理生产进度。,21,11.1.5生产调度问题优化的主要目标,22,23,11.2单台机器的排序问题,单台机器排序问题n个工件全部经由一台机器处理,J1J2J3Jn,机器,到达系统工件的集合,离开系统（机器）,24,11.2.1常见单台机器排序问题的目标函数1)平均流程时间最短,为n个零件经由一台机器的平均流程时间。,定义:,目标函数MIN:,2）最大延期量最小,定义:,为最大延期量。,目标函数,25,根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权(Priorities)。常见的优先权规则(Priorityrules)有：SPT-ShortestProcessTime,EDD-EarliestDueDateCR-CriticalRate等,分别用于解决不同的问题。按什么样的准则来选择，对排序方案的优劣有很大影响。,26,常用的优先顺序规则：,SPT（Shortestprocessingtime）法则优先选择加工时间最短的工序可使工件的平均流程时间最短，从而减少在制品量FCFS（Firstcomefirstserved）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平EDD（Earliestduedate）法则优先选择完工期限紧的工件可使工件最大延误时间最小MWKR（Mostworkremaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近,27,优先调度法则（续）,LWKR（Leastworkremaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成MOPNR（Mostoperationsremaining）法则优先选择余下工序数最多的工件与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的SCR（Smallestcriticalratio）法则优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）保证工件延误最少RANDOM法则随机地挑一个工件,28,具体就是：,FCFS规则优先选择最早进入可排序集合的工件。EDD规则优先选择完工期限最紧的工作。SPT规则优先选择加工时间最短的工件。SCR规则优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。MWKR规则优先选择余下加工时间最长的工件。LWKR规则优先选择余下加工时间最短的工件。MOPNR规则优先选择余下工序数最多的工件。RANDOM规则随机地挑选下一个工件。,29,一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化,30,例一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。,31,SPT规则（优先选择加工时间最短的工件）排序结果,顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。,流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和加工周期平均总库存=各工件实际取货时间之和加工周期,32,EDD规则（优先选择完工期限最紧的工作）排序结果,顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。,比较SPT（优先选择加工时间最短的工件）规则和EDD规则（优先选择完工期限最紧的工作）的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。,33,优先调度法则,按SPT法则可使工件的平均流程时间最短，从而减少在制品量。EDD法则可使工件延误时间最小。,34,35,11.3两台（或多台机器）的流水作业的排序问题,流水车间(Flowshop):工件的加工路线都一致，加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。典型的如流水线，主要考虑：（1）加工周期的计算（2）两台机器排序问题的最优算法（3）一般n/m/p/Fmax排序问题的启发式算法（4）相同零件、不同移动方式下加工周期,36,11.3.1最长流程时间Fmax的计算,n/m/P/Fmax问题，其中n为工件数，m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。,37,由于假设所有工件的到达时间都为零(ri=0，i=1，2，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。设n个工件的加工顺序为S(S1，S2，S3，Sn)，其中Si为第i位加工的工件的代号。以表示工件Si在机器Mk上的完工时间,表示工件Si在Mk上的加工时间，k=1，2，m；i=1，2，n，则可按以下公式计算：(111)(112)式(111)是一个递推公式。当由式(9.1)得出时，Fmax就求得了。,38,例有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。,39,对于第1行第1列，只需把加工时间的数值作为完工时间标在加工时间的右上角;对于第1行的其它元素，从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。对于从第2行到第m行，只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本列上一行的右上角数字中取较大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为Fmax。,Fmax的标注完工时间的规则,40,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,41,11.3.2n/2/F/Fmax问题的最优算法,对于n/2/F/Fmax问题，F表示流水线作业排序问题。对于n/2/F/Fmax问题，S.M.Johson于1954年给出了有效的算法，即著名的Johson算法。其目标是使从第一个工件开始到最后一个工件结束的总流程时间最短。,42,为了叙述方便，ai以Ji表示在M1上的加工时间，以bi表示Ji在M2上的加工时间。每个工件都按M1M2的路线加工。Johnson算法建立在Johnson法则的基础之上。Johnson法则为：如果min(ai,bj)min(aj,bi)则Ji应该排在Jj之前。如果中间为等号，则工件i既可排在工件j之前，也可以排在它之后。,43,Johnson算法的步骤：（1）列出每个作业在两台机器上的加工时间。（2）选择最短的加工时间，如果有两个相同的值，则任选一个。（3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。,44,【例】求如表所示的6/2/F/Fmax问题的最优解。,将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143,最优加工顺序为S=（2，5，6，1，4，3）最优顺序下的Fmax=28（如何算，用11.2.1最长流程时间Fmax的计算）,45,11.3.3n/m/P/Fmax问题的启发式算法,对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题，可以用运筹学中的分支定界法。用分支定界法可以保证得到一般nmPFmax问题的最优解。但对于实际生产中规模较大的问题，计算量相当大，以至用计算机也无法求解。同时，还需考虑经济性。如果为了求最优解付出的代价超过了这个最优解所带来的好处，也是不值得的。启发式算法（试探法）是一种能在可接受的费用内寻找最好的解的技术，但不一定能保证所得解的可行性和最优，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式算法是解决不确定性问题的重要方法，由于其计算量都比较大，所以随着计算机技术的发展，启发式算法取得了巨大的成就。,46,经典算法与启发式算法,驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后往山上开4.5公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路714号。用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。,47,1965年，DSPalmer提出按斜度指标排列工件的启发式算法，这种算法称之为Palmer算法。其中工件斜度指标可按下式计算：,算出i后，按i不增（递减）的顺序排列工件，可得出较满意的加工顺序。,一般n/m/P/Fmax问题的启发式算法,（一）Palmer（帕默）算法,48,P304例11.3有一个4/3/F/Fmax问题，用Palmer算法求解最优加工顺序。加工时间矩阵为：,49,解：,按照不增的顺序，得到最优加工顺序(1,2,3,4)和(2,1,3,4),50,按i不增的顺序排列工件，得到加工顺序(1，2，3，4)和(2，1，3，4)，恰好这两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下，Fmax=28。,51,52,11.3.4相同零件、不同移动方式下加工周期的计算（1）顺序移动方式,一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。,53,54,设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为ti（分钟/件），i=1.2n。则该批零件的加工周期为：例1：某企业生产产品的批量n=4件，经过4道工序加工，其单件工时为t1=10分，t2=5分，t3=20分，t4=10分，试求该批产品的生产周期？解：该批产品按顺序移动方式组织生产，则：,55,顺序移动法的优缺点采用顺序移动方式的优点是：1、组织与计划工作简单；2、零件集中加工，集中运输，减少了设备调整时间和运输工作量；3、设备连续加工不停顿，提高了工效。顺序移动法的缺点是：1、大多数产品有等待加工和等待运输的现象，生产周期长；2、资金周转慢，经济效益较差。顺序移动法的适用条件批量不大，单件加工时间较短、生产单位按工艺专业化组成，距离较远的情况下。,56,（2）平行移动方式,每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。,57,零件平行移动的加工周期为：,已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平=（10+5+15+10）+（4-1）15=85分钟,平行移动方式的优缺点优点：加工周期短，在制品占用量少；缺点：运输次数多，当前后工序时间不相等时，存在设备中断和制品等待的情况,58,（3）平行顺序移动方式,是顺序移动方式和平行移动方式两种方式的结合使用。是指一批零件在一道工序上尚未全部加工完毕，就将已加工好的一部分零件转入下道工序加工，以恰好能使下道工序连续地全部加工完该批零件为条件的移动方式。,（1）当titi+1时，零件按平行移动方式转移；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。,59,平行顺序移动加工周期计算,已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平顺=4（10+5+15+10）-（4-1）（5+5+10）=100分钟,60,例已知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分钟平行顺序移动法的优缺点优点：劳动过程中中断时间比顺序移动方式的少，零件生产周期较短；在一定程度上消除了工人与设备的空间时间，使工人和设备的空间时间集中起来，便于用来做其他工作。缺点：组织管理比较复杂。,61,三种移动方式的比较,当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型的移动方式顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工平行移动方式：单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式：两者混合,62,零件的三种移动方式的比较,63,64,生产运作控制是指对生产运作全过程进行监督、检查、调节和控制。它是生产与运作管理的重要职能之一，是实现生产运作主生产计划和生产作业计划的手段。前面所讲的主生产计划和生产作业计划仅仅是对生产运作过程事前的“预测性”安排，在计划执行过程中，注定会出现些预想不到的情况，管理者必须及时监督、检查，发现出现的偏差，并进行必要的调节和校正，也就是对生产系统实行实时控制，以确保计划的实现。,11.4生产作业控制,65,11.4.1实行生产作业控制的原因和条件11.4.2不同生产类型生产控制的特点11.4.3利用“漏斗模型”进行生产控制,66,11.4.1实行生产作业控制的原因和条件,原因加工时间估计不准确随机因素的影响加工路线