现场管理_生产与运作管理教材

2020 2 18 1 生产与运作管理 Production OperationManagement 2020 2 18 2 作业排序 2020 2 18 3 第七章作业排序 基本概念最长流程时间n 2 F Fmax问题的算法一般n m P Fmax问题的启发式算法 2020 2 18 4 一 基本概念 1 排序排序就是要将不同的工作任务安排一个执行的顺序 使预定的目标最优化 实际上就是要解决如何按时间的先后 将有限的人力 物力资源分配给不同工作任务 使预定目标最优化的问题 2020 2 18 5 排序中常用的几个概念工件 Job 服务对象 机器 Machine Processor 服务者 如 n个零件在机器上加工 则零件是工件 设备是机器 工人维修设备 出故障的设备是工件 工人是机器 2020 2 18 6 所以 作业排序也就是要确定工件在机器上的加工顺序 可用一组工件代号的一种排列来表示 如可用 1 6 5 4 3 2 表示加工顺序 J1 J6 J5 J4 J3 J22 2020 2 18 7 2 作业计划 Scheduling 作业计划与排序不是一回事 它不仅要确定工件的加工顺序 而且还要确定每台机器加工每个工件的开工时间和完工时间 如果按最早可能开 完 工时间来编排作业计划 则排序完后 作业计划也就确定了 2020 2 18 8 3 排序问题的分类与表示1 单台机器与多台机器的排序问题 2 流水车间与单件车间排序问题 2020 2 18 9 流水车间排序问题的基本特征 每个工件的加工路线都一样 如车 铣 磨 这里指的是工件的加工流向一致 并不要求每个工件必须在每台机器上加工 如有的工件为车 磨 有的为铣 磨 不仅加工路线一致 而且所有工件在各台机器上的加工顺序也一样 这种排序称为排列排序 同顺序排序 如工件排序为 J1 J3 J2 则表示所有机器都是先加工J1 然后加工J3 最后加工J2 2020 2 18 10 单件车间排序问题的基本特征 每个工件都有其独特的加工路线 工件没有一定的流向 2020 2 18 11 3 表示方法一般正规的表示方法为 n m A Bn 工件数 m 机器数 A 车间类型 F P G B 目标函数 2020 2 18 12 4 一般来说 排列排序问题的最优解不一定是相应流水车间排序问题的最优解 但一般是比较好的解 而对于仅有2台或3台机器的情况 则排列排序问题的最优解一定是相应流水车间排序问题的最优解 2020 2 18 13 二 最长流程时间 最长流程时间 加工周期 从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间 假定所有工件的到达时间都为0 则Fmax等于排在末位加工的工件在车间的停留时间 2020 2 18 14 计算Fmax的几个假定条件 机器M1不会发生空闲 对其它机器 能对某一工件加工必须具备2个条件 机器必须完成排前一位的工件的加工 要加工的工件的上道工序已经完工 2020 2 18 15 三 n 2 F Fmax问题的算法 Johnson算法 假定 ai为工件Ji在机器M1上的加工时间 bi为工件Ji在机器M2上的加工时间 每个工件按M1 M2的路线加工 2020 2 18 16 Johnson算法的步骤 从加工时间矩阵中找出最短的加工时间若最短时间出现在M1上 则对应的工件尽可能往前排若最短时间出现在M2上 则对应的工件尽可能往后排若最短时间有多个 则任选一个划去已排序的工件若所有工件都已排序 则停止 否则重复上述步骤 2020 2 18 17 四 一般n m P Fmax问题的启发式算法 对于一般的n m P Fmax问题 可以用分支定界法求得最优解 但计算量很大 实际中 可以用启发式算法求近优解 2020 2 18 18 关键工件法的步骤 计算Pi Pij 找出Pi最长的工件 将之作为关键工件C 对其余工件 若Pi1 Pim 则按Pi1不减的顺序排成序列SA 若Pi1 Pim 则按Pim不增的顺序排成序列SB 顺序 SA C SB 即为近优解 2020 2 18 19 ShopFloorActivityManagement 车间作业管理 POM2002 2020 2 18 20 车间作业管理的基本概念车间作业排序车间作业控制 2020 2 18 21 典型的作业排序和控制功能 以下职能必须在对作业排序和控制时完成 分配订单 设备和人员到各工作中心或其他规定的地方决定订单顺序 即建立订单优先级 对已排序作业开始安排生产 通常称之为调度车间作业控制 或生产作业控制 包括 在作业进行过程中 检查其状态和控制作业的速度加快为期已晚的和关键的作业计划员的决策取决于以下因素 每个作业的方式和规定的工艺顺序要求 每个工作中心上现有作业的状态 每个工作中心前作业的排队情况 作业优先级 物料的可得性 当天较晚发布的作业订单 工作中心资源的能力 2020 2 18 22 车间作业管理的信息源 计划文件项目主文件 记录全部有关零件的信息工艺路线文件 记录生产零件的加工顺序工作中心文件 记录工作中心数据控制文件车间文物主文件 为每个生产中的任务提供一条记录车间任务详细文件 记载完成每个车间任务所需工序从工作人员得到的信息 2020 2 18 23 计划文件数据概要 计划文件 文件中的内容 项目主文件 工艺路线文件 工作中心文件 零件号零件名称生产提前期现有库存已分配量已定货量批量 工序号工序名称准备时间加工时间 工作中心号能力数据替换工作中心排队时间 2020 2 18 24 控制文件 文件中的信息 车间任务主文件 车间任务细文件 车间任务号任务数量完工数量废品数量支付数量交货日期成本信息优先级未完成量 车间任务工序号工作中心计划准备时间 实际准备时间计划加工工时 实际加工工时计划数量 完工数量废品数量开工日期 完工日期 2020 2 18 25 加工单 知道需要经过哪些加工工序 工艺路线 知道需要什么工具 材料 能力的提前期确定工具 材料 能力和提前期的可用性解决工具 材料 能力和提前期短缺问题最后将任务下达 尽可能满足计划要求发放工具 材料和任务的有关文件给车间 加工单 workorder 或车间定单 shoporder 是一种面向加工件说明物料需求计划的文件 可以跨车间甚至厂际协作 加工单的格式同工艺路线报表相似 2020 2 18 26 计划进度开始日期完工日期 工作中心标准时间 小时 编号名称准备加工机器 加工单的典型格式 定单号 970215需用数量 100件计划日期 970630物料名称 C物料号 111000需用日期 970901 102030405060 下料车削热处理磨削电镀检验 010010203006010020529000108015 锯床车床电炉磨床 外协 质检 0 51 01 21 0 0 251 25 2 00 0 10 5 00 25 5126 06 2201 0 240 10 0 970710970715970725970729970815970829 970712970724970726970814970828970830 M432 工序 工序名称 本工序总时间 2020 2 18 27 派工单 派工单 dispatchlist 或称调度单 是一种面向工作中心说明加工优先级的文件 说明工作在一周或一个时期内要完成的生产任务 说明哪些工作已经达到 正在排队 应当什么时间开始加工 什么时间完成 加工单的需用日期是哪天 计划加工时数是多少 完成后又应传给哪道工序 说明哪些工件即将达到 什么时间到 从哪里来 根据派工单 车间调度员 工作中心操作员对目前和即将到达的任务一目了然 2020 2 18 28 数量需用完成 派工单的典型格式 计划进度开始日期完工日期 物料号 物料名称 工作中心 8513名称 车床 加工单号 工序号 数量需用完成 时间准备加工 上工序 下工序 正加工的工件 已加工的工件 将达到的工件 75831D970872016209705049705041 01028860188501C9709850209705049705060 21510288603 51888F9712040409705069705070 2108420入库16877G9737620309705079705070 15 085108523 37414D9708725159705109705110 18 07100820088501C9709810109705129705120 13 072008532 2020 2 18 29 工作中心特征和重要性 工作中心是生产经营中的个区域 在这个区域中 组织生产资源来完成工作 工作中心可以是一台机器 一一组机器或完成某一类型工作的一个区域 这些工作中心可以按工艺专业化的一般作业车间组织 或者按产品流程 装配线 成组技术单元结构进行组织 在工艺专业化情况下 工件需按规定路线在各个按功能组织的工作中心之间移动 作业排序涉及决定工件加工顺序以及分配相应的机器来对这些工件加工 一个作业排序系统区别于另一个作业排序系统的特征是 在进行作业排序时是如何考虑生产能力的 2020 2 18 30 有限负荷方法和无限负荷方法 无限负荷指的是当将工作分配给一个工作中心时 只考虑它需要多少时间 而不直接考虑完成这项工作所需的资源是否有足够的能力 也不考虑在该工作中 每个资源完成这项工作时的实际顺序 通常仅检查一下关键资源 大体上看看其是否超负荷 可以根据各种作业顺序下的调整和加工时间标准来计算出一段时间内所需的工作量来判定 有限负荷实际上是用每一订单所需的调整时间和运行时间对每一种资源详细计划 提前期由期望作业时间 调整和运行时间 加上由于材料运输和等待订单执行而引起的期望排队延期时间而估算出 从理论上将 当运用有限负荷时 所由的计划都是可行的 2020 2 18 31 前向排序和后向排序 前向排序 指的是系统接受一个订单后对订单所需作业按从前向后的顺序进行排序 前向排序系统能力告诉我们订单能完成的最早日期 后向排序 是从未来的某个日期 可能是一个约定交货日期 开始 按从后向前的顺序对所需作业进行排序 后向排序告诉我们为了按规定日期完成 一个作业必须开始的最晚时间 区分作业排序的另一个特征是基于前向排序还是后向排序 在前向排序和后向排序中 最常用的是前向排序 2020 2 18 32 生产工序类型和计划方法 类型产品特征通常的计划方法 单一工序大批量生产中等批量生产小批量生产 化工产品 钢 金属 液体产品等汽车 电话 摩托车 家用设施工业用品 最终消费品定做的或标准的设备 专用仪器等 全自动化 产品中劳动力成本低 设施专用于一种产品自动化装备 半自动化传动装置或移动装配线成组技术单元 专业化小工厂按生产功能组织的机器中心 通用设备换装时间相当长等 有限符合 前向排序 机器有限生产线有限负荷 前向排序 机器有限 准时化生产无限负荷 前向排序 有限调度控制 常劳动力有限但有时机器有限无限负荷 前向排序 2020 2 18 33 车间作业排序的目标 满足交货期极小化提前期极小化准备时间或成本极小化在制品库存极大化设备或劳动力的利用 注 最后一个目标是有争议的 因为仅仅依靠保持所有设备 或员工处于繁忙的状态可能不是在工序中管理生产的最有效方法 2020 2 18 34 作业计划和排序的关系 编作业计划 scheduling 与排序 sequencing 不是同义语 排序只是确定工件在机器上的加工顺序 可以通过一组工件的代号的一种排列来表示该组工件的加工顺序 而编制作业计划 则不仅包括确定工件的加工顺序 而且包括确定机器加工每个工件的开始时间和完成时间 因此 只有作业计划才能指导每个工人的生产活动 由于编制作业计划的主要问题是确定各台机器上工件的加工顺序 而且 在通常情况下都是按最早可能开 完 工时间来编排作业计划 因此 当工件的加工顺序确定之后 作业计划也就确定了 所以 人们常常不加区别地使用 排序 与 编作业计划 2020 2 18 35 作业排序的十大优先规则 FCFS 先到先服务 FirstComeFirstServer 按订单送到的先后顺序进行加工 SOT 最短作业时间 所需加工时间最短的作业首先进行 然后是加工时间第二最短的 如此等等 这个规则等同于SPT 最短加工时间 规则 DDate交货期 最早交货期最早加工 将交货期最早的作业放在第一个进行 开始日期 交货期减去正常的提前期 最早开始的作业第一个进行 2020 2 18 36 STR 剩余松弛时间 STR是交货期前所剩余时间减去剩余的加工时间所得的差值 STR最短的任务最先进行 STR OP 每个作业剩余的松弛 STR OP最短的任务最先进行 STR OP的计算方法为 CR紧迫系数 紧迫系数是用交货期减去当前日期的差值除以剩余的工作日数 紧迫系数最小的任务先进行 STR OP 交货提前期所剩的时间 剩余的加工时间 剩余的作业数 紧迫系数 CR 需用日期 今日日期剩余的计划提前期 2020 2 18 37 CR 负值说明已经脱期CR 1说明剩余时间刚好够用CR 1剩余时间有富裕CR 1剩余时间不够CR值小者优先级高 一个工件完成后 其余工件的CR值会有变化 应随时调整 QO 排队比率 排队比率是用计划中剩余的松弛时间除以计划中剩余的排队时间 排队比率最小的先进行 LCFS 后到先服务 该规则经常作为缺省规则使用 因为后来的工单放在先来的上面 操作人员通常是先加工上面的工单 随机规则 2020 2 18 38 作业排序的评价 在某机器上或某工作中心决定哪个作业首先开始工作的过程称为排序或优先调度排序 在进行作业排序时 需用到优先调度规则 这些规则可能很简单 仅需根据一种数据信息对作业进行排序 这些数据可以是加工时间 交货期货到达的顺序 下列作业排序标准可用于评价优先规则 满足顾客或下一道工序作业的交货期极小化流程时间 作业在工序中所耗费的时间 极小化在制品库存极小化设备和工人的闲置时间 2020 2 18 39 排序问题的分类与表示法 按机器的种类和数量分 单台机器排序问题和多台机器排序问题按加工路线的特征分 单件车间排序问题和流水车间排序问题按工件达到车间的情况不同分 静态排序问题和动态排序问题按目标函数分 平均流程时间最短或误期完工的工件数最少按参数的性质分 确定型排序问题与随机型排序问题 Conway等人提出的排序法 n m A B其中 n 工件数m 机器数A 车间类型 F表示流水车间排序 P流水车间排列排序问题 G表示单件车间 B 目标函数 2020 2 18 40 N个作业单台工作中心的排序 这类问题被称作 n个作业 单台工作中心的问题 或 n 1 理论上 排序问题的难度随着工作中心数量的增加而增大 而不是随着作业数量的增加而增大 对n的约束是其必须是确定的有限的数 例 n个作业单台工作中心排序问题 在一周的开始 有5位顾客提交了他们的订单 原始数据为 订单 以到达的顺序 加工时间 天交货期 天 ABCDE 34261 56792 2020 2 18 41 方案一利用FCFS规则 其流程时间的结果如下 加工顺序加工时间交货日期流程时间 ABCDE 34261 56792 0 3 33 4 77 2 99 6 1515 1 16 总流程时间 3 7 9 15 16 50 天 平均流程时间 50 5 10天将每个订单的交货日期与其流程时间相比较 发现只有A订单能按时交货 订单B C D和E将会延期交货 延期时间分别为1 2 6 14天 每个订单平均延期 1 1 2 6 14 5 4 6天 2020 2 18 42 方案二利用SOT规则 流程时间为 加工顺序加工时间交货日期流程时间 ECABD 12346 27569 0 1 11 2 33 3 66 4 1010 6 16 总流程时间 1 3 6 10 16 36 天 平均流程时间 36 5 7 5天SOT规则的平均流程时间比FCFS规则的平均流程时间小 另外 订单E和C将在交货日期前完成 订单A仅延期1天 每个订单的平均延期时间为 0 0 1 4 7 5 2 4天 2020 2 18 43 加工顺序加工时间交货日期流程时间 EABCD 13426 25679 0 1 11 3 44 4 88 2 1010 6 16 总流程时间 1 4 8 10 16 39 天 平均流程时间 39 5 7 8天在这种情况下 订单B C和D将会延期 平均延期时间为 0 0 2 7 5 2 4天 方案三利用DDate规则 排序结果为 2020 2 18 44 加工顺序加工时间交货日期流程时间 EDCBA 16243 29765 0 1 11 6 77 2 99 4 1313 3 16 总流程时间 1 7 9 13 16 46 天 平均流程时间 46 5 9 2天平均延期 4 0天 方案四利用LCFS规则 预计流程时间为 2020 2 18 45 加工顺序加工时间交货日期流程时间 DCAEB 62314 97526 0 6 66 2 88 3 1111 1 1212 4 16 总流程时间 6 8 11 12 16 55 天 平均流程时间 55 5 11天平均延期 5 4天 方案五利用随机规则 排序结果为 2020 2 18 46 加工顺序加工时间交货日期流程时间 EABDC 13462 25697 0 6 61 3 44 4 88 6 1414 2 16 总流程时间 6 4 8 14 16 43 天 平均流程时间 43 5 8 6天平均延期 3 2天 方案六利用STR规则 排序结果为 2020 2 18 47 规则总的完成时间平均完成时间平均延期 FCFSSOTDDateLCFS随机STR 503639465343 107 27 89 210 68 6 4 62 42 44 05 43 2 很明显 此例中SOT比其余的规则都好 但情况总是这样的吗 答案是肯定的 另外 从数学上可以证明 在n 1情况下 用其他的评价准则 如等待时间均值和完成时间均值最小 SOT规则也是最优方案 事实上 这个简单被称为 在整个排序学科中最重要的概念 2020 2 18 48 N个作业两台工作中心排序 稍微复杂的n 2排序情况 被称为约翰逊 Hohnson 规则或方法 这是S M Johnson于1954年提出的 其目的是极小化从第一个作业开始到最后一个作业为止的全部流程时间 以ai表示Ji在M1上加工时间 以bi表示Ji在M2上的加工时间 每个工件都按M1 M2的路线加工 Johnson的算法法则是 如果Min ai bj min aj bi 则Ji应该排在Jj之前 约翰逊规则包含下列几个步骤 列出每个作业在两台工作中心上的作业时间选择最短的作业时间如果最短的作业时间来自第一台工作中心 则首先进行这个作业 如果最短的作业时间来自第二个工作中心 则该作业最后排序对剩余作业重复进行步骤2和3 直到排序完成 2020 2 18 49 iaibi 157 212 382 454 537 644 解 应用Johnson算法 从加工时间矩阵中找出最短加工时间为1个时间单位 它出现在M1上 所以 相应的工件 工件2 应尽可能往前排 即将工件2排在第1位 划去工件2的加工时间 余下加工时间中最小者为2 它出现在M2上 相应的工件 工件3 应尽可能往后排 于是排到最后一位 划去工件3的加工时间 继续按Johnson算法安排余下工件的加工顺序 将工件2排第1位2 将工件3排第6位2 3将工件5排第2位25 3将工件4排第5位25 43将工件6排第3位256 43将工件1排第4位256143 答案 最优加工顺序为S 2 5 6 1 4 3 例求表所示 6 2问题的最优解 2020 2 18 50 N个作业n台工作中心排序 有些车间有足够数量的合适工作中心 使得所有的作业都可以在同一时间开始进行 在这里问题不是哪个作业先进行 而是将哪个作业指派给哪个工作中心 以使排序最佳 可以使用指派法 指派法是线性规划中运输方法的一个特例 其目的是极小化或极大化某些效率指标 指派方法很适合解决具有如下特征的问题 有n个 事项 要分配到n个 目的地 每个事项必须被派给一个而且是唯一的目的地只能用一个标准 例如 最小成本 最大利润或最少完成时间等 2020 2 18 51 例 指派方法假定一个调度员有5项作业要完成 每项作业可在5台工作中心的任一台上完成 n 5 完成每项作业的成本见下表 计划员想设计一个最小成本分配方案 有5 120个可能的分配方案 表明每项作业的工作中心加工成本分配矩阵 作业 A56473 B64926 E35435 D88555 C49244 2020 2 18 52 这个问题可以用指派法来解决 步骤如下 将每行中的数减去该行中的最小数 这将会使每行中至少有一个0 将每列中的各个数量减去该列中的最小数 这将会使每列中至少有一个0 判断覆盖所有0的最少线条数是否等于n 如果相等 就得到了一个最优方案 因为作业只在0位置上指派给工作中心 如果满足上述要求的线条数少于n个 转至第4步画尽可能少的线 使这些线穿过所有的0 这些线可能与步骤3中的线一样 将未被这些线覆盖的数减去其中最小的 并将位于线交点位置上的数加上该最小的数 重复步骤3 2020 2 18 53 分配矩阵的求解过程 步骤1 行减 从本行中减去本行最小数 工作中心 作业 A22250 B30103 C15021 D54332 E01212 步骤2 列减 从每一列中减去本列中最小数 工作中心 作业 A22250 B30103 C15021 D32110 E01212 2020 2 18 54 分配矩阵的求解过程 步骤3 应用线检验 覆盖全部0的线数是4 因为要求的是5 所以转至第4步 工作中心 作业 A22250 B30102 C15021 D32110 E01212 步骤4 将未被覆盖的数减去其中的最小数 并将该最小数加到直线的交点上 用步骤3中画的线 未被覆盖的数是1 工作中心 作业 A11240 B30204 C04011 D21100 E01313 2020 2 18 55 分配矩阵的求解过程 最优方案 用 线检验 工作中心 作业 A11240 B30204 C04011 D21100 E01313 最优分配几及其成本 作业 分配给E 3作业 分配给B4作业 分配给C2作业 分配给D5作业 分配给A3总成本 17 2020 2 18 56 N个作业m台工作中心排序 这是复杂作业车间的特征 如果有n项作业在m台工作中心上进行且每项作业都要在所有的工作中心上进行 则排序的量太大 计算机模拟是唯一可行的方法 当然 也要按一定的规则进行分析 应该用那种优先规则 优先计划应是动态的 也就是说 在作业过程中要经常计算 以反映不断变化的状况优先计划应尽量考虑松弛时间 这体现了由Johnkanet和JackHougya所提到的关于交货期的一些特征 最新的方法是在PC上将模拟和人工结合起来进行排序 2020 2 18 57 任务下达流程据概要 2020 2 18 58 车间作业控制的定义和主要功能 APICSA对车间控制系统的定义为 应用来自车间的数据以及数据处理文件 来维护和传递有关车间工单和工作中心状态信息的系统 车间作业控制的功能有 为每一车间工单分配优先级维护在制品数量信息将车间工单状态信息传递到办公室为能力控制提供实际产出数据根据工单和工位要求 为制品库存管理提供数量依据提供效率 利用率 人力和设备生产率等数据 2020 2 18 59 车间作业控制的内容和意义 车间作业控制 shopfloorcontrol 意义 控制生产作业在执行中不偏离MPS MRP计划 出现偏离时 采取措施 纠正偏差 若无法纠正 则反馈到计划层 报告生产作业执行结果 内容 控制加工单的下达 控制加工件在工作中心加工的工序优先级 控制投入和产出的工作量 保持物流稳定 控制加工成本 结清定单 完成库存事务处理 2020 2 18 60 常用调度措施 在需要压缩生产周期的情况下 一般有以下措施 平行顺序作业通过设依次顺序作业中下道工序的排队时间Q为负值来实现 依次顺序作业 平行顺序作业 工作中心1工作中心2工作中心3 QSRMQSRMQSRM 提前期 QSRM 工作中心1 QSRM 工作中心2 QSRM 工作中心3 提前期 Q 排队时间S 准备时间R 加工时间M 传送时间 2020 2 18 61 加工单分批把原来一张加工单加工的数量分成几批 由几张加工单来完成 以缩短加工周期 每批的数量可以不同 采用加工单分批或分割只有在用几组工作中心能完成同样的工作时才有可能 每组工作中心需要有准备时间 准备时间增加了 此外 还可能需要几套工艺装备 成本也会增加 有时 一道工序由一台工作中心完成 下一道工序分成由两组不同的工作中心加工 然后又由一台工作中心来完成第三道工序 压缩排队 等待和传送时间有人为设定和系统按设定的比例压缩两种处理方式 替代工序或改变工艺其它 如加班加点 调配人力 2020 2 18 62 车间控制的工具 车间控制的基本工具有 1 日常调度单它告诉主管将进行哪个作业 它们的优先级如何 以及每项作业用多长时间 分配表工作中心1501 Day 205 开始日期作业号零件名称运行时间151311514315145157121534015312 轴铆钉钉子钉子测量杆轴 11 420 64 38 66 54 6 2020 2 18 63 2 各种状态和例外报告 1 预期延期报告由车间计划员每周制作一次 并由车间计划负责人进行审核 看是否有会影响主计划的严重延期 8月8日第24部门报告 2 废品报告 3 返工报告 4 作业总结报告 报告完成订单的数量和百分比 未完成的情况等 部件号计划日期新日期拖延原因措施 171251304417653 4 104 114 11 4 155 14 14 夹具损坏送出去镀金镀金工罢工新孔未成直线 工具室返还4 15新批量开始生产工程部重新安排砖模 2020 2 18 64 3 输入 输出控制报告投入 产出控制 input outputcontrol 简称I O 是控制能力计划执行的方法 或者说是一种衡量能力执行情况的方法 它也可以用来计划和控制排队时间和提前期 投入 产出报表要用到是数据是 计划投入 实际投入 计划产出 实际产出 计划排队时间