第4讲-制造业作业计划与控制可编辑修改课件.ppt

1、生产运作管理生产运作管理 Production&Operations Management 青岛理工大学（临沂）冯海侠 2016年5月 1 第4章 制造业作业计划与控制Scheduling and Controlling for Manufacturing 4.1 作业计划问题的基本概念 4.2 流水车间作业计划问题 4.3 单件车间作业计划问题 4.4 生产作业控制 2 4.1作业计划问题的基本概念 4.1.1 生产作业计划概述 4.1.2 有关的名词术语 4.1.3 假设条件与符号说明 4.1.4 排序问题的分类和表示法 3 4.1.1生产作业计划概述 生产作业计划是企业年度生产计划和MR

2、P输出的具体执行计划。它根据年度生产计划的要求对每个生产单位（车间、工段、班组），在每个具体的时期（月、旬、周、日、轮班、小时等）内的生产任务作出详细的安排并规定实现的方法，从而保证企业按数量、品种、质量、交货期的要求全面完成生产计划。4?生产作业计划的内容生产作业计划的内容 生产作业计划的主要任务是将主生产计划或MRP中零部件的投入出产计划细化，他是MRP的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。5 生产作业计划工作由作业计划编制与作业计划控制两部分组成。作业计划编制：包括制定期量标准、开展生产运作能力核算与

3、平衡、编制各种形式的生产作业计划等。作业计划控制包括生产运作调度、生产运作作业统计与分析等内容。6 生产作业计划的作用?保证主生产计划规定的生产运作任务的完成。?保证企业获取更好的经济效益。7 4.1.2 有关的名词术语 排序：排序：就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力分配给不同工作任务，使预定目标最优化的问题。派工派工：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人。赶工赶工：是在实际进度已经落后于计划进度时采取的行动。调度调度：是作业计划编制以后，实行生产控制的

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

5、当一个零件一旦开始加工，必须一直进行到完工，不得中途停止插入其它零件。每道工序只在一台机器上完成。零件数、机器数和加工时间已知。每台机器同时只能加工一个零件。10 4.1.3 假设条件与符号说明（续）?Ji 零件i，i1,2,n。Mj机器j，j1,2,m。pij一Ji在Mj上的加工时间，Ji的总加工时间为Pipij ri一Ji的到达时间，指Ji从外部进入车间，可以开始加工的最早时间。di一Ji的完工期限。Ci一Ji的完工时间,Ciri(wij+pij)=ri+Wi+Pi.Cmax最长完工时间,Cmaxmax Ci.11 4.1.3 假设条件与符号说明（续）?Fi一Ji的流程时间，即零件在车间的

6、实际停留时间,FiCi-riWi+Pi.Fmax最长流程时间，Fmaxmax Fi.Li零件的延迟时间Li=Ci-di 当Li0(正延迟)，说明Ji的实际完工时间超过了完工期限；当Li0(负延迟)，说明Ji提前完工；当Li0(零延迟)，Ji按期完工。Lmax最长延迟时间，Lmaxmax Li.12 4.1.4 排序问题的分类和表示法 按机器 单机排序问题和多机排序问题?多机：单件作业排序与流水作业排序 按工件到达情况?静态和动态 单目标排序问题和多目标排序问题 按目标函数?13 按参数的性质按参数的性质 确定型排序问题确定型排序问题（加工时间和其他有关参数是已知的确定量）随机型排序问题随机型排

7、序问题（加工时间和有关参数为随机变量）四参数表示法（康韦（四参数表示法（康韦（Conway）：）：n/m/A/B 其中，其中，n为零件数，为零件数，m为机器数，为机器数，A为车间类型，若标以为车间类型，若标以F，则代，则代表流水作业排序问题，若标以表流水作业排序问题，若标以P，则代表流水作业排列排序问题，则代表流水作业排列排序问题，若标以若标以G，则表示一般单件作业排序问题。，则表示一般单件作业排序问题。B为目标函数，通常为目标函数，通常是使其值最小。是使其值最小。例如：例如：n/3/P/Cmax表示表示n个零件经个零件经3台机器加工的流水作业排列排台机器加工的流水作业排列排序问题，目标函数是

