第11章+制造业作业计划与控制.ppt

流水作业排序问题单件作业排序问题 重点 内容 排序问题的基本概念流水作业排序问题单件作业排序问题生产作业控制 第11章制造业作业计划与控制 生产作业计划的主要任务是将主生产计划或MRP中的零部件投入出产计划细化 是MRP的具体执行计划 具体 详细地规定了各车间 工段 班组以至每个工作地在较短的时间内 月 旬 周 日 轮班 小时 的生产运作任务 生产作业计划的内容 作业计划与控制的关系 作业计划 给生产活动制定详细时间表生产控制 以生产计划和作业计划为依据 检查 落实计划执行情况 发现偏差即采取纠正措施 保证实现各项各项计划目标 第一节排序问题的基本概念 一 名词术语 生产管理 编制 作业计划 Scheduling 排序 Sequencing 派工 Dispatching 控制 Controlling 赶工 Expediting 排序 工件在机器上的加工顺序 编制 作业计划 工件的加工顺序 加工工件的开始时间 加工工件的完成时间 作业计划的主要问题是确定各台机器上工件的加工顺序 通常情况下都是按最早可能开 完 工时间来编排作业计划的 当工件的加工顺序确定之后 作业计划也就确定了 派工 赶工 属于 调度 范围 编制作业计划 加工制造发生之前的活动 调度 是在加工制造发生之后的活动 是发现实生产进度已经偏离预定计划而采取的调配资源的行动调度的依据是作业计划 描述排序问题的术语 机器 工件 工序 加工时间 n个工件经过m台机器加工 加工路线 工件加工的工艺过程决定 一般用M1 M2 来表示 加工顺序 每台机器加工n个工件的先后顺序 排序问题的复杂性 确定出最佳的作业顺序看似容易 只要列出所有的顺序 然后再从中挑出最好的就可以了 但要实现这种想法几乎是不可能的 例如 考虑32项任务 工件 有32 2 6 1035种方案 假定计算机每秒钟可以检查1billion个顺序 全部检验完毕需要8 4 1015个世纪 如果只有16个工件 同样按每秒钟可以检查1billion个顺序计算 也需要2 3年 以上问题还没有考虑其他的约束条件 如机器 人力资源 厂房场地等 如果加上这些约束条件 所需要的时间就无法想象了 所以 很有必要去寻找一些有效算法 解决管理中的实际问题 二 假设条件与符号说明 假设条件 l 一个工件不能同时在几台不同的机器上加工2 工件在加工过程中采取平行移动方式3 不允许中断4 每道工序只在一台机器上完成5 工件数 机器数和加工时间已知 加工时间与加工顺序无关6 每台机器同时只能加工一个工件 符号 Ji 工件i i 1 2 nMj 机器j j 1 2 mPij Ji在Mj上的加工时间 Ji的总加工时间为Pi pijri Ji的到达时间 指Ji从外部进入车间 可以开始加工的最早时间di Ji的完工期限Ci Ji的完工时间 Ci ri wij pij ri Wi PiCmax 最长完工时间 Cmax max Ci 符号 Fi Ji的流程时间 即工件在车间的实际停留时间 Fi Ci ri Wi PiFmax 最长流程时间 Fmax max Fi Li 工件的延迟时间Wij Ji在Mj上加工之前的等待时间Wi Ji在加工过程中总的等待时间ai Ji的允许停留时间 符号 Li Ci di ri Pi Wi di Pi Wi di ri Fi ai 当Li 0 正延迟 说明Ji的实际完工时间超过了完工期限当Li 0 负延迟 说明Ji提前完工当Li 0 零延迟 Ji按期完工 Lmax 最长延迟时间 Lmax max Li 三 排序问题的分类和表示法 分类方法 机器工件目标函数 机器 单台机器的排序问题 多台机器的排序问题 工件加工路线 单件作业 Job Shop 排序问题 流水作业 Flow shop 排序问题 单件车间排序问题的基本特征 每个工件都有其独特的加工路线 工件没有一定的流向 流水车间排序问题的基本特征 每个工件的加工路线都一样 如车 铣 磨 这里指的是工件的加工流向一致 并不要求每个工件必须在每台机器上加工 如有的工件为车 磨 有的为铣 磨 不仅加工路线一致 而且所有工件在各台机器上的加工顺序也一样 这种排序称为排列排序 同顺序排序 如工件排序为 J1 J3 J2 则表示所有机器都是先加工J1 然后加工J3 最后加工J2 静态的排序问题动态的排序问题 单目标排序问题多目标排序问题 确定型排序问题随机型排序问题 Conway表示方法 4参数表示法 n m A B n工件数m机器数A车间类型 F代表流水作业排序问题P表示流水作业排列排序问题G表示一般单件作业排序问题m 1A空白 B目标函数 第二节流水作业排序问题 基本特征 工件的加工路线都一致 工件的流向一致 并不要求每个工件必须经过加工路线上每台机器加工 对于流水作业排序问题 工件在不同机器上的加工顺序不尽一致 流水作业排列排序问题 同顺序 排序问题 所有工件在各台机器上的加工顺序都相同 排列排序问题的最优解不一定是相应的流水作业排序问题的最优解 但一般是比较好的解 对于仅有2台和3台机器的特殊情况 排列排序问题下的最优解一定是相应流水作业排序问题的最优解 一 最长流程时间Fmax的计算 n m P Fmax 目标函数 最长流程时间最短 最长流程时间 加工周期 从第一个工件在第一台机器开始加工时算起 到最后一个工件在最后一台机器上完成加工时为止所经过的时间 Fmax等于排在末位的工件在车间的停留时间 等于一批工件的最长完工时间Cmax 设n个工件的加工顺序为S S1 S2 Sn Si排第i位加工的工件的代号 表示工件Si在机器Mk上的完工时间 表示工件Si在Mk上的加工时间 k 1 2 mi 1 2 n 按以下公式计算 11 1 k 1 2 m i 1 2 n 当ri 0 i 1 2 n时 Fmax 例11 1有一个6 4 P Fmax问题 其加工时间如表11 1所示 当按顺序S 6 1 5 2 4 3 加工时 求Fmax 表11 l加工时间矩阵 表11 2顺序S下的加工时间矩阵 二 n 2 F Fmax问题的最优算法 n项任务在两台机器的排序问题SchedulingnJobsonTwoMachinesn个工件都必须经过机器1和机器2的加工 即工艺路线是一致的 两台机器排序问题的目标 两台机器排序的目标是使最大完成时间 总加工周期 Fmax最短 Fmax的含义见如下的甘特图 GanttChart 多台机器排序的目标一般也是使最大完成时间 总加工周期 Fmax最短 1954年Johnson提出用ai表示Ji在M1上的加工时间 用bi表示Ji在M2上的加工时间 每个工件都按M1 M2的路线加工 Johnson指出 若min ai bj min aj bi 则Ji应排在Jj之前 按上关系式可以确定每两个工件的相对位置 从而可以得到n个工件的完整的顺序Johnson算法 从加工时间矩阵中找出最短的加工时间若它出现在M1上 则其对应的工件应尽可能往前排 若它出现在M2上 则其对应的工件应尽可能往后排划去已排序工件并重复上述步骤直至排完 例11 2求表11 3所示的6 2 F Fmax问题的最优解 表11 3加工时间矩阵 将工件2排第1位2将工件3排第6位23将工件5排第2位253将工件6排第3位2563将工件4排第5位25643将工件1排第4位256143 最优加工顺序为S 2 5 6 l 4 3 最优顺序下的Fmax 28 Johnson法则2 将所有ai bi的工件按ai值不减的顺序排成一个序列A 将所有ai bi的工件按bi值不增的顺序排成一个序列B 将A放到B之前 就构成了最优加工顺序 序列A为 2 5 6 1 序列B为 4 3 最优顺序为 2 5 6 l 4 3 应用Johnson法则求得的最优顺序中任意去掉一些工件时 余下的工件仍构成最优顺序 Johnson法则只是一个充分条件 不是必要条件 不符合这个法则的加工顺序 也可能是最优顺序 两台机器排序问题算法的扩展 ExtensiontoThreeMachines 一般情况下当机器数为3台以上时 就很难找到最优解了但是 对于n个工件由三台机器流水作业时 在满足某些条件后可以采用Johnson sLaw解决问题 设 A B C为三台机器 如果工件在三台机器上的加工时间满足以下条件 则可以转化为两台机器的排序问题 minAi maxBiorminCi maxBi定义 A i Ai Bi B i Bi Ci例 考虑以下问题 5个工件由3台机器加工 作业时间见下表 求 总加工周期最短的作业顺序 解 检查上表 发现 minAi 4maxBi 6minCi 6因此 满足以上条件 建立两台机器的作业时间表 应用Johnson法则 得出 总加工周期为 三 n m P Fmax问题的启发式算法 对于3台机器的流水车间排序问题 只有几种特殊类型的问题找到了有效算法 对于一般的流水车间排列排序问题 分支定界法 启发式算法 求一般n m P Fmax问题近优解 Nearoptimalsolution 的启发式算法 一 Palmer法 按斜度指标排列工件的启发式算法 工件斜度指标 k 1 2 n m为机器数 pik为工件i在Mk上的加工时间 按照各工件不增的顺序排列工件 可得出令人满意的顺序 11 4 例11 3有一个4 3 F Fmax问题 其加工时间如表11 5所示 用Palmer法求解 表11 5加工时间矩阵 解 对于本例 式 11 4 变成 k 1 2 3 pk1 pk3 p11 p13 1 4 3 p21 p23 2 5 3 p31 p33 6 8 2 p41 p43 3 2 1 按不增的顺序排列工件 得到加工顺序 l 2 3 4 和 2 l 3 4 这两个顺序都是最优顺序 Fmax 28 二 关键工件法 步骤 1 计算每个工件的总加工时间Pi pij 找出加工时间最长的工件C j m 将其作为关键工件 2 对于余下的工件 若pi1 pim 则按pi1不减的顺序排成一个序列Sa 若pi1 pim 则按pim不增的顺序排列成一个序列Sb 3 顺序 Sa C Sb 即为所求顺序 表11 6用关键工件法求解 总加工时间最长的为3号工件 三 CDS法 把Johnson算法用于一般的n m P Fmax问题 得到 m 1 个加工顺序 取其中优者 具体做法 按 和 合并组成新的 机器 l 1 2 m 1 合并 m 1 次 得到 m 1 个n 2 F Fmax问题 用Johnson算法求 m 1 次加工顺序 取其中最好的结果 L 1 按Johnson算法得到加工顺序 1 2 3 4 Fmax 28L 2 按Johnson算法得到加工顺序 2 3 1 4 Fmax 29取顺序 1 2 3 4 为最优顺序 四 相同零件不同移动方式下加工周期的计算 排序问题针对的是不同的零件 如果n个零件相同 则没有排序问题 零件在加工过程中采取的移动方式不同 会导致一批零件的加工周期不同 零件在加工过程中可以采用三种典型的移动方式 顺序移动平行移动平行顺序移动 第三节单件作业排序问题 每个工件都有其独特的加工路线 工件没有一定的流向单件作业的排序问题是最一般的排序问题 也是最复杂的一种排序问题R w Conway 作业计划理论 TheoryofScheduling 一 问题的描述 对于一般单件作业排序问题 描述一道工序 要用3个参数 i j和k i表示工件代号j表示工序号k表示完成工件i的第j道工序的机器的代号 用 i j k 来表示工件i的第j道工序是在机器k上进行的这样一件事用加工描述矩阵描述所有工件的加工要求 加工描述矩阵D 加工描述矩阵D的每一行描述一个工件的加工每一列的工序序号相同行表示不同的工件 列表示不同的工序 单件作业排序问题 n m G Fmax 加工描述矩阵D 每一行描述一个工件的加工 每一列的工序序号相同 加工时间矩阵T 与D相对应 单件作业排序问题 n m G Fmax 加工顺序矩阵S 每一行与机器相对应 每一列与工件相对应 单件作业排序问题 n m G Fmax 用方块图表示 二 一般n m G Fmax问题的启发式算法 对于一般的n m G Fmax排序问题 分支定界法或整数规划法 是无效算法 启发式算法是求解一般单件车间排序问题使用最多的方法 一 两种作业计划的构成 半能动作业计划 Semi activeschedule 各工序都按最早可能开 完 工时间安排的作业计划 能动作业计划 Activeschedule 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业划 无延迟作业计划 Non delayschedule 没有任何延迟出现的能动作业计划 延迟 有工件等待加工时 机器出现空闲 即使这段空闲时间不足以完成一道工序 能动作业计划和无延迟作业计划的生成方法 将每安排一道工序称作一 步 设 St t步之前已排序工序构成的部分作业计划 Ot 第t步可以排序的工序的集合Tk Ot 中工序Ok的最早可能开工时间T k Ot 中工序Ok的最早可能完工时间 1 能动作业计划的构成步骤 1 设t l 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 否则 停止 得到加工顺序矩阵 2 无延迟作业计划的构成步骤 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 若还有未安排的工序 转步骤 否则 停止 得到加工顺序矩阵 二 三类启发式算法 能动作业计划和无延迟作业计划尽管不一定是最优作业计划 但一般是较好的作业计划 特别是无延迟作业计划能提供令人满意的解 一般能动作业计划和无延迟作业计划都有多个 可用启发式方法从中选择结果较好的作业计划 一般来说 以构成无延迟作业计划的步骤为基础的