生产计划_生产作业计划教材

第八章生产作业计划OperationsSchedulingandControlling 第一节生产作业排序第二节生产作业控制 第一节生产作业排序一 基本概念 1 排序排序就是要将不同的工作任务安排一个执行的顺序 使预定的目标最优化 实际上就是要解决如何按时间的先后 将有限的人力 物力资源分配给不同工作任务 使预定目标最优化的问题 排序的作用油漆生产顺序 某企业生产白 灰 红 蓝四种油漆 每次生产前都有清洗容器的调整准备时间 按怎样的顺序 总的调整准备时间最少 复印排序问题 有四人同时到达复印室 每人的复印量不同 如何安排顺序 使得他们的平均等待时间和平均流程时间最小 方案1 白 灰 红 蓝T setup 12方案2 蓝 红 灰 白T setup 20 排序中常用的几个概念工件 Job 服务对象 机器 Machine Processor 服务者 如 n个零件在机器上加工 则零件是工件 设备是机器 工人维修设备 出故障的设备是工件 工人是机器 所以 作业排序也就是要确定工件在机器上的加工顺序 可用一组工件代号的一种排列来表示 如可用 1 6 5 4 3 2 表示加工顺序 J1 J6 J5 J4 J3 J2 2 作业计划 Scheduling 作业计划是安排零部件 作业 活动 的出产数量 设备及人工使用 投入时间及出产时间 作业计划与排序不是一回事 它不仅要确定工件的加工顺序 而且还要确定每台机器加工每个工件的开工时间和完工时间 如果按最早可能开 完 工时间来编排作业计划 则排序完后 作业计划也就确定了 3 排序问题的分类与表示根据机器数的多少单台机器的排序问题多台机器的排序问题根据加工路线的特征单件作业排序 JobShop 流水型排序 FlowShop 流水作业排序问题的基本特征 每个工件的加工路线都一样 如车 铣 磨 这里指的是工件的加工流向一致 并不要求每个工件必须在每台机器上加工 如有的工件为车 磨 有的为铣 磨 不仅加工路线一致 而且所有工件在各台机器上的加工顺序也一样 这种排序称为排列排序 同顺序排序 如工件排序为 J1 J3 J2 则表示所有机器都是先加工J1 然后加工J3 最后加工J2 单件车间排序问题的基本特征 每个工件都有其独特的加工路线 工件没有一定的流向 表示方法一般正规的表示方法为 n m A Bn 工件数 m 机器数 A 作业类型 F P G B 目标函数 4 排序常用的符号Ji 工件i i 1 2 nMj 机器 j 1 2 mdi 工件i的交货期pij 工件i在机器j上的加工时间 j 1 mPi 工件i的加工时间 Wi 工件i在系统内的等待时间 wij 工件i在机器j前的等待时间 j 1 m Ci 工件i的完成时间 在工件都已到达的情况下 Ci Pi WiFi 工件i的流程时间 在工件都已到达的情况下 Fi Pi WiLi 工件i的延误时间 Li Ci di Li0延误Ti 工件i的延期量 Ti max 0 Li Ei 工件i提前完成的时间 5 排序问题的假设条件工件同时到达 一个工件不能同时在几台不同的机器上加工 工件在加工过程中采取平行移动方式 不允许中断 每道工序只在一台机器上完成 每台机器同时只能加工一个工件 工件数 机器数和加工时间已知 加工时间与加工顺序无关 二 两台机器的排序问题 1 两台机器排序问题的含义n个工件都必须经过机器1和机器2的加工 即工艺路线是一致的 2 最长流程时间最长流程时间 加工周期Fmax 从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间 假定所有工件的到达时间都为0 则Fmax等于排在末位加工的工件在车间的停留时间 计算Fmax的几个假定条件 机器M1不会发生空闲 对其它机器 能对某一工件加工必须具备2个条件 机器必须完成排前一位的工件的加工 要加工的工件的上道工序已经完工 3 Fmax问题的算法两台机器排序的目标是使Fmax最短 假定 ai为工件Ji在机器M1上的加工时间 bi为工件Ji在机器M2上的加工时间 每个工件按M1 M2的路线加工 Johnson算法 从加工时间矩阵中找出最短的加工时间 若最短时间出现在M1上 则对应的工件尽可能往前排 若最短时间出现在M2上 则对应的工件尽可能往后排 若最短时间有多个 则任选一个 划去已排序的工件 若所有工件都已排序 则停止 否则重复上述步骤 例 某一班组有A B两台设备 要完成5个工件的加工任务 每个工件在设备上的加工时间如下表所示 求总加工周期最短的作业顺序 解 由约翰逊法可知 表中最小加工时间值是1个时间单位 它又是出现在设备1上 根据约翰逊法的规则 应将对应的工件4排在第一位 即得 J4 去掉J4 在剩余的工件中再找最小值 不难看出 最小值是2个时间单位 它是出现在设备2上的 所以应将对应的工件J1排在最后一位 即 J4 J1 再去掉J1 在剩余的J2 J3 J5中重复上述步骤 求解过程为 J4 J5 J1J4 J2 J5 J1J4 J2 J3 J5 J1当同时出现多个最小值时 可从中任选一个 最后得J4 J2 J3 J5 J1 a J1 J2 J3 J4 J5 b J4 J2 J3 J5 J1 可以看出 初始作业顺序的总加工周期是30 用约翰逊法排出的作业顺序总加工周期是26 显然后者的结果优于前者 N项任务 三台设备的排序例 三台设备 8项任务 各任务的工艺顺序相同 资料如下 求最优解条件 满足如下条件之一 求解步骤 1 把三台设备转换为两台假象设备 假想设备加工时间按如下公式转换 用约 贝规则求得排序结果如下 J8 J2 J5 J6 J1 J3 J7 J4 或 J4 J7 上例中 满足条件 转换两台假想设备 结果如下表 三 一般n m P Fmax问题的启发式算法 对于一般的n m P Fmax问题 可以用分支定界法求得最优解 但计算量很大 实际中 可以用启发式算法求近优解 1 Palmer法计算工件斜度指标 i m 机器数pik 工件i在机器k上的加工时间 i 1 2 n排序方法 按 i从大到小的顺序排列 按排序的顺序计算Fmax 2 关键工件法 计算Pi Pij 找出Pi最长的工件 将之作为关键工件C 对其余工件 若Pi1 Pim 则按Pi1由小到大排成序列SA 若Pi1 Pim 则按Pim由大到小排成序列SB 顺序 SA C SB 即为近优解 得到的加工顺序为 1 2 3 4 关键工件法举例 找出关键工件 工作负荷最大的40 对应的是工件6 所以JC J6 确定排在关键工件前面的工件 满足步骤2条件的有J1 J4 J5 所以有SA J4 J5 J1 确定排在关键工件后面的工件 满足步骤3条件的有J2 J3 所以有SB J2 J3 最后有 J4 J5 J1 J6 J2 J3 3 CDS法 CDS法是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个零件在某个加工中心的排序排序的优先规则主要有 先到的先服务 FCFS 加工时间短的优先加工 SPT 交货期早的先加工 EDD 最短松弛时间先加工 LS 某项任务距计划交货期的剩余时间与该任务的作业时间之差 随机加工 比较研究 例 有5个任务到达 原始排序是 1 先到的先服务 FCFS 2 加工时间短的优先加工 SPT 3 交货期早的先加工 EDD 4 最短松弛时间先加工 LS 优先调度规则比较 零件在加工过程中的移动方式 包括 顺序移动方式 平行移动方式 平行顺序移动方式 五 相同零件 不同移动方式下加工周期的计算 1 顺序移动方式一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工 优点 设备利用率高 移动次数少缺点 加工周期长 管理工作复杂常用于单件或成批生产过程 工艺原则 T顺 nt1 nt2 ntn n ti 2 平行移动方式每个零件在前道工序加工完毕后立即转移到下道工序继续加工 形成前后工序交叉作业 优点 加工周期短 管理工作简单缺点 设备利用率低 移动次数多常用于装配流水线 大量生产过程 对象原则 T平 ti n 1 tl n 4件 m 4工序t1 10分钟 件 t2 5分钟 件 t3 20分钟