讲制造业作业计划与控制PPT课件.ppt

1 生产运作管理Production OperationsManagement 青岛理工大学 临沂 冯海侠2016年5月 华中科大管理学院陈荣秋马士华 2 第4章制造业作业计划与控制SchedulingandControllingforManufacturing 4 1作业计划问题的基本概念4 2流水车间作业计划问题4 3单件车间作业计划问题4 4生产作业控制 3 4 1作业计划问题的基本概念 4 1 1生产作业计划概述4 1 2有关的名词术语4 1 3假设条件与符号说明4 1 4排序问题的分类和表示法 4 4 1 1生产作业计划概述 生产作业计划是企业年度生产计划和MRP输出的具体执行计划 它根据年度生产计划的要求对每个生产单位 车间 工段 班组 在每个具体的时期 月 旬 周 日 轮班 小时等 内的生产任务作出详细的安排并规定实现的方法 从而保证企业按数量 品种 质量 交货期的要求全面完成生产计划 5 生产作业计划的内容生产作业计划的主要任务是将主生产计划或MRP中零部件的投入出产计划细化 他是MRP的具体执行计划 具体 详细地规定了各车间 工段 班组以至每个工作地在较短的时间内 月 旬 周 日 轮班 小时 的生产运作任务 6 生产作业计划工作由作业计划编制与作业计划控制两部分组成 作业计划编制 包括制定期量标准 开展生产运作能力核算与平衡 编制各种形式的生产作业计划等 作业计划控制包括生产运作调度 生产运作作业统计与分析等内容 7 生产作业计划的作用 保证主生产计划规定的生产运作任务的完成 保证企业获取更好的经济效益 8 4 1 2有关的名词术语 排序 就是要将不同的工作任务安排一个执行的顺序 使预定的目标最优化 实际上就是要解决如何按时间的先后 将有限的人力 物力分配给不同工作任务 使预定目标最优化的问题 派工 在作业计划制定以后 按照作业计划的要求 将具体生产任务通过工票或施工单的形式下达到具体的机床和工人 赶工 是在实际进度已经落后于计划进度时采取的行动 调度 是作业计划编制以后 实行生产控制的一切行动 9 4 1 2有关的名词术语 续 机器 表示 服务者 可以是工厂里的各种机床 也可以是维修工人 可以是轮船要停靠的码头 也可以是电子的计算机中央处理单元 存贮器和输入 输出单元 零件 代表 服务对象 零件可以是单个零件 也可以是一批相同的零件 加工路线 是零件加工的工艺过程决定的 它是零件加工在技术上的约束 加工顺序 则表示每台机器加工n个零件的先后顺序 是排序和编制作业计划要解决的问题 10 4 1 3假设条件与符号说明 假设条件 一个零件不能同时在几台不同的机器上加工 零件在加工过程中采取平行移动方式 即当上一道工序完工后 立即送下道工序加工 不允许中断 当一个零件一旦开始加工 必须一直进行到完工 不得中途停止插入其它零件 每道工序只在一台机器上完成 零件数 机器数和加工时间已知 每台机器同时只能加工一个零件 11 4 1 3假设条件与符号说明 续 Ji 零件i i 1 2 n Mj 机器j j 1 2 m pij一Ji在Mj上的加工时间 Ji的总加工时间为Pi pijri一Ji的到达时间 指Ji从外部进入车间 可以开始加工的最早时间 di一Ji的完工期限 Ci一Ji的完工时间 Ci ri wij pij ri Wi Pi Cmax 最长完工时间 Cmax max Ci 12 Fi一Ji的流程时间 即零件在车间的实际停留时间 Fi Ci ri Wi Pi Fmax 最长流程时间 Fmax max Fi Li 零件的延迟时间Li Ci di当Li 0 正延迟 说明Ji的实际完工时间超过了完工期限 当Li 0 负延迟 说明Ji提前完工 当Li 0 零延迟 Ji按期完工 Lmax 最长延迟时间 Lmax max Li 4 1 3假设条件与符号说明 续 13 4 1 4排序问题的分类和表示法 按机器单机排序问题和多机排序问题多机 单件作业排序与流水作业排序按工件到达情况静态和动态按目标函数单目标排序问题和多目标排序问题 14 按参数的性质确定型排序问题 加工时间和其他有关参数是已知的确定量 随机型排序问题 加工时间和有关参数为随机变量 四参数表示法 康韦 Conway n m A B其中 n为零件数 m为机器数 A为车间类型 若标以F 则代表流水作业排序问题 若标以P 则代表流水作业排列排序问题 若标以G 则表示一般单件作业排序问题 B为目标函数 通常是使其值最小 例如 n 3 P Cmax表示n个零件经3台机器加工的流水作业排列排序问题 目标函数是使最长完工时间Cmax最短 15 4 2流水作业排序问题 流水车间 Flowshop 工件的加工路线都一致 典型的如流水线4 2 1加工周期的计算4 2 2两台机器排序问题的最优算法4 2 3一般n m p Fmax排序问题的启发式算法4 2 4相同零件 不同移动方式下加工周期 16 n个不同的零件要按相同的加工路线经过m台机器加工 目标是使这批零件的加工周期最短 n m P Fmax加工周期又称为最长流程时间 它是从第一个零件在第一台机器开始加工时起 到最后一个零件在最后一台机器上完成加工时为止所经过的时间 假设所有零件的到达时间都为零 ri 0 i 1 2 n 则Fmax等于排在末位加工的零件在车间的停留时间 也等于一批零件的最长完工时间Cmax 4 2 1加工周期的计算 17 设n个零件的加工顺序为S S1 S2 Sn 其中Si为排第i位加工的零件的代号 以CkSi表示零件Si在机器Mk上的完工时间 PSik表示零件Si在Mk上的加工时间 k 1 2 m i 1 2 n 则CkSi可按以下公式计算C1Si C1Si 1 PSi1CkSi maxC k 1 Si CkSi 1 PSikk 2 3 m i 1 2 nCmSn 即为最长流程时间Fmax 18 4 2 1加工周期的计算 工件代号i 123456 Pi1464583Pi2353971Pi3792658Pi4549623 有一个6 4 P Fmax问题 其加工时间如下表所示 当按顺序S 1 4 6 3 5 2 加工时 求Fmax 19 4 2 1加工周期的计算 工件代号i 146352 Pi1453486Pi2391375Pi3768259Pi4563924 4912162430 71819223136 142432343948 193035444652 20 对于n个零件经过两台机器加工 要使加工周期最短的流水作业排序问题 即n 2 F Fmax问题 约翰逊于1954年提出了一个最优算法 即著名的Johnson算法 为叙述方便 以ai表示零件Ji在机器M1上的加工时间 以bi表示零件Ji在机器M2上的加工时间 每个零件都按M1M2的路线加工 4 2 2两台机器排序问题的最优算法 21 4 2 2两台机器排序问题的最优算法 约翰逊法则如果Min ai bj Min aj bi 则工件i应该排在工件j之前 如果为等号 则零件i即可安排在零件j之前 又可安排在零件j之后 约翰逊算法 Johnson算法 1 从加工时间矩阵中找出最短加工时间 2 若最短加工时间出现在机器M1上 则对应工件应该尽可能往前排 若最短加工时间出现在机器M2上 则对应工件应该尽可能往后排 22 4 2 2两台机器排序问题的最优算法 续 然后从加工时间矩阵中划去已排序工件的加工时间 若最短加工时间有多个 则任挑一个 3 若所有工件都已排序 停止 否则 转步骤 1 23 将工件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 I123456 ai518534bi722474 4 2 2两台机器排序问题的最优算法 续 24 4 2 2两台机器排序问题的最优算法 续 Johnson算法的改进 1 将所有ai bi的工件按ai值不减的顺序排成一个序列A 2 将ai bi的工件按bi值不增的顺序排成一个序列B 3 将A放到B之前 就构成了一个最优加工顺序 25 4 2 2两台机器排序问题的最优算法 续 举例 工件号123456 ai518534 bi722474 工件最优顺序 256143 134558274742 48131826 31115222628 ai bi 最优顺序下的加工周期为28 26 应用Johnson算法求得的最优顺序中任意去掉一些零件时 余下零件构成的顺序仍为最优顺序 Johnson法则只是一个充分条件 不是必要条件 不符合这个法则的加工顺序 也可能是最优顺序 最优顺序不一定是唯一的 例如顺序 2 5 6 4 1 3 说明 27 4 2 3多台机器排序问题的启发式算法 关键工件法1 计算每个工件的总加工时间 将加工时间最长的工件作为关键工件C 2 对于余下的工件 若pi1 pim则按pi1不减的顺序排成一个序列Sa 若pi1 pim则按pim不增的顺序排成一个序列Sb 3 顺序 Sa C Sb 即为所求顺序 28 4 2 3多台机器排序问题的启发式算法 续 举例 工件i1234 Pi12163Pi24829Pi35482 11131614 C Sa 2 1 Sb 4 所求顺序 2 1 3 4 29 Palmer 帕尔默 法 1965年 帕尔默 D S Palmer 对流水作业排序问题提出了按斜度指标排列工件的启发式算法 该算法先定义工件的斜度指标 然后将各工件按其斜度指标不增进行排序 零件的斜度指标可按下式计算 式中 m为机器数 Pik为零件i在机器Mk上的加工时间 按照各零件不增的顺序排列零件 可得出令人满意的加工顺序 30 例3 有一个4 3 F Fmax问题 其加工时间如下表所示 试用Palmer法求解 工件i1234 Pi11263Pi28429Pi34582 31 CDS法 坎贝尔 Campbell 杜德克 Dudek 史密斯 Smith 三人提出了一个启发式算法 简称CDS法 他们把Johnson算法用于一般的n m F Fmax问题 得到 m 1 个加工顺序 取其中的优者 具体的做法是 对加工时间 注 当取不同值 对每一组值 看成是分别在两个机器上的加工时间 32 4 3单件车间作业计划问题 4 3 1任务分配问题4 3 2排序问题的描述4 3 3两种作业计划的构成4 3 4求解一般n m G Fmax问题的启发式方法 33 4 3 1任务分配问题 把n项任务分给n台机器加工 有n 方案匈牙利算法 1 从加工时间 费用 矩阵每一行所有元素减去该行最小的元素 使每行至少出现一个零元素 2 从实施第 1 步得到的矩阵中的每一列所有元素减去该列最小的元素 使每列至少出现一个零元素 3 从实施第 2 步得到的矩阵中 划出能覆盖尽可能多的零元素的直线 如果线条数等于矩阵的行数 则已找到最优矩阵 转第 6 步 否则 转第 4 步 4 从矩阵中未被线条穿过的元素中减去这些元素中的最小数 并将这个最小数加到直线交叉的元素上 其余元素不变 5 重复步骤 3 和步骤 4 直到获得最优矩阵 6 从仅有一个零的行或列开始 找出零元素对应的分配方案 每行和每列仅能确定一个元素 最后使每行和每列都有一个零元素 零元素对应的就是最优分配方案 例4 3 1有如下任务分配问题 34 求解过程如下表所示 35 36 e 零件1由机器M3加工 零件2由机器M2加工 零件3由机器M4加工 零件4由机器M1加工 可使总加工时间最少 37 38 对于一般单件作业排序问题 要描述一道工序 要用三个参数 i j 和k i表示工件的代号 j表示工序 k表示完成工件i的第j道工序的机器的代号 用 i j k 表示工件i的第j道工序是在机器k上进行加工的 于是可以用加工描述矩阵的形式来描述所有工件的加工 4 3 2单件作业排序问题的描述 39 4 3 2单件作业排序问题的描述 D 1 1 11 2 31 3 22 1 32 2 12 3 2 T 241345 加工描述矩阵D和加工时间矩阵T对应 40 两种作业计划的构成半能动作业计划 各工序都按最早可能开 完 工时间安排的作业计划 能动作业计划 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划 无延迟作业计划 没有任何延迟出现的能动作业计划 延迟 指有工件等待加工时 机器出现空闲 既使这段空闲时间不足以完成一道工序 4 3 3一般n m G Fmax问题的启发式算法 41 4 3 3两种作业计划的构成 续 符号说明每安排一道工序称为一 步 St t步之前已排序工序构成的部分作业计划 Ot t步可排序工序的集合 Tk为 Ot 中工序Ok的最早可能开始时间 T k为 Ot 中工序Ok的最早可能完成时间 42 4 3 3两种作业计划的构成 续 能动作业计划的构成步骤 1 设t 1 S1 为空集 O1 为各工件第一道工序的集合 2 求T min T k 并求出T 所出现的机器M 如果M 有多台 则任选一台 3 从 Ot 中选出满足以下两个条件的工序Oj 需要M 加工 且Tj T 4 将选定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 5 若还有未安排的工序 转步骤 2 否则 停止 43 能动作业计划的构成 44 能动作业计划的甘特图 2 3 2 1 1 12 2 1 1 3 2 2 1 31 2 3 37 7813 237 0 时间 机器 M1 M2 M3 45 4 3 3两种作业计划的构成 续 无延迟作业计划的构成 1 设t 1 S1 为空集 O1 为各工件第一道工序的集合 2 求T min Tk 并求出T 所出现的机器M 如果M 有多台 则任选一台 3 从 Ot 中选出满足以下两个条件的工序Oj 需要M 加工 且Tj T 4 将选定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 5 若还有未安排的工序 转步骤 2 否则 停止 46 无延迟作业计划的构成 47 无延迟作业计划的甘特图 2 3 2 1 1 12 2 1 2 1 31 2 3 37 712 237 0 时间 机器 M1 M2 M3 1 3 2 48 4 3 4三类启发式算法 1 优先调度法则构成两种作业计划的第 3 步一般都有多道工序可以满足 按不同的优先调度法则来选择工序 可以得出满足不同目标函数的作业计划更能符合计划编制者的要求计算量小已经提出100多种优先调度法则 49 优先调度法则FCFS firstcome firstserved 优先选择最早进入可排序集合的工序SPT shortestprocessingtime 优先选择加工时间最短的工序EDD earliestduedate 优先选择完工期限紧的工序SCR smallestcriticalratio 选择临界比最小的工件 临界比 工件允许停留时间与工件余下加工时间之比 MWKR mostworkremaining 优先选择余下加工时间最长的工件LWKR leastworkremaining 优先选择余下加工时间最短的工件MOPNR mostoperationsremaining 优先选择余下工序数最多的工件 50 按SPT法则 可使工件的平均流程时间最短 从而减少在制品库存量 FCFS法则来自排队论 它对工件较公平 EDD法则可使工件最大延误时间最小 SCR法则也是保证工件延误最小的法则 MWKR与MOPNR法则类似使不同工作量的工件的完工时间尽量接近 LWKR法则使工作量小的工件尽快完成 RANDOM随机挑选一个工件 51 在应用优先调度法则时 只要将构成能动作业计划的第3步修改为 对 Ot 中需要M 加工 且Tj T 的工序 按预定的优先调度法则确定一个进入 St 的工序 对于构成无延迟作业计划的第3步修改为 对 Ot 中需要M 加工 且Tj T 的工序 按预定的优先调度法则确定一个进入 St 的工序 一般来说 以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好 有时应用一个优先法则还不能惟一地确定一道应挑选的工序 需要多个优先调度法则的有序组合 譬如 SPT MWKR RANDOM 52 4 3 3三类启发式算法 续 2 随机抽样法从全部能动计划或无延迟计划中随机抽样 得出多个作业计划 从中取优 介于两个极端之间效果与样本大小和母体有关比用优先调度法则得到的结果一般要好一些 但计算量要大一些从无延迟作业计划母体抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好 3 概率调度法将优先调度法则与随机抽样法结合对不同工件按优先调度法则分配不同的挑选概率 效果较好 53 4 4生产作业控制 4 4 1实行生产作业控制的原因和条件4 4 2不同生产类型生产控制的特点4 4 3利用 漏斗模型 进行生产控制 54 4 4 1实行生产作业控制的原因和条件 原因加工时间估计不准确随机因素的影响加工路线的多样性企业环境的动态性条件要有控制标准取得实际进度偏离计划的信息能够采取纠正行动 55 生产作业控制的程序 制定生产作业监控体系监控实际生产过程评估偏差情况采取纠偏措施 56 生产作业控制的功能 为每个车间的工单指派优先级维护车间在制品数量将车间工单信息传送到相应办公室提供实际产出数据来为能力控制服务根据车间工单对机位的要求 为在制品库存管理提供数量信息测量人员和设备的效率 利用率和产量 57 4 4 2不同生产类型生产控制的特点 不同生产类型的特点 58 4 4 2不同生产类型生产控制的特点 续 单件小批生产 排队时间是主要的 通过输入 输出控制排队队长大量大批生产 控制问题较简单 主要是调整工作班次 工作时间和工人数量 移动时间 排队时间 调整准备时间 加工时间 待运时间 零件加工提前期的构成 59 生产作业控制的主要工具 实际生产中 有不少工具可以用来进行生产作业控制 这些工具容易通过运用适当的软件来生成 主要包括 调度单日报 月报例外报告 异常报告输入 输出 Input outputcontrol I O 报告 60 4 4 3利用 漏斗模型 进行生产控制 德国汉诺威大学的贝克特 Bechte 和温道尔 Wiendall 等人于20世纪80年代初在实施输入 输出控制时提出了漏斗模型 FunnelModel 漏斗模型的基本原则 工作中心的输入永远不能超过工作中心的输出 当工作中心的输入超过输出 就会拖欠订单 结果将会出现作业推迟 客户不满 下游作业或相关作业的延期 61 62 注 曲线图的垂直段表示某天到达或完成的一个或多个工件之间所包含的工作量 水平段表示相邻两个到达或完成的任务之间的时间间隔 如果运输时间不变 输入曲线与上道工序的输出曲线相对应 63 4 4 3利用 漏斗模型 进行生产控制 续 在一段较长的时间内 如数周 内 若工况稳定 输入输出两条曲线可以近似地用两条直线来表示 其斜率 平均生产率 等于平均在制品库存 平均通过时间实际实践中 可以采用四个规则来调整输入 输出 在制品库存和通过时间 若希望保持在制品库存稳定 就要使单位时间内的平均输入等于平均输出 若希望改变在制品库存量 可暂时增加或减少输入 若希望平均通过时间在所控制的范围内 则适当调整平均在制品库存与生产率的比例 要使各个工件的平均通过时间稳定 可以采用FIFO规则来安排各工件的加工顺序 漏斗模型适合于多品种中小批量生产系统的控制 64 本章习题 思考题 1 作业计划解决什么问题 请举例说明 2 排序 编制作业计划 派工 赶工 调度 控制等术语的含义及其相