生产与运作管理章生产作业计划与控制.pptx
2023/2/161第九章 生产作业计划第一节 流水线生产作、业计划的期量标准 第二节 流水线生产作业计划的编制 第二节 周期性生产类型作业计划的期量标准 第四节 周期性生产类型作业计划编制 第五节 流程式吁：产作业计划案例 第六节 关于作业计划的进一步讨论 第1页/共48页2023/2/162生产作业计划与控制单件作业排序问题4排序问题的基本概念1单台设备的排序问题2 35流水型作业排序问题生产作业控制第2页/共48页2023/2/163第一节 排序问题的基本概念1、排序的概念与作用u作业排序：生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。u生产作业计划：不仅包括确定零件的加工顺序，而且还包括确定设备加工每一个零件的开始时间和完工时间。u作用：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货第3页/共48页2023/2/164排排序序问问题题分分类类按按 机机 器器 数数量量单台机器排序问题单台机器排序问题多台机器排序问题多台机器排序问题流水作业排序问题流水作业排序问题单件作业排序问题单件作业排序问题按零件到达车间的情况按零件到达车间的情况静态的排序问题静态的排序问题动态的排序问题动态的排序问题按目标函数的性质分类按目标函数的性质分类按参数按参数确定型排序问题确定型排序问题随机型排序问题随机型排序问题2、排序问题的分类 单目标排序多目标排序第4页/共48页2023/2/165排序的目标函数（1）流程时间：任务在车间的停留时间Fi总流程时间：Fi最大流程时间：Fmax=maxFi平均流程时间：Fi/n（2）等待时间总等待时间平均等待时间（3）延期量：交货期拖延的时间（D）最大延期量:Dmax=maxDi总延期量：Di（4）加工周期已知条件u零件加工工艺过程u作业时间ti u交货期 Ci时间J1J2J3J4C1C2C3C4t1t2t3t4F1F2F3F4第5页/共48页2023/2/1663、排序问题的表示法 n/m/A/B 其中：n零件数 m设备数 A车间类型 流水作业排序F 单件作业排序G 当m=1时，A处为空白，因为对于单台设备的排序问题，无所谓加工路线问题，也谈不上流水型或单件作业 B目标函数 例：5个工件经过4台设备加工，目标是使加工周期最短的流水型作业排序可以表示为：5/4/F/Fmax第6页/共48页2023/2/1671、单台设备排序问题的特点 无论n个零件加工任务作何种排序，n项任务中的最大流程时间(加工周期)总是一个固定值第二节 单台设备加工排序问题 零件号零件号 作业时间作业时间 4 4 8 82 2 5 5 9 9 加工周期=4+8+2+5+9=28目标函数？第7页/共48页2023/2/1681)目标:使平均流程时间最短或平均等待时间最短2)方法：按任务所需时间长短，从短到长顺序排列。例：零件号零件号 作业时间作业时间 1.751.750.250.250.70.70 01.301.302.252.251.01.00.750.75排序：一一一一一一2、SPT法（最短最短等待等待时间）时间）第8页/共48页2023/2/169例题:已知条件如表所示,求平均流程时间,平均等待时间，最大交货延期 零件号零件号 作业时间作业时间 4 4 8 82 2 5 5 9 9 3 3 预定交货期预定交货期 24 24 23 23 8 8 6 6 3232 13 13解：列表如下加工顺序123456零件号作业时间234589流程时间259142231等待时间02591422预定交货期8132462332交货延期000800第9页/共48页2023/2/1610答：最大流程时间：31 最大等待时间：22 平 均 流 程 时 间=(2+5+9+14+22+31)613.83 平均等待时间=(0+2+5+9+1+14+22)/6=8.67 最大交货延期：8 总交货延期：(0+0+0+8+0+0)=8缺点：可能发生交货延期；优点：平均流程时间短加工顺序123456零件号作业时间234589流程时间259142231等待时间02591422预定交货期8132462332交货延期000800第10页/共48页2023/2/16111)目标：最大交货延期时间最小。2)方法：按预定交货期(生产任务规定完成时刻)的先后，从先到后按次序排列，即按预定交货期非减的次序排序3、EDD法（最早交期(EDD)排队策略）零件号零件号 作业时间作业时间 4 4 8 82 2 5 5 9 9 3 3 预定交货期预定交货期 24 24 23 23 8 8 6 6 3232 13 13排序：一一一一一例题1:已知条件如表所示,用EDD法排序，并求平均流程时间,平均等待时间，最大交货延期第11页/共48页2023/2/1612答：最大流程时间：31最大等待时间：22平均流程时间=(5+7+10+18+22+31)615.5平均等待时间=(0+5+7+10+18+22)/6=10.33最大交货延期：0总交货延期：(0+0+0+0+0+0)=0缺点：平均流程时间较长优点：最大交货延期最小加工顺序123456零件号作业时间523849流程时间5710182231等待时间057101822预定交货期6813232432交货延期000000第12页/共48页2023/2/1613课堂练习：用SPT法和EDD法对下列问题排序，并求最大流程时间、平均流程时间、最大交货延期和总交货延期。零件号零件号 作业时间作业时间 8 8 12 125 56 64 41010 预定交货期预定交货期353513134242191925251010第13页/共48页2023/2/1614第三节 流水型作业排序问题流水型作业排序流水型作业排序问题的特点:零件的加工路线相同两台设备的流水型排序问题两台设备的流水型排序问题三台设备的的流水型排序问题m m台设备的流水型排序问题台设备的流水型排序问题车床1到达系统工件的集合离开系统（机器）J1J2J3Jn铣床2磨床m第14页/共48页2023/2/16151、两台设备流水型排序问题及解法2)目标：使完成任务的最大流程时间最短3)方法：约翰逊法 设ti1和ti2分别是零件i在第一台设备和第二台设备上的加工时间。首先：以零件编号为行，以设备编号为列，建立加工时间矩阵。其次：从加工时间矩阵中找出最短的加工时间。第三：若最短的加工时间出现在第一台设备上，则对应的零件尽可能往前排，若最短的时间出现在第二台设备上，则对应的零件尽可能往后排若最短的加工时间有多个，任选一个。最后：若所有工件都已排序，停止，否则，转步骤“第三”。设备零件(1)车床ti1681237(2)铣床ti21195341）问题：n个零件在两台设备上加工，它们的工艺顺序相同第15页/共48页2023/2/16164)例1：已知如表，求加工周期 解：首先进行排序方案一：一一一一方案二；一一一一有两个方案设备零件(1)车床ti1681237(2)铣床ti2119534第16页/共48页2023/2/1617其次计算加工周期:设备零件(1)车床681237(2)铣床119534Fi1计算的根据：一个零件在设备(1)上加工必须等到它前面的零件在设备(1)上加工完成之后才能进行。加工顺序加工顺序(1)(1)(2)(2)ti1ti2Fi1Fi233681274591133629179640342920故:从表中可以看出，最大流程时间(零件的总加工周期）为40Fi2计算的根据：一个零件在设备(2)上加工必须等到该零件在设备(1)上加工完并且设备(2)加工完前一个零件之后才能开始第17页/共48页2023/2/1618加工顺序加工顺序(1)(1)(2)(2)ti1ti2Fi1Fi26118312745896362917141743393426设备零件(1)车床ti1681237(2)铣床ti2119584排序方案1（按照ti2从大到小）：一一一一例2：对下列问题排序，使完成任务的最大流程时间最短.排序方案2（按照约翰逊法）：一一一一加工顺序加工顺序(1)(1)(2)(2)ti1ti2Fi1Fi2386812745911336291791140363122第18页/共48页2023/2/1619约翰逊法算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：（1）将所有aibi的零件按ai值不减的顺序排成一个序列A。（2）将所有aibi的零件按bi值不增的顺序排成一个序列B。（3）将A放到B之前，就构成了最优加工顺序设备零件(1)车床681237(2)铣床119534（1）aibi的零件为 ，按ai值不减的顺序列得：序列A：-解：（2）aibi的零件为，按bi值不增的顺序排列得：序列B：-（3）将A放到B之前得到：-第19页/共48页2023/2/1620约翰逊法约翰逊法，又名约翰逊规则，是作业排序中的一种排序方法。这种方法适用的条件是：n个工件经过二、三台设备（有限台设备）加工，所有工件在有限设备上加工的次序相同。第20页/共48页2023/2/1621 4)使用条件：minti1maxti2:即各零件在第一台设备上的最短加工时间大于或等于各零件在第二台设备上的最长加工时间。或：minti3maxti2：即各零件在第三台设备上的最短加工时间大于或等于各零件在第二台设备上的最长加工时间设备零件A车床158612B铣床3156C磨床410572、三台设备流水型排序问题及解法1）问题：n种零件在三台设备上加工，其工艺顺序均相同。2)目标：加工周期最短，即最大流程时间最小。3)方法：约翰逊扩展法第21页/共48页2023/2/1622第一步：检查各零件在设备(1)、(2)、(3)的加工时间是否满 足使用条件的其中一个，若满足，进行第二步；第二步：将第一台设备和第二台设备加工时间按零件依次相 加，令tG=ti1+ti2第三步：将第三台设备和第二台设备加工时间按零件依次相 加，令tH=ti3+ti2第四步：将得到的tG和tH看作两台假想设备G和H的加工时间第五步；按两台设备的流水型排序问题及解法得出最优排序 此排序就是三台设备的流水型排序的最优解。设备零件A车床158612B铣床3156C磨床410575）步骤第22页/共48页2023/2/1623 按约翰逊法：可得最优解为：一一 一 设备零件A车床158612B铣床3156C磨床41057设备零件G1891118H71110136)例题：已知如表，求加工周期。解：判定是否满足使用条件：minti1=6maxti2=6满足：minti1maxti2可得右下表：第23页/共48页2023/2/1624计算加工周期：设备零件A车床158612B铣床3156C磨床41057最优排序为：一一一加工顺序加工顺序 (1)(1)(2)(2)（3 3）84126209443126ti1ti2Fi1Fi2ti3Fi381126153561075419333848第24页/共48页2023/2/1625课堂练习：对下列流水型问题排序，使完成任务的最大流程时间最短，并求最短加工周期。(1)(2)设备零件(1)车床ti1108642(2)铣床ti213579设备设备 零件零件(1)(1)车床车床 t ti1i17 73 34 48 89 97 7(2)(2)铣床铣床 t ti2i28 85 55 510101 12 2第25页/共48页2023/2/16263、m台设备的流水型排序问题及解法问题：n种零件在m台设备上加工，其工艺顺序相同式中：i表示i零件的斜度指标m为设备数tik为i零件在k设备上的加工时间k=1,2,m设备零件(1)1263(2)8429(3)4582（1）零件的斜率指标法(palmer)第一步：求各零件的斜度指标第26页/共48页2023/2/1627 则:1=-t11+t13=-1+4=3 2=-t21+t23=-2+5=3 3=-t31+t33=-6+8=2 4=-t41+t43=-3+2=-1设备零件(1)1263(2)8429(3)4582k=1,2,m解：对于本例i第二步：按不增的顺序排列零件，即得满意解故排序：一一一或一一一=-ti1+ti3第27页/共48页2023/2/1628（2）关键零件法 第一步：计算各零件的 总加工时间ti，找出加 工时间最长的零件,将其作为关键零件。第二步：除之外，将满足ti1 tim的零件，按ti1的值从小到大把对应的零件排在之前.第三步：除之外，将满足ti1 tim的零件，按tim的值从大到小把对应的零件排在之后.第四步：满足ti1=tim的零件，既可放在的紧前，又可放在的紧后.第五步：如果得到多个排序方案，选优即可设备零件(1)1263(2)8429(3)4582ti13111614tik为i零件在k设备上的加工时间,m为设备数.第28页/共48页2023/2/1629例：已知如下表求使加工周期最短的排序方案 设备零件(1)1263(2)8429(3)4582ti13111614解：计算此例中ti=ti1+ti2+ti3总加工时间最长的为零件，故关键零件选择ti1ti3的零件为，按ti1的值从小到大排在之前，即为一一ti1ti3的零件为，排在之后，即为一故排序为一一一第29页/共48页2023/2/1630（3）CDS法第一步:当L=1,2,m-1时,分别计算加工时间:设备零件(1)1263(2)8429(3)4582tikk=1Ltikk=m+1-Lm和第二步:对于每个L,用上述两组数据构成一个两台设备的流水型排序问题,并用约翰逊法进行排序。第三步:对所得（m-1）个排序比较选优。i i L=1L=1t ti1i11 12 26 63 3t ti3i34 45 58 82 2L=2L=2t ti1i1+t ti2i29 96 68 81212t ti2i2+t ti3i312129 910101111第30页/共48页2023/2/1631i i1 12 23 34 4L=1L=1t ti1i11 12 26 63 3t ti3i34 45 58 82 2L=2L=2t ti1i1+t ti2i29 96 68 81212t ti2i2+t ti3i312129 910101111当L=1时，排序为一一一Fmax=28加工顺序加工顺序 (1)(1)(2)(2)（3 3）112939241513ti1ti2Fi1Fi2ti3Fi318263924458213182628第31页/共48页2023/2/1632加工顺序加工顺序(1)(1)(2)(2)（3 3）212986271810ti1ti2Fi1Fi2ti3Fi324613982584211192329当L=2时，排序为一一一Fmax=29故按故按CDSCDS法排序结果为：法排序结果为：一一一Fmax=28i i1 12 23 34 4L=1L=1t ti1i11 12 26 63 3t ti3i34 45 58 82 2L=2L=2t ti1i1+t ti2i29 96 68 81212t ti2i2+t ti3i312129 910101111第32页/共48页2023/2/1633 设备设备 零件零件 （1 1）4 4 8 82 2 5 5 9 9 （2 2）2 2 3 3 6 6 4 4 1 1 （3 3）5 57 73 38 84 4 （4 4）6 62 216167 78 8课堂练习：分别用零件的斜率指标法、关键零件法、CDS法对下列流水型问题排序，并求加工周期。第33页/共48页2023/2/16344、实际应用例题例：东风汽车维修和上漆公司正在争取一份名为“风暴的合同，这个合同的一个主要要求就是迅速交货，即如果能够将5辆需要维修和喷漆的车在24小时内整修并重新喷漆，这份合同就成交下面是东风汽车维修和上漆公司对这5辆车进行整修和上漆分别所需的作业时间问东风汽车维修和上漆公司能否取得这份名为风暴”的合同工艺要求在喷漆之前必须先进行整修汽车整修时间(小时)喷漆时间(小时)A63B04C52D86E21第34页/共48页2023/2/1635铣床到达系统工件的集合离开系统（机器）J1J2Jk.Jn车床磨床车床离开系统（机器）磨床铣床JiJk单件作业排序问题的特征：零件的加工路线不同第四节 单件作业排序问题1、问题的描述2、排序方法3、优选调度法则第35页/共48页2023/2/16361、问题的描述(1)对于流水型作业排序问题，第K道工序永远在MK上加工，没有必要将工序号与机器号分开.(2)对于单件作业排序问题，要描述一道工序，必须将工件号、工序号和机器号结合在一起。试说明事件(3，4，1)和事件(2，3，3)的含义(3)上图中每个方框表示一个事件。事件的表达方式为：(i，j，k)，i表示工件号，j表示工序号，k表示完成i工件的第j道工序的机器代号。J1,1,铣床J1,2,车床J1,m，磨床J1Jk,1,车床离开系统（机器）Jk,2,磨床Jk,m,铣床Jk离开系统（机器）第36页/共48页2023/2/1637(5)用加工描述矩阵D来描述所有工件的加工每一行描述一个工件的加工，故每一行的工件号相同，每一列的工序号相同(6)加工时间矩阵242354T1,1,11,2,31,3,22,1,32,2,12,3,2D第37页/共48页2023/2/1638单件作业计划种类:q半能动作业计划（Semi-active schedule）各工序都按最早可能开（完）工时间安排的作业计划。q能动作业计划（Active schedule）任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划。q无延迟作业计划（Non-delay schedu1e）没有任何延迟出现的能动作业计划。“延迟”：有工件等待加工时，机器出现空闲，即使这段空闲时间不足于完成一道工序。2两种单件作业排序方法第38页/共48页2023/2/16392 两种单件作业排序方法例：加工描述矩阵和加工时间矩阵如下，分别按下列两种方法进行作业排序(1)最小最早完工时间法（能动作业计划）(2)最小最早开工时间法（无延迟作业计划）1,1,11,2,31,3,22,1,32,2,12,3,2D242354T第39页/共48页2023/2/1640(l)最小最早完工时间法 1,1,11,2,31,3,22,1,32,2,12,3,2D242354T序序列列可排事件可排事件最早可能最早可能开工时间开工时间最早可能最早可能完工时间完工时间最小最早可最小最早可能完工时间能完工时间所需机所需机器器排定事排定事件件1 12 23 34 45 56 61,3,21,3,2M2M2141414141212 1,3,21,3,22,3,22,3,2M2M29 99 912127 78 81,3,21,3,22,3,22,3,22,2,12,2,1M1M18 89 98 87 73 31,3,21,3,22,2,12,2,11,2,31,2,3M3M37 77 78 83 33 31,2,31,2,32,2,12,2,12,1,32,1,3M3M33 36 63 32 20 01,2,31,2,32,1,32,1,31,1,11,1,1M1M12 22 23 30 00 01,1,11,1,12,1,32,1,3排定事件条件第40页/共48页2023/2/1641最小最早完工时间法选择排定事件的条件：（1）属于可排事件（2）符合所需机器（3）最早可能开工时间小于最小最早可能完工时间返回第41页/共48页2023/2/1642按此方法编制出的作业计划叫做：能动作业计划 1,1,11,2,31,3,22,1,32,2,12,3,2D242354T排定事件排定事件1,1,11,1,12,1,32,1,31,2,31,2,32,2,12,2,12,3,22,3,21,3,21,3,2时间机器机器1机器2机器31,1,12,1,31,2,32,2,12,3,21,3,20032 37812148第42页/共48页2023/2/1643(2)最小最早开工时间法1,1,11,2,31,3,22,1,32,2,12,3,2D242354T序序列列可排事件可排事件最早可能最早可能开工时间开工时间最早可能最早可能完工时间完工时间最小最早可最小最早可能开工时间能开工时间所需机所需机器器排定事排定事件件1 12 23 34 45 56 62,3,22,3,2M2M29 913139 9 2,3,22,3,21,3,21,3,2M2M27 79 912127 78 81,3,21,3,22,3,22,3,22,2,12,2,1M1M13 39 98 87 73 31,3,21,3,22,2,12,2,11,2,31,2,3M3M3M1M13 3337 78 83 33 31,2,31,2,32,2,12,2,12,1,32,1,3M3M30 06 63 32 20 01,2,31,2,32,1,32,1,31,1,11,1,1M1M1M3M30 0002 23 30 00 01,1,11,1,12,1,32,1,3排定事件条件第43页/共48页2023/2/1644最小最早开工时间法选择排定事件的条件：（1）属于可排事件（2）符合所需机器（3）最早可能开工时间等于最小最早可能开工时间返回第44页/共48页2023/2/1645时间机器机器1机器2机器31,1,11,2,31,3,22,1,32,2,12,3,2D242354T排定事件排定事件1,1,11,1,12,1,32,1,31,2,31,2,32,2,12,2,11,3,21,3,22,3,22,3,2按此方法编制出的作业计划叫做：无延迟作业计划1,1,12,1,31,2,32,2,12,3,21,3,20032 3789137第45页/共48页2023/2/16463 优选调度法则v SPT：优先选择加工时间最短的事件v PCFS：优先选择最早进入可排事件集合的事件v EDD：优先选择完工期限紧的事件v MWKR：优先选择余下加工时间最长的事件v LWKR：优先选择余下加工时间最小的事件v MOPNR：优先选择余下工序数最多的事件v RANDOM：随机地挑选一个第46页/共48页2023/2/1647第五节 生产作业控制1.实行生产作业控制的原因2.实施生产作业控制的条件3.生产作业控制的内容n预先控制n生产过程控制n生产调度 4.不同生产类型生产控制的特点第47页/共48页2023/2/16授人以鱼不如授人以渔48感谢您的观看！第48页/共48页