8、使最长完工时间序问题，目标函数是使最长完工时间Cmax最短最短。14 4.2 流水作业排序问题 流水车间(Flow shop):工件的加工路线都一致，典型的如流水线 4.2.1 加工周期的计算 4.2.2 两台机器排序问题的最优算法 4.2.3 一般n/m/p/Fmax排序问题的启发式算法 4.2.4 相同零件、不同移动方式下加工周期 Work Center#1 Work Center#2 Output 15 4.2.1 加工周期的计算 n个不同的零件要按相同的加工路线经过 m台机器加工，目标是使这批零件的加工周期最短-n/m/P/Fmax 加工周期加工周期又称为最长流程时间，它是从第一个零件

9、在第一台机器开始加工时起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。假设所有零件的到达时间都为零（ri=0,i=1,2,n)，则Fmax等于排在末位加工的零件在车间的停留时间，也等于一批零件的最长完工时间 Cmax 16 设n个零件的加工顺序为S=（S1，S2，,Sn），其中Si为排第i位加工的零件的代号。以CkSi表示零件Si在机器Mk上的完工时间，P Sik表示零件Si在Mk上的加工时间，k=1,2,m;i=1,2,n,则CkSi可按以下公式计算 C1Si=C1Si-1+P Si1 CkSi=max C(k-1)Si,CkSi-1 +P Sik k=2,3,m;i=1,2,

10、n CmSn,即为最长流程时间Fmax 17 4.2.1 加工周期的计算 有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序 S=（1,4,6,3,5,2）加工时，求Fmax 工件代号i 1 2 3 4 5 6 Pi1 4 6 4 5 8 3 Pi2 3 5 3 9 7 1 Pi3 7 9 2 6 5 8 Pi4 5 4 9 6 2 3 18 4.2.1 加工周期的计算 工件代号i 1 4 6 3 5 2 Pi1 4 5 3 4 8 6 Pi3 7 6 8 2 5 9 Pi4 5 6 3 9 2 4 4 9 12 16 24 30 Pi2 3 9 1 3 7 5 7 18 19 2

11、2 31 36 14 24 32 34 39 48 19 30 35 44 46 52 19 4.2.2 两台机器排序问题的最优算法 对于n个零件经过两台机器加工，要使加工周期最短的流水作业排序问题，即n/2/F/Fmax问题，约翰逊于1954年提出了一个最优算法，即著名的Johnson算法。为叙述方便，以ai表示零件Ji在机器M1上的加工时间，以bi表示零件Ji在机器M2上的加工时间，每个零件都按M1 M2的路线加工。20 4.2.2 两台机器排序问题的最优算法 约翰逊法则?如果Min(ai,bj)pim 则按pim不增的顺序排成一个序列 Sb;3.顺序（Sa,C,Sb）即为所求顺序。27

12、4.2.3 多台机器排序问题的 启发式算C 法（续）举例 工件i 1 2 3 4 Pi1 2 1 6 3 Sa(2,1)Sb(4)所求顺序：11 13 16 14（2,1,3,4）Pi2 4 8 2 9 Pi3 5 4 8 2 28 Palmer（帕尔默）法 1965年，帕尔默（D.S.Palmer)对流水作业排序问题提出了按斜度指标排列工件的启发式算法，该算法先定义工件的斜度指标，然后将各工件按其斜度指标不增进行排序。零件的斜度指标可按下式计算：mm+1l i=?(k-)Pik,k=1,2,.n.2k=1式中，m为机器数，Pik为零件i在机器Mk上的加工时间。按照各零件 l i不增的顺序排列

13、零件，可得出令人满意的加工顺序。29 例3：有一个4/3/F/Fmax问题，其加工时间如下表所示，试用Palmer法求解。工件i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 30 CDS法 坎贝尔（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一个启发式算法，简称CDS法。他们把Johnson算法用于一般的n/m/F/Fmax问题，得到（m-1）个加工顺序，取其中的优者。具体的做法是：对加工时间 lmpik,l=1,2,.,m-1;邋pik,k=1k=m+1-l根据Johnson算法可以求得一个排序，共可得到 m-1个排序，

