生产运作管理--制造业作业计划与控制--课件

第十一章 制造业作业计划与控制引言通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。1PPT课件11.1 作业计划问题的基本概念11.2 流水作业排序问题11.3 单件作业的排序问题11.4 生产作业控制 2PPT课件 11 收入、费用和利润收入、费用和利润要求掌握：1.最长流程时间的计算2.约翰逊算法 3.一般流水作业排序问题的3种启发式算法4.相同零件的3种移动方式下机器加工周期的计算方法学习目的与要求3PPT课件 重点 最长流程时间的计算 约翰逊算法 相同零件的3种移动方式下机器加工周期的计算方法 难点 一般流水作业排序问题的启发式算法教学重点与难点4PPT课件生产任务的最终落实MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。将任务安排到工作地，牵涉到作业计划。5PPT课件编制作业计划要解决的问题由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间例如;医院要安排病人手术，为此要安排手术室，配备手术器械、手术医师和护士。6PPT课件第一节 排序问题的基本概念一、名词术语排序：确定工件在机器上的加工顺序。作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。赶工：实际进度已落后于计划进度时采取的行动。7PPT课件“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题8PPT课件二、假设条件和符号说明假设条件：1.一个工件不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。4.每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件9PPT课件有关符号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为最长延迟时间10PPT课件三、排序问题的分类根据机器数的多少单台机器的排序问题多台机器的排序问题对于多台机器排序问题，根据加工路线的特征，分成单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。11PPT课件根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序12PPT课件4参数法n/m/A/B其中，n为工件数m为机器数A车间类型。在A的位置若标以标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。当m=1，则A处为空白。B为目标函数，通常是使其值最小例如：n/3/P/Cmax13PPT课件四、作业排序方案的评价标准1.工作流程时间从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。2.加工周期完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。14PPT课件3.在制品库存（WIP）在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。4.利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。15PPT课件五、优先调度规则调度方法：所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。16PPT课件常用的优先顺序规则：FCFS规则 优先选择最早进入可排序集合的工件。EDD规则 优先选择完工期限最紧的工作。SPT规则 优先选择加工时间最短的工件。SCR规则 优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。MWKR规则 优先选择余下加工时间最长的工件。LWKR规则 优先选择余下加工时间最短的工件。MOPNR规则 优先选择余下工序数最多的工件。RANDOM规则 随机地挑选下一个工件。17PPT课件一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化18PPT课件例 一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。发动机机壳所需标准加工时间（包括机器调整）预计顾客取货时间（从现在开始算起的所需工作时间）机壳1810机壳2612机壳31520机壳4318机壳5122219PPT课件机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存=102/44=2.32个 平均总库存=120/44=2.73个SPT规则排序结果 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和加工周期平均总库存=各工件实际取货时间之和加工周期20PPT课件机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数23.00.67.2平均在制品库存=115/44=2.61个 平均总库存=118/44=2.68个EDD规则排序结果 顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。21PPT课件优先调度法则按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件延误时间最小。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。22PPT课件第二节 流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致。加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。23PPT课件一、最长流程时间Fmax的计算n/m/P/Fmax问题，n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。24PPT课件例 有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。i12345642314245674558755542433125PPT课件ipi1pi2pi3pi461524325514454445325821753367426101213167111520273312172230354213212532384626PPT课件二、两台机器排序问题两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤：（1）列出每个作业在两台机器上的加工时间。（2）选择最短的加工时间，如果有两个相同的值，则任选一个。（3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。27PPT课件【例】求如表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474.5将零件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 328PPT课件【例 题】有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间：（1）根据Johnson算法安排工作顺序；（2）计算加工周期。任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.529PPT课件任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作230PPT课件A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2iCBDEA操作1操作231PPT课件【例 题】根据Johnson算法求以下8/2/F/Fmax问题的最优解。任务aibiA96B72C103D81EFGH2154587432PPT课件1.将所有ai bi的工件按ai值不减的顺序排成一个序列A；2.将aibi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。改进算法33PPT课件工件号 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4工件最优顺序：2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 21 4 8 13 18 263 11 15 22 26 28 ai bi 最优顺序下的加工周期为2834PPT课件练 习某公司要生产4种产品，需要两台机器1和2。其中，有3种产品需要先在机器1上加工。下表给出了两台机器上加工各产品所需的时间。（1）安排生产顺序，使得在最短时间内完成生产。（2）机器1共需工作多长时间？（3）机器2应该在机器1开始工作后多长时间开始运转？任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.1035PPT课件任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.109.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65机器1机器236PPT课件三、一般n/m/P/Fmax问题的启发式算法启发式算法是一个基于直观或经验构造的算法，在可接受的花费(时间、占用空间等)下给出待解决组合优化问题的可行解。启发式方法因其易于实现、计算复杂度低等原因，目前应用得最为广泛。37PPT课件（一）Palmer法1965年，DSPalmer提出按斜度指标排列工件的启发式算法，称之为 Palmer法。工件的斜度指标可按下式计算：k=l，2，m 式中，m为机器数；pik为工件i在Mk上的加工时间。按照各工件i不增的顺序排列工件，可得出令人满意的顺序。38PPT课件39PPT课件例 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用帕尔默法求最优顺序。i1234Pi11263Pi28429Pi34582解：对于本例，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。40PPT课件（二）关键零件法步骤如下：（1）计算每个零件的总加工时间，找出加工时间最长的零件C，将其作为关键零件。（2）对于余下的零件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。41PPT课件i1234pi11263pi28429pi34582pi13111614例 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用关键零件法求最优顺序。解：总加工时间最长的为3号零件，pi1pi3的零件为1和2，按pi1不减的顺序排成Sa=（1，2）；pi1pi3的零件为4号零件，Sb=（4）,这样得到的加工顺序为（1，2，3，4）。42PPT课件例 题用关键工件法求解下表的最优排序。解：总加工时间最长的为2号零件，pi1pi4的零件为1和3，按pi1不减的顺序排成sa=（1，4）；pi1pi4的零件为4号零件，sb=（3），这样得到的顺序为（1，4，2，3）。i1234pi11954pi25763pi34635pi46237i1234pi11954pi25763pi34635pi46237pi1624171943PPT课件（三）CDS法康坎贝尔-杜德克-史密斯三人提出了一个启发式算法，简称CDS法。具体做法是，对加工时间用Johnson算法求（m-1）次加工顺序，取其中最好的结果。44PPT课件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+pi445PPT课件lA 加工时间 B 加工时间1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tm46PPT课件i1234Pi11263Pi28429Pi34582i1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi3129101147PPT课件i1234l=1pi11263pi34582l=2pi1+pi296812pi2+pi31291011当l=1时，按（Johnson）算法得到加工顺序（1，2，3，4）；当l=2时，得到加工顺序（2，3，1，4）。对于（2，3，1，4），相应的Fmax=29。所以，取顺序（1，2，3，4）。48PPT课件用Palmer法、关键工件法和CDS法求以下4/4/P/Fmax问题的最优解，并比较三种方法的结果。i1234pi11954pi25763pi34635pi4623749PPT课件四、相同零件、不同移动方式下加工周期的计算排序问题针对的是不同零件，如果n个零件相同，则没有排序问题。但零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。三种典型的移动方式顺序移动方式(串行工程)平行移动方式（平行工程）平行顺序移动方式50PPT课件（一）顺序移动方式加工周期时间工序 1 2 3 4顺序移动方式顺序移动方式 一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。51PPT课件 设零件批量为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分钟52PPT课件（二）平行移动方式工序 1 2 34时间 加工周期 每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。53PPT课件零件平行移动的加工周期 为：已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平=（10+5+15+10）+（4-1）15=85分钟54PPT课件（三）平行顺序移动方式既要求每道工序连续进行加工，又要求各道工序尽可能平行地加工。时间工序1234 加工 周期（1）当titi+1时，零件按平行移动方式转移；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。55PPT课件具体做法（1）当titi+1时，零件按平行移动方式转移；（2）当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）ti+1作为零件在（i+1）工序的开始时间。56PPT课件平行顺序移动加工周期计算已知n=4，t1=10分钟，t2=5分钟，t3=15分钟，t4=10分钟，则T平顺=4（10+5+15+10）-（4-1）（5+5+10）=100分钟57PPT课件例已知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分钟58PPT课件比较项目平行移动平行顺序移动 顺序移动生产周期短中长运输次数多中少设备利用差好好组织管理中复杂简单零件三种移动方式的比较59PPT课件已知m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分别求在顺序移动、平行移动和平行顺序移动方式下，这批零件的加工周期。60PPT课件第三节 单件作业排序问题11.3.1 指派问题11.3.2 单件作业排序问题的描述11.3.3 两种作业计划的构成11.3.4 求解一般n/m/G/Fmax问题的启发式方法61PPT课件1 1、指派问题的形式表述、指派问题的形式表述给定了一系列所要完成的任务（给定了一系列所要完成的任务（taskstasks）以）以及一系列完成任务的被指派者及一系列完成任务的被指派者（assigneesassignees），所需要解决的问题就是要），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务确定出哪一个人被指派进行哪一项任务 2 2、指派问题的假设、指派问题的假设被指派者的数量和任务的数量是被指派者的数量和任务的数量是相同的相同的每一个被指派者只完成每一个被指派者只完成一项任务一项任务 每一项任务只能由每一项任务只能由一一个被指派者个被指派者来完成来完成 每个被指派者和每项任务的组合有一个相关成本每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小目标是要确定怎样进行指派才能使得总成本最小 11.3.1 指派问题62PPT课件设设n n 个个人人被被分分配配去去做做n n 件件工工作作，每每人人只只能能完完成成一一项项任任务务，每每项项任任务务只只能能由由一一人人完完成成。已已知知第第i i 个个人人去去做做第第j j 件件工工作作的的的的效效率率为为C Cijij(i i=1.2=1.2n n;j j=1.2=1.2n n)并并假假设设C Cijij 00。问问应应如如何何分配才能使总效率（分配才能使总效率（时间或费用）最高？时间或费用）最高？3、指派问题模型、指派问题模型（The Model for Assignment Problem）63PPT课件典型问题典型问题 例例1 1：有一份说明书，要分别译成英、日、：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。每个人只能完成其中的一项工作。64PPT课件问：如何分配，能使所需的总时间最少？问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 65PPT课件建立模型设设 xij=10若第若第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=1xij=0或或1 (i=1,2,3,4;j=1,2,3,4)甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 66PPT课件4、指派问题的匈牙利解法、指派问题的匈牙利解法67PPT课件2497第第1 1步：变换指派问题的系数矩阵（步：变换指派问题的系数矩阵（c cijij），使各行），使各行各列中都出现各列中都出现0 0元素元素(1)(1)从（从（c cijij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。再从所得新系数矩阵无零元素的列中减去该列的最小元素。4268PPT课件在变化后的效率矩阵中找尽可能多的独立在变化后的效率矩阵中找尽可能多的独立0 0元素，若元素，若能找出能找出n n个独立个独立0 0元素，就以这元素，就以这n n个独立个独立0 0元素对应解元素对应解矩阵矩阵(x xijij)中的元素为中的元素为1 1，其余为，其余为0 0，这就得到最优解。，这就得到最优解。第第2 2步：进行试指派，即确定独立零元素步：进行试指派，即确定独立零元素（1 1）从有唯一的零元素的行或）从有唯一的零元素的行或列开始确定独立零元素，并用列开始确定独立零元素，并用 表示，并划掉其所在行或列的表示，并划掉其所在行或列的其他零。直到尽可能多的零元其他零。直到尽可能多的零元素都被圈出和划掉为止。素都被圈出和划掉为止。0 0（2 2）若）若独立零元素独立零元素的数目的数目m m等等于矩阵的阶数于矩阵的阶数n n，那么这指派，那么这指派问题的最优解已得到。若问题的最优解已得到。若m m n n,则转入下一步。则转入下一步。69PPT课件70PPT课件例例2 2 有有甲、乙、丙、丁甲、乙、丙、丁四个工人，要分别派他们完四个工人，要分别派他们完成四项不同的任务，分别记作成四项不同的任务，分别记作A A、B B、C C、D D。他们完成各项。他们完成各项任务所需时间如下表所示，任务所需时间如下表所示，问如何分派任务，可使总时间问如何分派任务，可使总时间最少？最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁598271PPT课件第第1 1步，变换系数矩阵：步，变换系数矩阵：-5第第2 2步，确定独立零元素步，确定独立零元素 找到找到 3 个独立零元素，个独立零元素，但但 m=3 n=4求解过程如下求解过程如下 第第3 3步，作最少的直线覆盖所有零元素：步，作最少的直线覆盖所有零元素：(5)(5)对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就号的列画纵线，这就得到覆盖所有零元素的最少直线数得到覆盖所有零元素的最少直线数(1)(1)对没有独立零元素的行打对没有独立零元素的行打号；号；(2)(2)对已打对已打号的行中所有含划掉零元素的列打号的行中所有含划掉零元素的列打号；号；(3)(3)再对打有再对打有号的列中含独立零元素的行打号的列中含独立零元素的行打号；号；(4)(4)重复重复(2)(2)，(3)(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；72PPT课件第第4 4步步：在在没没有有被被直直线线覆覆盖盖的的所所有有元元素素中中找找出出最最小小元元素素，然后将所在行然后将所在行（或列）（或列）都减去这最小元素；都减去这最小元素；在出现负数的列在出现负数的列（或行）（或行）都加上这最小元素（以保证都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第原问题仍相同。转回第2 2步。步。73PPT课件-574PPT课件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上进行。75PPT课件11.3.3 两种作业计划的构成各工序都按最早可能完工时间安排的作业计划称为能动作业计划。各工序都按最早可能开始时间安排的作业计划称为无延迟作业计划。无延迟作业计划是没有任何延迟出现的能动作业计划。76PPT课件符号说明每安排一道工序称为一“步”St:t步之前已排序工序构成的部分作业计划；Ot:t步可排序工序的集合；Tk为Ot中工序Ok的最早可能开始时间；Tk为Ot中工序Ok的最早可能完成时间。77PPT课件（一）能动作业计划的构成步骤（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）；否则，停止。78PPT课件例 有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5试构成一个能动作业计划。79PPT课件能动作业计划的构成2,3,2M2131382,3,261,3,2M28812771,3,22,3,252,2,1M1787731,3,22,2,141,2,3M3777331,2,32,2,132,1,3M3363201,2,32,1,321,1,1M1223001,1,12,1,31OjM*T*TkTkOtt80PPT课件能动作业计划的甘特图2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70时间时间机器 M1M2M381PPT课件（二）无延迟作业计划构成步骤（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）；否则，停止。82PPT课件无延迟作业计划的构成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,31OjM*T*TkTkOtt83PPT课件无延迟作业计划的甘特图2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 13 2 3 70时间时间机器 M1M2M31,3,284PPT课件能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。85PPT课件练 习1.南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交易所提供全部客户服务的合同。取得合同的主要要求是快速交货。爱得说，如果南希厂可以在24小时内将爱得收到的5辆车全部整修并且重新喷漆，合同就归该厂。下面是这5辆车在整修和喷漆车间各自需要的时间。假定车子在重新喷漆前要经过重新整修的步骤，南希厂可以满足时间要求并且得到合同吗？汽车整修时间（小时）重新喷漆时间（小时）A63B04C52D86E2186PPT课件2.有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：试构成一个能动作业计划和无延迟作业计划。D=1,1,1 1,2,3 1,3,22,1,3 2,2,2 2,3,1T=3 5 22 4 387PPT课件4，1，2M20604，1，20403，1，11182，2，11251，2，230604，1，20403，1，11182，2，11，1，1M10501，1，120604，1，20403，1，12，1，3M30802，1，30501，1，11OjM*T*T kTkOtt88PPT课件1694，3，11393，2，41292，2，11，2，2M261361，2，264，2，4M46864，2，41393，2，41292，2，161361，2，25864，2，43，1，1M15953，1，11182，2，11361，2，24OjM*T*T kTkOtt89PPT课件4，3，1M11219124，3，118133，3，317132，3，419131，3，3919124，3，13，2，4M491393，2，416122，3，419131，3，3891694，3，191393，2，42，2，1M191292，2，119131，3，37OjM*T*T kTkOtt90PPT课件22194，4，31819183，4，21827182，4，31，3，3M31824181，3，31222194，4，33，3，3M31318133，3，326172，4，31319131，3，31122194，4，31318133，3，32，3，4M41317132，3，41319131，3，310OjM*T*T kTkOtt91PPT课件2，4，3M32736272，4，34，4，3M32427244，4，32433242，4，32427244，4，32433242，4，31，4，4M42426241，4，41427244，4，33，4，2M21819183，4，233242，4，326241，4，413OjM*T*T kTkOtt151692PPT课件11.3.3 求解一般n/m/G/Fmax问题的启发式方法三类启发式算法：n优先调度法则n随机抽样法n概率调度法93PPT课件1.优先调度法则SPT（Shortest processing time）法则优先选择加工时间最短的工序可使工件的平均流程时间最短，从而减少在制品量FCFS（First come first served）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平EDD（Earliest due date）法则优先选择完工期限紧的工件可使工件最大延误时间最小MWKR（Most work remaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近94PPT课件1.优先调度法则（续）LWKR（Least work remaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成MOPNR（Most operations remaining）法则优先选择余下工序数最多的工件与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的SCR（Smallest critical ratio）法则优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）保证工件延误最少RANDOM法则随机地挑一个工件95PPT课件96PPT课件2.随机抽样法随机抽样法实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划这种方法不一定能得到最优作业计划，但可以得到较满意的作业计划效果与样本大小有关。样本越大，获取较好解的可能性越大从无延迟作业计划母体中抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好97PPT课件3.概率调度法给不同的工序按某一优先调度法则分配不同的挑选概率，可以得到多个作业计划供比较。例如，在构成无延迟作业计划的第（3）步 有3道工序，A、B和C可挑选 3道工序所需的时间分别为3，4和7 将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率比如A、B和C的挑选概率分别为6/14、5/14和3/14既保证了SPT法则起作用，又可产生多个作业计划供挑选98PPT课件u 生产作业控制是指在生产过程中，按既定的政策、目标、计划和标准，通过监督和检查生产活动的进展情况、实际成效，及时发现偏差，找出原因，采取措施，以保证目标、计划的实现。u 生产运作控制的受控客体是生产运作过程，其预定目标是主生产计划与生产作业计划的目标值。11.4 生产作业控制生产作业控制99PPT课件一、生产活动与作业计划产生偏差的原因（1）加工时间估计不准确（2）随机因素的影响（3）加工路线的多样性（4）企业环境的动态性11.4 生产作业控制生产作业控制100PPT课件二、生产作业控制的程序 制定生产作业监控体系 监控实际生产过程 评估偏差情况 采取纠偏措施11.4 生产作业控制生产作业控制101PPT课件三、生产作业控制的主要工具 实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：调度单 日报、月报 例外报告、异常报告 输入/输出（I/O）报告102PPT课件日常调度单它告诉主管哪些工件要被加工，这些工件的优先它告诉主管哪些工件要被加工，这些工件的优先级以及加工时间。级以及加工时间。开始日期开始日期开始日期开始日期工件号工件号工件号工件号描述描述描述描述运行时间运行时间运行时间运行时间201201201201203203203203205205205205205205205205207207207207208208208208151311513115131151311514315143151431514315145151451514515145157121571215712157121534015340153401534015312153121531215312轴轴轴轴铆钉铆钉铆钉铆钉锭子锭子锭子锭子锭子锭子锭子锭子测量杆测量杆测量杆测量杆轴轴轴轴11.411.411.411.420.620.620.620.64.34.34.34.38.68.68.68.66.56.56.56.54.64.64.64.6103PPT课件各种状态和异常报告各种状态和异常报告1、预计延期报告、预计延期报告2、废品报告、废品报告3、返工报告、返工报告4、作业总结报告、作业总结报告部件号部件号部件号部件号 计划日期计划日期计划日期计划日期 新日期新日期新日期新日期延期原因延期原因延期原因延期原因措施措施措施措施1712517125130441304417653176534/104/104/114/114/114/114/154/155/15/15/145/14夹具损坏夹具损坏夹具损坏夹具损坏送去镀金，镀金工送去镀金，镀金工送去镀金，镀金工送去镀金，镀金工罢工罢工罢工罢工新孔未成直线新孔未成直线新孔未成直线新孔未成直线工具室返还工具室返还工具室返还工具室返还4/154/15新批量开始生产新批量开始生产新批量开始生产新批量开始生产工程部重新安装工程部重新安装工程部重新安装工程部重新安装钻模钻模钻模钻模104PPT课件漏斗模型德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。105PPT课件漏斗模型 漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。106PPT课件注：曲线图的垂直段表示到达或完成的工作量；水注：曲线图的垂直段表示到达或完成的工作量；水平段表示相邻到达或完成的任务之间的时间间隔。平段表示相邻到达或完成的任务之间的时间间隔。107PPT课件控制规则在一段较长的时间内(如数周)内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率(平均生产率平均生产率)等于平均在制品库存/平均通过时间。实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：若希望保持在制品库存量稳定，就要使单位时间内的平均输入等于平均输出。若希望改变在制品库存量，可暂时增加或减少输入。若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。108PPT课件