(本科）第9章 制造业作业计划与控制.ppt

《(本科）第9章 制造业作业计划与控制.ppt》由会员分享，可在线阅读，更多相关《(本科）第9章 制造业作业计划与控制.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程主讲人：第9章 制造业作业计划与控制生产与运作管理生产与运作管理Production & Operations Management华中科技大学管理学院The School of Management，HUST陈荣秋 马士华Rongqiu Chen and Shihua Ma华中科大管理学院陈荣秋马士华2第9章 制造业作业计划与控制Scheduling and Controlling for Manufacturing9.1 作业计划问题的基本概念9.2 流水作业排序问题9.3 单件作业的排序问题9.4 生产作业控制 华中科大管理学院陈荣秋马士华39.1作业计划问题的基本概念编制作业计划要

2、解决的问题n编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。n由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。有关名词术语9.1.2 假设条件与符号说明华中科大管理学院陈荣秋马士华4 9.1.1 有关的名词术语编制作业计划或排程(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)赶工(Expediting) “调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动，属于计划范畴。华中科大管理学院陈荣

3、秋马士华5有关名词术语（续）n“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”。n“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件。n“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束 。n“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题。华中科大管理学院陈荣秋马士华69.1.2 假设条件与符号说明假设条件n一个工件不能同时在几台不同的机器上加工。n工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序

4、加工。n不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。n每道工序只在一台机器上完成。n工件数、机器数和加工时间已知，加工时间与加工顺序无关。n每台机器同时只能加工一个工件。华中科大管理学院陈荣秋马士华79.1.2 假设条件与符号说明（续）符号说明nJi工件i，i1,2,n。nMj机器j，j1,2,m。npijJi在Mj上的加工时间，Ji的总加工时间为Pipij nriJi的到达时间，或准备就绪时间，指Ji从外部进入车间，可以开始加工的最早时间。ndiJi的完工期限。nCiJi的完工时间, Ciri(wij+ pij) = ri+Wi+Pi.nCmax最长完工

5、时间, Cmaxmax Ci .华中科大管理学院陈荣秋马士华89.1.2 假设条件与符号说明（续）FiJi的流程时间，即工件在车间的实际停留时间, FiCI-riWi+Pi.Fmax最长流程时间，Fmaxmax Fi .Li工件延迟时间，LiCidi riPi.+ Widi (Pi.+ Wi)(di -ri)Fiai.当Li0 (正延迟)，说明Ji的实际完工时间超过了完工期限； 当Li0(负延迟)，说明Ji提前完工；当Li0(零延迟)，Ji按期完工。Lmax最长延迟时间，Lmaxmax Li . 华中科大管理学院陈荣秋马士华99.2 流水作业排序问题流水车间(Flow shop):工件的加工路

6、线都一致，典型的如流水线n9.2.1 最长流程时间的计算 n9.2.2 两台机器排序问题的最优算法 n9.2.3 多台机器排序问题的启发式算法n相同零件、不同移动方式下加工周期的计算Work Center #1Work Center #2Output华中科大管理学院陈荣秋马士华109.2.1 最长流程时间的计算工件代号i 1 4 6 3 5 2Pi1 4 5 3 4 8 6Pi2 3 9 1 3 7 5Pi3 7 6 8 2 5 9Pi4 5 6 3 9 2 44 9 12 16 24 307 18 19 22 31 3614 24 32 34 39 4819 30 35 44 46 52华中

7、科大管理学院陈荣秋马士华119.2.2 两台机器排序问题的 最优算法约翰森法则n如果Min(ai, bj) pim 则按pim不增的顺序排成一个序列Sb;n3. 顺序（Sa,C,Sb）即为所求顺序。华中科大管理学院陈荣秋马士华179.2.3 多台机器排序问题的 启发式算法（续） 举例工件i 1 2 3 4Pi1 2 1 6 3Pi2 4 8 2 9Pi3 5 4 8 211 13 16 14CSa (2,1)Sb(4)所求顺序：（2,1,3,4）华中科大管理学院陈荣秋马士华189.2.4 相同零件不同移动方 式下加工周期的计算当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型

8、的移动方式n顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工n平行移动方式：单个零件加工完成后，立即移动到下道工序加工n平行顺序移动方式：两者混合华中科大管理学院陈荣秋马士华19顺序移动方式时间M1t2t1t3t4t4工序M2M3M4T顺O华中科大管理学院陈荣秋马士华20 设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 （分钟/件），i=1.2n. 则该批零件的加工周期为： 121.mimiTntntntnt顺序移动方式（续）华中科大管理学院陈荣秋马士华21平行移动方式时间M1工序M2M3M4

9、T平Ot2t1t3t4华中科大管理学院陈荣秋马士华22平行移动方式（续）零件平行移动的加工周期 为： T平1(1)miLiTtnt平Lt为最长单件工序时间华中科大管理学院陈荣秋马士华23平行顺序移动方式 特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：时间M1工序M2M3M4T平顺Ot1t2t3t4华中科大管理学院陈荣秋马士华24平行顺序移动方式（续）平行顺序移动加工周期计算 111(1)mmiiiiTtnt平 顺=n华中科大管理学院陈荣秋马士华259.3 单件作业排序问题9.3.1 任务分配问题9.3.2 单件作业排序问题的描述9.3.3 优先派工准则9.3.4

10、求解一般n/m/G/Fmax问题的启发式方法华中科大管理学院陈荣秋马士华269.3.1 任务分配问题M1 M2 M3 M4 J1J2J3J49 7 3 57 8 12 114 6 8 76 11 13 10有4个零件可以分配给4台机器加工，其所需加工时间如图所示。即，零件1分配给机器1加工，需要9个时间单位；分配给机器2加工 ，需要7个时间单位；分配给机器3加工，需要3个时间单位；分配给机器4加工，需要5个时间单位，等等。如果有n个零件要分配给n台机器加工，则有n!种不同的分配方案。通过匈牙利算法可以较方便地找到最优分配方案。华中科大管理学院陈荣秋马士华279.3.1 任务分配问题（续）匈牙利

11、算法n(1)从加工时间(费用)矩阵每一行所有元素减去该行最小的元素，使每行至少出现一个零元素。n(2)从实施第(1)步得到的矩阵中的每一列所有元素减去该列最小的元素，使每列至少出现一个零元素。n(3)从实施第(2)步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，如果线条数等于矩阵的行数，则已找到最优矩阵，转第(6)步；否则，转第(4)步。华中科大管理学院陈荣秋马士华289.3.1 任务分配问题（续）n(4)从矩阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个最小数加到直线交叉的元素上，其余元素不变。n(5)重复步骤(3)和步骤(4)，直到获得最优矩阵。n（6）从仅有一个零的行或列开始

12、，找出零元素对应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素。零元素对应的就是最优分配方案。华中科大管理学院陈荣秋马士华29M1 M2 M3 M4J1J2J3J49 7 3 5 37 8 12 11 74 6 8 7 46 11 13 10 6 (a)M1 M2 M3 M4J1 J2J3J46 4 0 20 1 5 40 2 4 30 5 7 40 1 0 2 (b)9.3.1 任务分配问题（续）行最小数列最小数华中科大管理学院陈荣秋马士华30M1 M2 M3 M4J1J2J3J4 3 0 00 0 5 20 1 4 10 4 7 2 (C)M1 M2 M3 M4J1

13、 J2J3J4 3 0 0 0 5 20 0 3 00 3 6 1(d)9.3.1 任务分配问题（续）华中科大管理学院陈荣秋马士华31M1 M2 M3 M4J1J2J3J47 3 0 01 0 5 30 0 3 00 3 6 1 ()M1 M2 M3 M4J1 J2J3J4 3 0 0 0 5 30 0 3 00 3 6 1()9.3.1 任务分配问题（续）华中科大管理学院陈荣秋马士华329.3.2 单件作业排序问题的描述D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5加工描述矩阵D和加工时间矩阵T对应华中科大管理学院陈荣秋马士华339.3.3

14、优先派工准则按什么样的法则来选择可安排的工序，对作业计划的优劣有很大影响。迄今，人们已提出了100多个优先派工法则，下面列出4个进行比较：FCFS(First Come First Served)法则优先选择最早进入可排工序集合的工件。SPT(Shortest Processing Time)法则优先选择加工时间最短的工序。EDD(Earliest Due Date)法则优先选择完工期限紧的工件。LPT(Longest Processing Time )法则优先选择加工时间最长的工件。华中科大管理学院陈荣秋马士华349.3.3 优先派工准则（续）例：有6项任务A，B，C，D，E ，F要完成。每

15、项任务所需时间和完工期限如下表所示。分别按（1）FCFS，（2）SPT，（3）EDD和（4）LPT法则，来确定完成任务的先后次序及相应的指标。任务所需时间（天）完工期限（天）ABCDEF284105127164171518华中科大管理学院陈荣秋马士华359.3.3 优先派工准则（续）如果任务下达的顺序是A-B-C-D-E-F，按FCFS法则，任务的流程时间就是每件任务的等待时间加上加工时间。任务次序加工时间流程时间完工期限延迟时间ABCDEF28410512210142429417164171518001071423累计4112054华中科大管理学院陈荣秋马士华36 9.3.3 优先派工准则（

16、续）按照FCFS法则，可以得到下列结果：n 平均流程时间=累计流程时间/任务数=120/6=20天n 利用率=累计加工时间/累计流程时间=41/120=34.2%n 系统中平均在制品数量=累计流程时间/累计加工时间=120/41=2.93件任务n 平均延迟时间=延迟时间总和/任务数 =54/6=9天华中科大管理学院陈荣秋马士华379.3.3 优先派工准则（续）按SPT法则，处理任务的的流程时间就是每件任务的等待时间加上加工时间。 任务次序加工时间流程时间完工期限延迟时间ACEBDF245810122611192941741516171802031223累计4110840华中科大管理学院陈荣秋马

17、士华389.3.3 优先派工准则（续）按照SPT法则，得到下列结果： 平均流程时间=108/6=18天 利用率=41/108=38% 系统中平均在制品数量=108/41=2.63件任务 平均延迟时间=40/6=6.67天华中科大管理学院陈荣秋马士华399.3.3 优先派工准则（续）按EDD法则，处理任务的先后次序是C-A-E-B-D-F，如下表所示。 任务次序加工时间流程时间完工期限延迟时间CAEBDF425810124611192941471516171800031223累计4111038华中科大管理学院陈荣秋马士华409.3.3 优先派工准则（续）按照EDD法则，得到下列结果：n 平均流程

18、时间=110/6=18.3天n 利用率=41/110=37.3%n 系统中平均在制品数量=110/41=2.68件任务n 任务平均延迟时间=38/6=6.33天华中科大管理学院陈荣秋马士华419.3.3 优先派工准则（续）按LPT法则，处理任务的先后次序是F-D-B-E-C-A，如下表所示。 任务次序加工时间流程时间完工期限延迟时间FDBECA12108 54212223035394118171615470514203534累计41179108华中科大管理学院陈荣秋马士华429.3.3 优先派工准则（续）按照LPT法则，得到下列结果：n 平均流程时间=179/6=29.8天n 利用率=41/1

19、79=22.9%n 系统中平均在制品数量=179/41=4.37件任务n 任务平均延迟时间=108/6=18天华中科大管理学院陈荣秋马士华439.3.3 优先派工准则（续）方法平均流程时间（天）利用率（%）平均在制品数平均延迟时间（天）FCFSSPTEDDLPT201818.329.834.23837.322.92.932.632.684.3796.676.3318（1）按照LPT法则进行作业排序，各项指标最差。（2）按SPT法则可使工件的平均流程时间最短，使平均在制品数量最少。（3）FCFS法则对工件较公平，这一点在对顾客服务中尤其重要，但在多数情况下都不具有优势。（4）EDD法则可使工件的

20、平均延迟时间最小，其它指标也不错。华中科大管理学院陈荣秋马士华44求解一般n/m/G/Fmax问题的启发式方法（1）两种作业计划的构成n能动作业计划n无延迟作业计划（2）三类启发式算法n运用优先派工法则n随即抽样法n概率调度法华中科大管理学院陈荣秋马士华45（1）两种作业计划的构成符号说明n每安排一道工序称为一“步”nSt:t步之前已排序工序构成的部分作业计划；nOt:t步可排序工序的集合；nTk为Ot中工序Ok的最早可能开始时间；nTk为Ot中工序Ok的最早可能完成时间。华中科大管理学院陈荣秋马士华46（1） 两种作业计划的构成（续）能动作业计划的构成n（1）设t=1,S1为空集，O1为各工

21、件第一道工序的集合。n（2）求T* = minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。n（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj T* 。n（4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot ，使t=t+1.n（5）若还有未安排的工序，转步骤（2）；否则，停止。华中科大管理学院陈荣秋马士华47能动作业计划的构成tOtTkTkT*M*Oj11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,1

22、51,3,22,3,2778128M21,3,262,3,281313M22,3,2华中科大管理学院陈荣秋马士华48能动作业计划的甘特图2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70时间时间机器 M1M2M3华中科大管理学院陈荣秋马士华499.3.2 两种作业计划的构成（续）无延迟作业计划的构成n（1）设t=1,S1为空集，O1为各工件第一道工序的集合。n（2）求T* = minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。n（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T* 。n（4）将选定的工序Oj

23、放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot ，使t=t+1.n（5）若还有未安排的工序，转步骤（2）；否则，停止。华中科大管理学院陈荣秋马士华50无延迟作业计划的构成tOtTkTkT*M*Oj11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,32,2,1337733M3M11,2,341,3,22,2,173873M12,2,151,3,22,3,27781277M2M22,3,261,3,2121312M21,3,2华中科大管理学院陈荣秋马士华51无延迟作业计划的甘特图2,3,21,1,1 2,2,12,1,3 1,2,3

24、 3 7 7 12 13 2 3 70时间时间机器 M1M2M31,3,2华中科大管理学院陈荣秋马士华52（2）三类启发式算法优先调度法则n构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划n计算量小n已经提出100多种优先调度法则华中科大管理学院陈荣秋马士华53优先调度法则nFCFS（first come, first served）选择最早进入可排序集合的工序nSPT( shortest processing time）选择加工时间最短的工序nEDD（earliest due date）选择完工期限最紧的工序nSCR(s

25、mallest critical ratio)选择临界比最小的工件nMWKR(most work remaining)选择余下加工时间最长的工件nLWKR(least work remaining)选择余下加工时间最短的工件nMOPNR(most operations remaining)选择余下工序数最多的工件nRANDOM 随机挑选一个工件nRushTop Priority华中科大管理学院陈荣秋马士华54（2）三类启发式算法（续）随机抽样法n从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。概率调度法n将优先调度法则与随机抽样法结合n对不同工件将优先调度法则分配不同的挑选概

26、率，效果较好华中科大管理学院陈荣秋马士华559.4 生产作业控制实行生产作业控制的原因生产环境的变化计划的失误执行的原因：执行过程中，有可能会出现操作人员执行不力、效率不高和工作态度等现象，造成计划完不成执行因素的影响华中科大管理学院陈荣秋马士华569.4 生产作业控制（续） 生产作业控制的程序制定生产作业监控体系监控实际生产过程 评估偏差情况 采取纠偏措施华中科大管理学院陈荣秋马士华579.4 生产作业控制（续） 生产作业控制的功能为每个车间的工单指派优先级维护车间在制品数量将车间工单信息传送到相应办公室提供实际产出数据来为能力控制服务根据车间工单对机位的要求，为在制品库存管理提供数量信息测

27、量人员和设备的效率、利用率和产量。华中科大管理学院陈荣秋马士华58华中科大管理学院陈荣秋马士华599.4 生产作业控制（续） 生产作业控制的主要工具实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：n调度单n日报、月报n例外报告、异常报告n输入/输出（Input/output control，I/O）报告华中科大管理学院陈荣秋马士华609.4 生产作业控制（续） 漏斗模型模型介绍德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。漏斗模型的基本原则：工作中心的输入永

28、远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。华中科大管理学院陈荣秋马士华61注：曲线图的垂直段表示某天到达或完成的一个或多个工件之间所包含的工作量；水平段表示相邻两个到达或完成的任务之间的时间间隔。如果运输时间不变，输入曲线与上道工序的输出曲线相对应。华中科大管理学院陈荣秋马士华629.4 生产作业控制（续） 控制规则在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存/平均通过时间实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：n若希望保持在制品库存量，可暂时增加或减少输入。n若希望改变在制品库存量，可暂时增加或减少输入。n若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。n要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。华中科大管理学院陈荣秋马士华63谢谢！华中科大管理学院陈荣秋马士华64