14、从中选优。l取不同值，对每一组值，看成是分别在两注：当 个机器上的加工时间。31 4.3 单件车间作业计划问题 4.3.1 任务分配问题 4.3.2 排序问题的描述 4.3.3 两种作业计划的构成 4.3.4 求解一般n/m/G/Fmax问题的启发式方法 32 4.3.1 任务分配问题 把n项任务分给n台机器加工，有n!方案 匈牙利算法?(1)从加工时间(费用)矩阵每一行所有元素减去该行最小的元素，使每行至少出现一个零元素。(2)从实施第(1)步得到的矩阵中的每一列所有元素减去该列最小的元素，使每列至少出现一个零元素。(3)从实施第(2)步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，如果线

15、条数等于矩阵的行数，则已找到最优矩阵，转第(6)步；否则，转第(4)步。(4)从矩阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个最小数加到直线交叉的元素上，其余元素不变。(5)重复步骤(3)和步骤(4)，直到获得最优矩阵。（6）从仅有一个零的行或列开始，找出零元素对应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素。零元素对应的就是最优分配方案。33 例例4-3-1有如下任务分配问题有如下任务分配问题:34 求解过程如下表所示：求解过程如下表所示：35 e 36 零件零件1由机器由机器M3加工，零件加工，零件2由机器由机器M2加工，加工，零件零件3由机器由机器M

16、4加工，零件加工，零件4由机器由机器M1加工，加工，可使总加工时间最少。可使总加工时间最少。37 4.3.2 单件作业排序问题的描述 对于一般单件作业排序问题，要描述一道工序，要用三个参数：i,j,和k。i表示工件的代号，j表示工序，k表示完成工件i的第j道工序的机器的代号。用（i,j,k）表示工件i的第j道工序是在机器k上进行加工的。于是可以用加工描述矩阵的形式来描述所有工件的加工。38 4.3.2 单件作业排序问题的描述 加工描述矩阵D和加工时间矩阵T对应 1,1,1 1,2,3 1,3,2 D=2,1,3 2,2,1 2,3,2 2 4 1 3 4 5 T=39 4.3.3一般n/m/G

17、/Fmax问题的启发式算法 两种作业计划的构成两种作业计划的构成 半能动作业计划：半能动作业计划：各工序都按最早可能开（完）工时间安排的作业计划；能动作业计划能动作业计划：任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划；无延迟作业计划无延迟作业计划：没有任何延迟出现的能动作业计划。延迟：延迟：指有工件等待加工时，机器出现空闲，既使这段空闲时间不足以完成一道工序。40 4.3.3 两种作业计划的构成（续）符号说明?每安排一道工序称为一“步”St:t步之前已排序工序构成的部分作业计划；Ot:t步可排序工序的集合；Tk为Ot中工序Ok的最早可能开始时间；Tk为Ot中工序Ok的最

18、早可能完成时间。41 4.3.3 两种作业计划的构成（续）能动作业计划的构成步骤?（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）；否则，停止。42 能动作业计划的构成 t 1 2 Ot 1,1,1 2,1,3 1,2,3 2,1,3 Tk 0 0 2 0 Tk 2 3 6 3 T*2 3 M*M1 M

19、3 Oj 1,1,1 2,1,3 3 4 1,2,3 2,2,1 1,3,2 2,2,1 3 3 7 3 7 7 8 7 7 7 M3 M1 M1 1,2,3 2,2,1 5 6 1,3,2 2,3,2 2,3,2 7 7 8 8 12 13 8 13 M2 M2 1,3,2 2,3,2 43 能动作业计划的甘特图 机器 M1 1,1,1 2,2,1 2 3 7 M2 1,3,2 2,3,2 7 8 13 M3 0 2,1,3 1,2,3 3 7 时间时间 44 4.3.3 两种作业计划的构成（续）无延迟作业计划的构成无延迟作业计划的构成?（1）设t=1,S1为空集，O1为各工件第一道工序的集

20、合。（2）求T*=minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T*。（4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。45 无延迟作业计划的构成 t 1 2 Ot 1,1,1 2,1,3 1,2,3 2,1,3 Tk 0 0 2 0 Tk 2 3 6 3 T*0 0 0 M*M1 M3 M3 Oj 1,1,1 2,1,3 3 4 1,2,3 2,2,1 1,3,2 2,2,1 3 3 7 3 7 7 8 7 3

