《《精编》生产作业排序的问题》由会员分享，可在线阅读，更多相关《《精编》生产作业排序的问题（38页珍藏版）》请在金锄头文库上搜索。
1、生产作业排序 一 基本概念二 最长流程时间三 n 2 F Fmax问题的算法四 一般n m P Fmax问题的启发式算法五 单件车间排序问题 一 基本概念 1 排序排序就是要将不同的工作任务安排一个执行的顺序 使预定的目标最优化 实际上就是要解决如何按时间的先后 将有限的人力 物力资源分配给不同工作任务 使预定目标最优化的问题 一 基本概念 排序中常用的几个概念工件 Job 服务对象 机器 Machine Processor 服务者 如 n个零件在机器上加工 则零件是工件 设备是机器 工人维修设备 出故障的设备是工件 工人是机器 一 基本概念 所以 作业排序也就是要确定工件在机器上的加工顺序
2、可用一组工件代号的一种排列来表示 如可用 1 6 5 4 3 2 表示加工顺序 J1 J6 J5 J4 J3 J2 一 基本概念 2 作业计划 Scheduling 作业计划与排序不是一回事 它不仅要确定工件的加工顺序 而且还要确定每台机器加工每个工件的开工时间和完工时间 如果按最早可能开 完 工时间来编排作业计划 则排序完后 作业计划也就确定了 一 基本概念 3 排序问题的分类与表示1 单台机器与多台机器的排序问题 2 流水车间与单件车间排序问题 一 基本概念 流水车间排序问题的基本特征 每个工件的加工路线都一样 如车 铣 磨 这里指的是工件的加工流向一致 并不要求每个工件必须在每台机器上加
3、工 如有的工件为车 磨 有的为铣 磨 不仅加工路线一致 而且所有工件在各台机器上的加工顺序也一样 这种排序称为排列排序 同顺序排序 如工件排序为 J1 J3 J2 则表示所有机器都是先加工J1 然后加工J3 最后加工J2 一 基本概念 单件车间排序问题的基本特征 每个工件都有其独特的加工路线 工件没有一定的流向 一 基本概念 3 表示方法一般正规的表示方法为 n m A Bn 工件数 m 机器数 A 车间类型 F P G B 目标函数 一 基本概念 4 一般来说 排列排序问题的最优解不一定是相应流水车间排序问题的最优解 但一般是比较好的解 而对于仅有2台或3台机器的情况 则排列排序问题的最优解
4、一定是相应流水车间排序问题的最优解 一 基本概念 4 排序问题的假设条件一个工件不能同时在几台不同的机器上加工 工件在加工过程中采取平行移动方式 不允许中断 每道工序只在一台机器上完成 每台机器同时只能加工一个工件 工件数 机器数和加工时间已知 加工时间与加工顺序无关 二 最长流程时间 最长流程时间 加工周期 从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间 假定所有工件的到达时间都为0 则Fmax等于排在末位加工的工件在车间的停留时间 二 最长流程时间 计算Fmax的几个假定条件 机器M1不会发生空闲 对其它机器 能对某一工件加工必须具备2个条件 机器必
5、须完成排前一位的工件的加工 要加工的工件的上道工序已经完工 二 最长流程时间 二 最长流程时间 i pi1 pi2 pi3 pi4 6 1 5 2 4 3 2 5 5 1 4 4 5 4 4 4 5 3 2 5 8 2 1 7 5 3 3 6 7 4 2 6 10 12 13 16 7 11 15 20 27 33 12 17 22 30 35 42 13 21 25 32 38 46 三 n 2 F Fmax问题的算法 Johnson算法 假定 ai为工件Ji在机器M1上的加工时间 bi为工件Ji在机器M2上的加工时间 每个工件按M1 M2的路线加工 三 n 2 F Fmax问题的算法 Jo
6、hnson算法的步骤 从加工时间矩阵中找出最短的加工时间 若最短时间出现在M1上 则对应的工件尽可能往前排 若最短时间出现在M2上 则对应的工件尽可能往后排 若最短时间有多个 则任选一个 划去已排序的工件 若所有工件都已排序 则停止 否则重复上述步骤 四 一般n m P Fmax问题的启发式算法 对于一般的n m P Fmax问题 可以用分支定界法求得最优解 但计算量很大 实际中 可以用启发式算法求近优解 四 一般n m P Fmax问题的启发式算法 1 Palmer法计算工件斜度指标 i m 机器数pik 工件i在机器k上的加工时间 i 1 2 n排序方法 按 i从大到小的顺序排列 按排序的
7、顺序计算Fmax 四 一般n m P Fmax问题的启发式算法 2 关键工件法 计算Pi Pij 找出Pi最长的工件 将之作为关键工件C 对其余工件 若Pi1 Pim 则按Pi1由小到大排成序列SA 若Pi1 Pim 则按Pim由大到小排成序列SB 顺序 SA C SB 即为近优解 四 一般n m P Fmax问题的启发式算法 得到的加工顺序为 1 2 3 4 四 一般n m P Fmax问题的启发式算法 3 CDS法 CDS法是Johnson算法的扩展方法 从M 1个排序中找出近优解 四 一般n m P Fmax问题的启发式算法 L 1 按Johnson算法得到加工顺序 1 2 3 4 Fm
8、ax 28L 2 按Johnson算法得到加工顺序 2 3 1 4 Fmax 29取顺序 1 2 3 4 为最优顺序 五 单件车间排序问题 n m G Fmax 1 问题描述 i j k 表示工件i的第j道工序是在机器k上进行 加工描述矩阵D 每一行描述一个工件的加工 每一列的工序序号相同 五 单件车间排序问题 n m G Fmax 加工时间矩阵T 与D相对应 五 单件车间排序问题 n m G Fmax 加工顺序矩阵S 每一行与机器相对应 每一列与工件相对应 S 1 1 12 2 1 1 3 22 3 2 2 1 31 2 3 五 单件车间排序问题 n m G Fmax 用方块图表示 五 单件
9、车间排序问题 n m G Fmax 2 能动作业计划的构成各工序都按最早可能开 完 工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序 符号说明 Ot 第t步可以排序的工序的集合 St t步之前已排序的工序构成的部分作业计划Tk Ot 中工序Ok的最早可能开工时间T k Ot 中工序Ok的最早可能完工时间 五 单件车间排序问题 n m G Fmax 能动作业计划的构成步骤 设t 1 St 为空 Ot 为各工件第一道工序的集合 求最小的最早完工时间T min T k 并找到出现T 的机器M 若有多台 任选一台 从 Ot 中跳出满足以下两条件的工序Oj需要机器M 加工 Tj T 将确
10、定的Oj放入 St 从 Ot 中消去Oj并将Oj的紧后工序放入 Ot 中 使t t 1 若还有未安排的工序 转步骤 否则 停止 一个实例 i 1 Ot Tk T k T M Oj 1 1 1 0 2 2 M1 1 1 1 2 1 3 0 3 2 1 2 3 2 6 3 M3 2 1 3 2 1 3 0 3 3 1 2 3 3 7 7 M3 1 2 3 2 2 1 3 7 4 1 3 2 7 8 7 M1 2 2 1 2 2 1 3 7 5 1 3 2 7 8 8 M2 1 3 2 2 3 2 7 12 6 13 M2 2 3 2 2 3 2 8 13 得到加工顺序矩阵 1 1 1 2 1 3
11、1 2 3 2 2 1 1 3 2 2 3 2 M1 M2 M3 2 3 7 7 3 8 13 五 单件车间排序问题 n m G Fmax 3 无延迟作业计划的构成没有任何延迟出现的能动作业计划 所谓 延迟 指有工件等待加工时 机器出现空闲 即使这段空闲时间不足以完成一道工序 构成步骤 五 单件车间排序问题 n m G Fmax 无延迟作业计划的构成步骤 设t 1 St 为空 Ot 为各工件第一道工序的集合 求最小的最早完工时间T min Tk 并找到出现T 的机器M 若有多台 任选一台 从 Ot 中跳出满足以下两条件的工序Oj需要机器M 加工 Tj T 将确定的Oj放入 St 从 Ot 中消
12、去Oj并将Oj的紧后工序放入 Ot 中 使t t 1 若还有未安排的工序 转步骤 否则 停止 一个实例 i 1 Ot Tk T k T M Oj 1 1 1 0 2 0 M1 1 1 1 2 1 3 0 3 2 1 2 3 2 6 0 M3 2 1 3 2 1 3 0 3 3 1 2 3 3 7 3 M3 1 2 3 2 2 1 3 7 4 1 3 2 7 8 3 M1 2 2 1 2 2 1 3 7 5 1 3 2 7 8 7 M2 2 3 2 2 3 2 7 12 6 12 M2 1 3 2 2 3 2 12 13 0 M3 3 M1 7 M2 得到加工顺序矩阵 1 1 1 2 1 3 1
13、 2 3 2 2 1 1 3 2 2 3 2 M1 M2 M3 2 3 7 7 3 12 13 4 启发式算法 能动作业计划和无延迟作业计划尽管不一定是最优作业计划 但一般是较好的作业计划 特别是无延迟作业计划能提供令人满意的解 一般能动作业计划和无延迟作业计划都有多个 可用启发式方法从中选择结果较好的作业计划 一般来说 以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好 五 单件车间排序问题 n m G Fmax 优选调度法则 SPT ShortestProcessingTime 法则 优先选择加工时间最短的工序 FCFS FirstComeFi
14、rstServed 法则 优先选择最早进入可排工序集合的工件 EDD EarliestDueDate 法则 优先选择完工期限紧的工件 MWKR MostWorkRemaining 法则 优先选择余下加工时间最长的工件 LWKR LeastWorkRemaining 法则 优先选择余下加工时间最短的工件 MOPNR MostOperationsRemaining 法则 优先选择余下工序数最多的工件 五 单件车间排序问题 n m G Fmax 优选调度法则 按SPT法则可使工件的平均流程时间最短 从而减少在制品量 FCFS法则来自排队论 它对工件较公平 EDD法则可使工件最大延误时间最小 SCR也是保证工件延误最少的法则 MWKR法则使不同工作量的工件的完工时间尽量接近 LWKR法则 使工作量小的工件尽快完成 MOPNR法则与MWKR法则类似 只不过考虑工件在不同机器上的转运排队时间是主要的 五 单件车间排序问题 n m G Fmax