21、 3 3 M3 M1 M1 1,2,3 2,2,1 5 6 1,3,2 2,3,2 1,3,2 7 7 12 8 12 13 7 7 12 M2 M2 M2 2,3,2 1,3,2 46 无延迟作业计划的甘特图 机器 M1 1,1,1 2,2,1 2 3 7 M2 2,3,2 1,3,2 7 12 M3 0 2,1,3 1,2,3 3 7 时间时间 47 4.3.4 三类启发式算法（1）优先调度法则?构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划 更能符合计划编制者的要求 计算量小 已经提出100多种优先调度法则 48

22、优先调度法则?FCFS（first come,first served）优先选择最早进入可排序集合的工序 SPT(shortest processing time）优先选择加工时间最短的工序 EDD（earliest due date）优先选择完工期限紧的工序 SCR(smallest critical ratio)选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比）MWKR(most work remaining)优先选择余下加工时间最长的工件 LWKR(least work remaining)优先选择余下加工时间最短的工件 MOPNR(most operations r

23、emaining)优先选择余下工序数最多的工件 49?RANDOM 随机挑选一个工件 按SPT法则，可使工件的平均流程时间最短，从而减少在制品库存量；FCFS法则来自排队论，它对工件较公平；EDD法则可使工件最大延误时间最小；SCR法则也是保证工件延误最小的法则；MWKR与MOPNR法则类似使不同工作量的工件的完工时间尽量接近；LWKR法则使工作量小的工件尽快完成；50 在应用优先调度法则时，只要将构成能动作业计划的第3步修改为：对Ot中需要M*加工，且TjT*的工序，按预定的优先调度法则确定一个进入St的工序。对于构成无延迟作业计划的第3步修改为：对Ot中需要M*加工，且Tj=T*的工序，按

24、预定的优先调度法则确定一个进入St的工序。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。有时应用一个优先法则还不能惟一地确定一道应挑选的工序，需要多个优先调度法则的有序组合。譬如，SPT+MWKR+RANDOM 51 4.3.3 三类启发式算法（续）（2）随机抽样法?从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。介于两个极端之间 效果与样本大小和母体有关 比用优先调度法则得到的结果一般要好一些，但计算量要大一些 从无延迟作业计划母体抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好 将优先调度法则与随机抽

25、样法结合 对不同工件按优先调度法则分配不同的挑选概率，效果较好（3）概率调度法?52 4.4 生产作业控制 4.4.1 实行生产作业控制的原因和条件 4.4.2 不同生产类型生产控制的特点 4.4.3 利用“漏斗模型”进行生产控制 53 4.4.1 实行生产作业控制的原因和条件 原因?加工时间估计不准确 随机因素的影响 加工路线的多样性 企业环境的动态性 条件?要有控制标准 取得实际进度偏离计划的信息 能够采取纠正行动 54 生产作业控制的程序?制定生产作业监控体系?监控实际生产过程?评估偏差情况?采取纠偏措施 55 生产作业控制的功能?为每个车间的工单指派优先级?维护车间在制品数量?将车间工

26、单信息传送到相应办公室?提供实际产出数据来为能力控制服务?根据车间工单对机位的要求，为在制品库存管理提供数量信息?测量人员和设备的效率、利用率和产量。56 4.4.2 不同生产类型生产控制的特点 不同生产类型的特点不同生产类型的特点 特点 零件的流动 瓶颈 设备 调整准备费用 工人操作 工人工作的范围 工作节奏的控制 在制品库存 产品库存 供应商 作业计划编制 单件小批生产 没有主要的流动路线 经常变动 通用设备，有柔性 低 多 宽 工人自己和工长 高 很少 经常变化 不确定性高，变化大 大量大批生产 单一的流动路线 稳定 高效专用设备 高 少 窄 由机器和工艺过程 低 较高 稳定 不确定性低

27、，变化小 57 4.4.2 不同生产类型生产控制的特点（续）移动 时间 排队 时间 调整准备时间 加工 待运 时间 时间 零件加工提前期的构成 单件小批生产，排队时间是主要的，通过输入/输出控制排队队长 大量大批生产，控制问题较简单，主要是调整工作班次、工作时间和工人数量 58 生产作业控制的主要工具?实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：?调度单?日报、月报?例外报告、异常报告?输入/输出（Input/output control，I/O）报告 59 4.4.3 利用“漏斗模型”进行生产控制 德国汉诺威大学的贝克特（Bechte）和温

28、道尔（Wiendall）等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。60 到达的任务到达的任务 在制品在制品 计划能力计划能力 实际能力实际能力 完成的任务完成的任务 61 注：曲线图的垂直段表示某天到达或完成的一个或多个工件之间所包含的工作量；水平段表示相邻两个到达或完成的任务之间的时间间隔。如果运输时间不变，输入曲线与上道工序的输出曲线相对应。62 4.4.3 利用“漏斗模型”进行生产控

29、制(续)在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存/平均通过时间 实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：若希望保持在制品库存稳定，就要使单位时间内的平均输入等于平均输出。?若希望改变在制品库存量，可暂时增加或减少输入。?若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。?要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。漏斗模型适合于多品种中小批量生产系统的控制。?63 本章习题：思考题：1、作业计划解决什么问题？请举例说明。2、

30、排序、编制作业计划、派工、赶工、调度、控制等术语的含义及其相互关系。3、解释加工路线和加工顺序。4、说明能动作业计划和无延迟作业计划的关系。5、漏斗模型的基本原理是什么？它在生产控制中的用途如何？64 判断题：1.排序是指安排工件在机器上的加工顺序。排序是指安排工件在机器上的加工顺序。2.按照按照JohnsonJohnson法则可得到多个加工顺序，则应从中取最法则可得到多个加工顺序，则应从中取最优者。优者。3.3.派工属于通常所说的调度范围。派工属于通常所说的调度范围。4 4、流水车间排序问题是指所有工件的加工顺序都相同的、流水车间排序问题是指所有工件的加工顺序都相同的排序问题。排序问题。5

31、5、列车时刻表属于作业计划。、列车时刻表属于作业计划。6 6、Johnson算法应用于只存在一台机器或者一个加工工段的情形。7、n/m/A/B中A表示车间类型，B表示目标函数。8、确定加工路线是排序要解决的主要问题。9、排序与编制作业计划是同义词。65 选择题 1、下列哪项不是排序的优先调度法则？A 优先选择余下加工时间最长的工件 B优先选择加工时间最短的工件 C优先选择临界比最小的工件 D优先选择临界比最大的工件 66 2、一个工件剩下5天加工时间，今天是这个月的10号。如果这个工件14号到期，临界比是多少？A.0.2 B.4 C.1 D.0.8 3、任务分配情况下，5个工件分派到5台机器上

32、有多少种不同方法？A.5 B.25 C.120 D.125 67 4.下列哪项可将生产计划任务落实到操作工人身上？A.流程设计 B.能力计划 C.生产大纲 D.排序和车间生产作业计划 5.与流水车间排序不直接相关的是：A.加工描述矩阵 B.加工时间矩阵 C.加工顺序矩阵 D.“漏斗”模型 68 计算题 1.有5件任务都需要两步操作（先 1后2）来完成，下表给出了加工时间。任务 操作1所需时间（小时）操作2所需时间（小时）A B C D E 3.0 2.0 1.0 3.0 3.5 1.2 2.5 1.6 3.0 1.5 根据Johnson算法安排工作顺序，并计算最短加工周期。69 2、有一个4/

33、4/P/Fmax问题，其加工时间如下表所示，用Palmer法求解。i 1 2 3 4 Pi1 1 9 5 4 Pi2 5 7 6 3 Pi3 4 6 3 5 Pi4 6 2 3 7 3、用关键工件法求解第 2题的最优排序。4、用CDS启发式算法求解第2题的最优排序。70 5、有一个2/3/G/Fmax问题，其加工描述矩阵 D和加工时间矩阵T分别为：1,1,1 1,2,3 1,3,2 3 5 2 D=T=2,1,3 2,2,2 2,3,1 2 4 3 试构成一个能动作业计划。6、求第5题中加工描述矩阵和加工时间矩阵构成的无延迟作业计划。7、求解第5题中加工描述矩阵和加工时间矩阵由(1)FCFS；(2)SPT法则决定的作业顺序。71