matlab生产调度问题及其优化算法

生生产产调调度度问问题题及及其其优优化化算算法法 采采用用遗遗传传算算法法 与与 M MA AT TL LA AB B 编编程程 信信息息 0 01 14 4 孙孙卓卓明明 二二零零零零 三三年年八八月月十十四四日日 1 生生产产调调度度问问题题及及其其优优化化算算法法 背景及摘要 这是一个典型的 Job Shop 动态排序问题 目前调度问题的理论研究成果主 要集中在以 Job Shop 问题为代表的基于最小化完工时间的调度问题上 一个复 杂的制造系统不仅可能涉及到成千上万道车间调度工序 而且工序的变更又可 能导致相当大的调度规模 解空间容量巨大 N 个工件 M 台机器的问题包含 种排列 由于问题的连环嵌套性 使得用图解方法也变得不切实际 传 M N 统的运筹学方法 即便在单目标优化的静态调度问题中也难以有效应用 本文给出三个模型 首先通过贪婪法手工求得本问题最优解 既而通过编 解码程序随机模拟优化方案得出最优解 最后采用现代进化算法中有代表性发 展优势的遗传算法 文章有针对性地选取遗传算法关键环节的适宜方法 采用 MATLAB 软件实现算法模拟 得出优化方案 并与计算机随机模拟结果加以比较 显示出遗传算法之优化效果 对车间调度系列问题的有效解决具有一定参考和 借鉴价值 一 问题重述 某重型机械厂产品都是单件性的 其中有一车间共有 A B C D 四种不 同设备 现接受 6 件产品的加工任务 每件产品接受的程序在指定的设备上加 工 其工序与加工周期如下表 S 设备号 T 周期 12345678工序工序 产品产品 STSTSTSTSTSTSTST 1C8A2B4C24D6 2A4D5B3C4 3C3D7A15B20A8 4B7C6D21A1D16C3 5D10B4C8D4A12C6D1 6A1B4A7C3D5A2C5A8 表一 条件 1 每件产品必须按规定的工序加工 不得颠倒 2 每台设备在同一时间只能担任一项任务 每件产品的每个工序为一个任务 问题 做出生产安排 希望在尽可能短的时间里 完成所接受的全部任务 要求 给出每台设备承担任务的时间表 注 在上面 机器 A B C D 即为机器 1 2 3 4 程序中以数字1 2 3 4表示 说明时则用A B C D 2 二 模型假设 1 每一时刻 每台机器只能加工一个工件 且每个工件只能被一台机器所加 工 同时加工过程为不间断 2 所有机器均同时开工 且工件从机器 I 到机器 J 的转移过程时间损耗不计 3 各工件必须按工艺路线以指定的次序在机器上加工多次 4 操作允许等待 即前一操作未完成 则后面的操作需要等待 可用资源有 限 三 符号说明及初始数据表达分析 第i个工件 i 1 6 i J 机器顺序阵 表示i工件的第 j个操作的机器号 M J jiJM 第j台机器 j 1 4 j M 工件排列阵 表示i机器上第j次加工的工件号 J M jiM J 加工时间阵 为i工件的第 j个操作的时间周期T jiT 整个任务完成时间C 整理数据后得到 C A B C D 0 0 0 8 2 4 24 6 0 0 0 M JT A D B C 0 0 0 0 4 5 3 4 0 0 0 0 C D A B A 0 0 0 3 7 15 20 8 0 0 0 B C D A D C 0 0 7 6 21 1 16 3 0 0 D B C D A C D 0 10 4 8 4 12 6 1 0 A B A C D A C A 1 4 7 3 5 2 5 8 上述二阵直接从题目得出 而则是我们要求的 J M 关于工件的加工时间表关于工件的加工时间表 表二 产品 工件 i 123456总计 总净加工时间 周期 i J441653544535247 加工工序总数 个 i J54567835 关于机器的加工时间表关于机器的加工时间表 表三 机器 设备 j ABCD总计 总净加工时间 j M60427075247 加工操作次数 j M10610935 分析 分析 由于各产品总净加工时间和各机器总净加工时间之中最大值为 75 而总计为247 3 那么 总时间总时间 C C 介于介于 75 75 247 247 同时各工件加工繁杂程度不一 各机器的任务量也有轻 重之别 合理的调度排序是对于节省时间和资源是必要的 希望最优化答案是75 这样达到最小值 如果答案是75 那么意味着机器D不间断工 作 直至全部加工任务完成 四 贪婪法快速求解 如果按照一定规则排序 当多个工件出现 抢占 同一机器的局面的时候 我 们可以制定如下的工序安排规则 1 优先选择总剩余时间或总剩余操作较多的工件 如果出现总剩余加工时 间多者总剩余操作数反而较少的情况时 按照程度具体情况具体分析 2 机器方面来说 尽量避免等待空闲时间 优先考虑剩余净加工时间或者剩余 加工总次数较多的机器 尤其是机器 D 即倘若能够使机器D不间断工作且 其他机器完工时间均不多余75时 那么就可以得到最优解 首先按照最优化时间为75的设想避免D出现等待 排序后得到升以下具体 排列顺序 各机器承担任务表为 其中粗体字为对应工件产品号 括号内为对应时间周期段 操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10 A A 6 6 1 2 2 2 5 1 1 12 13 6 6 14 20 3 3 21 35 4 4 36 5 5 43 54 6 6 55 56 3 3 57 64 6 6 66 73 B B 4 4 1 7 6 6 8 11 5 5 12 15 1 1 16 19 3 3 36 55 2 2 56 58 C C 3 3 1 3 1 1 4 11 4 4 12 17 5 5 18 25 6 6 26 28 1 1 29 52 5 5 55 60 6 6 61 65 2 2 66 69 4 4 70 72 D D 5 5 1 10 3 3 11 17 4 4 18 38 5 5 39 42 6 6 43 47 2 2 48 52 4 4 53 68 1 1 69 74 5 5 75 表四 10 3 7 1 7 8 4 4 21 6 4 6 4 8 4 2 5 3 16 7 5 24 20 15 16 2 3 1 6 6 6 1 5 12 4 2 3 88 1 01020304050607080 D机机器器 C机机器器 B机机器器 A机机器器 4 图一 上图为加工周期图 甘特图 标注数字为相应操作的周期 完工时间为第 75 周期 五 计算机随机模拟 编程 1 1 编码 编码 随机产生生产的工序操作优先顺序 进行编码 如 K 4 3 5 6 6 2 3 1 4 1 6 3 5 4 5 3 6 6 4 1 5 5 1 3 2 6 2 2 4 4 1 5 6 6 5 注 同时作为下文的染色 体之用 意思为 工件 4 优先被考虑进行第一次操作 然后 3 进行其第一 步操作 然后 5 操作 6 操作 再 6 操作其第二步工序 依次进行 如果 前后互相不冲突 则可同时在不同机器上操作 通过排列组合得出 总共有类似 K 的排列序列 2多种 23 10 当然 这其中只对应解 75 247 意味着有大量排列序列对应同一加工 方案 而大量加工方案又对应同一时间解 2 解码 解码 即对编码进行翻译 产生具体可操作工序安排方案 这里采用活动活动 化解码化解码算法 例如工件 2 第 i 步操作 记为 2 i 且在机器 A 上进 M J 行 被安排在工件 3 第 j 步操作 记为 JM 3 j 后面进行 那么如果安 排好 M J 3 j 后 只要 2 i 在工件 2 已经排序好的操作之后进行 那么操 M J 作 2 i 可插入到机器 A 处最前可安置的时间段进行 M J 在这里 一个编码序列对应一个加工方案 而一个加工方案可对应一 个或多个编码序列 这就是二者之关系 3 编程 编程 通过一组随机编码产生一生产加工优先序列 通过解码过程产生相应 加工方案及其总耗费时间 C N 次模拟后即可得出解 C 的概率密度分布情 况以及相对最优解 N 个 C 的最小值 如 80 77 等 甚至出现 75 4 计算机模拟所得数据分析 计算机模拟所得数据分析 a 进行 100 次模拟得出最优解情况 共运行 10 次 82 83 82 84 78 80 81 83 87 82 平均值 82 2 每回耗时约 3 秒 b 进行 1000 次模拟得出最优解情况 共运行 10 次 80 79 78 78 79 79 76 80 77 78 平均值 78 4 每回耗时 25 秒 5 c 进行 10000 次模拟得出最优解情况 共运行 10 次 76 77 77 75 76 76 77 76 76 77 平均值 76 3 每回耗时 4 分钟 d 模拟 1000000 次得到的解 C 的概率密度分布情况为 如图二所示 图二 注 75 处为 17 次 概率为 17 1000000 1 58823 76 处为 40 次 77 处 167 次 结论 结论 如果想将 2中排序序列以平均出现一次的可能性进行模拟 23 10 即运行 2次 计算机需运行将近 150 万亿年 当然 我们没有这个 23 10 必要 因为我们只需要运行数万次 就很可能得到最优解 75 在随机 在随机 模拟模拟 1000000 次后出现次后出现 17 次次 75 那么意味着概率大约 那么意味着概率大约 17 1000000 1 58823 另外 另外 76 处为处为 40 次 次 77 处处 167 次 次 六 遗传算法模型建立和步骤解法 遗传算法 Genetic Algorithm 作为一种优化算法特别适合于对象模型难 于建立 搜索空间非常庞大的复杂问题的优化求解 它和模糊控制技术一样 虽然在理论上还没有完善 但是在实践中已经得到了广泛的应用 遗传算法的 基本思想是 模仿生物系统 适者生成 的原理 通过选择 复制 交叉 变异 等简单操作的多次重复来达到去劣存优的目的 从而获得问题的优化结果 遗 传算法的实现由两个部分组成 一是编码与解码 二是遗传操作 其中遗传操 作又包括选择 复制 交叉 变异等步骤 本文根据实际情况采取了 1 6 整数编码 数字 1 2 3 4 5 6 分别代表 6 件待加工产品 本文遗传算法基本流程 通过编码 解码程序随机产生 N 个 有一定数量 如 50 或 100 个体构成初始种群 a 从初始中群中选取 2 个具有最优染色体 最有排序方案 的个体作为临时个体 父代 b 如果此 2 个体中有一个个体通过解码操作能够实现最优排序 即使总时间为 75 周期 那么结束此算法 得到最优解 6 c 对 2 个临时个体以一定方式 循环交叉 执行染色体交叉变换和变异选择 小概率 互换 操作 产生 2 个新的个体 d 对父代和子代共 4 个个体进行选择 从中选出最佳的 2 个个体 做为下一代的父代 e 重复执行第二步 b 操作 f 如果执行完 M 步后仍然未得出答案 75 那么将目前的最优解作为本算法的最优解答案 1 1 编码和解码 编码和解码 同上 同上 2 2 交叉变换 交叉变换 crossover crossover 对 2 个父代临时个体进行染色体交叉变换 采用循环交叉方法循环交叉方法 Cycle crossover CX 如父代染色体为 X 9 2 6 4 7 3 5 8 1 和 Y 3 4 5 8 1 6 7 2 9 如果 随机选到第二位开始交叉 那么 X 的 2 对应 Y 的 4 X 的 4 对应 Y 的 8 X 的 8 对应 Y 的 2 这样就确定了以上为不变的染色体 其余位置的染色体互换位置 最后得到 X 3 2 5 4 1 6 7 8 9 9 4 6 8 7 3 5 2 1 实现交叉变换 Y 3 3 变异选择 变异选择 mutationmutation 采用互换操作互换操作 SWAP 即随机交换染色体中两不同基因的位置 如上面的染 色体为 3 2 5 4 1 6 7 8 9 随机产生变换位置号 如产生随机数 3 和 5 X 那么交换数字后得到染色体 3 2 1 4 5 6 7 8 9 变异概率取 0 1 4 4 选择操作 选择操作 selectionselection 对父代 2 个体 f1 f2 和子代 2 个体 f3 f4 进行选择 通过编码操作确定具有最优 解的 2 个个体 成为新一代 f1 和 f2 如此 通过多次编码和解码随机产生一定数量的个体 选取 2 个最佳个体进行交叉变 换操作 产生 2 个新个体 然后对 4 个个体进行选择 产生下一代 如果某时刻通过解码 操作得出最优解 所有解的下限 这里是 75 周期 那么算法结束 否则循环进行 直至 预先给定的循环次数达到为止 以最后得到的最优解作为最终最优解 七 遗传算法模拟 采用 MATLAB 工具编程 主程序如下 子程序见略 本程序为主程序 调用以下各分支程序 task Welcome Wait a moment please Writer 孙 卓 明 信息 014 f1 zeros 1 35 f2 zeros 1 35 while f1 f2 此步避免初始染色体 f1 f2 相同 导致以下死循环 minminmax1 s1 chushijie N N 种群初始化 基于操作的编码策略 活动化解码算法 chushijie N 参数 N 为初始种群数 f1 s1 minminmax1 选取的第一个初始个体 minminmax2 s2 chushijie N N 再次种群初始化 f2 s2 minminmax2 选取的第二个初始个体 end 7 for e 1 M M e 1 M 进行 M 次遗传操作 交叉 变异 选择 D jiaocha f1 f2 交叉变化 循环交叉操作 cycle crossover CX 选 取 f1 f2 染色体 无需变动部分基因 f3 f4 jiaocha bianyi f1 f2 D 生成交叉后的 染色体 并进行变异选择 f3 f4 f1 f2 xuanze f1 f2 f3 f4 选择 对父代 f1 f2 和子代 f3 f4 进行解码 得出 2 个 f1 f2 较优个体 成为下一代的父代 minmaxf1 a1 b1 tongbujinzhan f1 求该时刻个体 f1 的最优时间 因为 f1 优于 f2 if minmaxf1 75 f1 a1 b1 minminmax1 minminmax2 minminmax last minmaxf1 task Finish Successful Best answer Congratulation return end end f1 a1 b1 minminmax1 minminmax2 minminmax last minmaxf1 if minminmax last 90 task Finish Action again please end if minminmax last 80 task Finish end if minminmax last 80 task Finish Successful end 八 遗传算法模拟结果 首先给出最优方案 在进行某次 n 100 m 200n 100 m 200 的操作后得到模拟最优结果 75 周期时间 minminmax1 83 minminmax2 78 二个初始较优个体解 f1 4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3 1 5 2 6 4 5 6 4 6 6 4 3 2 2 5 1 1 f1 为各工件优先选择顺序排列 即 染色体 a1 5 35 39 64 0 0 0 0 0 a1 b1 为四台机器空闲周期段 15 24 0 0 0 0 0 0 0 17 53 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 b1 11 38 42 65 0 0 0 0 0 20 35 0 0 0 0 0 0 0 18 54 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 m mi in nm mi in nm ma ax x 7 75 5 最终最优解 其中机器 A 空闲时间段为 5 11 35 38 39 42 64 65 机器 B 则为 15 20 24 35 机器 C 为 17 18 53 54 65 68 机器 D 无空闲 以下为 取不同 N 和 M 值情况下数据优化过程以及时间上的比较 表五 NNM 第一次运行第二次运行第三次运行第四次运行第五次运行平均运行时间 111104 114 989898 105 939392 93 9292100 132 959586 86 8484 1110106 97 8686108 100 8989102 87 878799 90 909088 104 8484 1110094 81 818181 102 787891 105 9191101 84 808090 101 9090 111000107 100 787892 101 7676101 100 82 8288 97 868691 93 87878 5 s 111000088 105 7777103 81 777789 99 8484107 104 787893 105 787880 s 8 10101090 108 9090104 91 8383104 100 939395 98 8787105 106 8787 101010098 96 969693 99 909088 90 8080105 92 808091 95 8585 10101000101 96 787891 89 808096 104 8787105 105 848488 99 78789 5 s 10101000099 92 777797 95 757596 104 767689 99 767691 101 757590 s 10010010095 100 868698 90 8080104 99 787893 88 81 8192 99 8080 1001001000109 98 858591 100 8282100 99 7777114 101 84 8496 110 767611 s 1001001000096 101 7878101 86 7676101 97 808099 110 767699 111 7777100 s 说明 以最后一行第一次运行 96 101 78 为例 96 和 101 分别为 2 次 N 取 100 时得到的 100 2 个随机解中的最优解 78 为经过 M 10000 代的遗传 交叉变异选择 后得到的最终最优解 明显地发现 M 的增大所产生的优化效果明显好于 N 增大产生的优化效果 M 从 1 10 100 1000 10000 的变化使最优解有从 9 8 7 的变化规律 N 的 1 10 100 的变化则不明显 因此相对于随机取解 经过遗传算法优化之后效果是显著的 另外对采用遗传算法前后模拟所得数据进行比较 第一次第二次第三次第四次第五次均值平均时间 N 1000 M 0 78 79 818079 79 4 25 S N 1 N 1 M 1000 80 75 77 7682 78 0 8 5 S 表六 由上表看来 虽然在均值方面相差不显著 但是时间上采用遗传算法之后 节约了约三分之二的运行时间 效率显而易见 九 模型优缺点及改进 模型优点 采用遗传算法可对一个理论上无法求尽的 NP 问题以较有效方 法在较短时间内得到较精确解 缺点 采用遗传算法还不全面 只是一个简单模型 未考虑收敛性 适配 值等 对参数设置与最优解关系研究还不够深入 模型本身还具有漏动 仍需改进 较好设想为采用和模拟退火算法的混 合遗传算法 由于时间紧迫 在此就不再深入给出模型及分析了 参考文献 1 车间调度与遗传算法 王凌 清华大学出版社 2 数值计算的算法与分析 张可村 赵英良 科学出版社 3 Permutation Based GAs and Ordered Greed Peter G Anderson 4 MATLAB6 0 与科学计算 王沫然 电子工业出版社 5 C 程序设计 第二版 潭浩强 清华大学出版社 9 信息 014014 孙 卓 明 20032003 年 8 8 月 1414 日 本文网上下载地址 个人主页 附录 子程序一 种群初始化 得较优个 体 function minminmax ss chushijie n 种群初始化 以下为编码和解码过程 同时对 n 次 选取最优化个体 Jm 3 1 2 3 4 0 0 0 1 4 2 3 0 0 0 0 3 4 1 2 1 0 0 0 2 3 4 1 4 3 0 0 4 2 3 4 1 3 4 0 1 2 1 3 4 1 3 1 minminmax 200 for d 1 n s 0 编码程序 基于操作的编码策略 k 1 for t 1 35 I randint 1 1 1 6 while Jm I 1 0 I randint 1 1 1 6 end s k I k k 1 x 1 while x 7 Jm I x Jm I x 1 x x 1 end Jm I 8 0 end Jm 3 1 2 3 4 0 0 0 1 4 2 3 0 0 0 0 3 4 1 2 1 0 0 0 2 3 4 1 4 3 0 0 4 2 3 4 1 3 4 0 1 2 1 3 4 1 3 1 T 8 2 4 24 6 0 0 0 4 5 3 4 0 0 0 0 3 7 15 20 8 0 0 0 7 6 21 1 16 3 0 0 10 4 8 4 12 6 1 0 1 4 7 3 5 2 5 8 解码程序 活动化解码算法 for i 1 6 k i 1 end for q 1 4 for x 1 9 a q x 0 b q x 0 flag q 0 end end for p 1 6 flag p 0 end for i 1 35 q Jm s i k s i t T s i k s i z 0 v 0 for x 1 9 if max flag s i a q x t b q x if flag s i a q x flag s i b q x for y x 8 a q y a q y 1 b q y b q y 1 end z 1 elseif flag s i a q x flag s i b q x b q x b q x t z 1 10 elseif flag s i a q x for y 8 x 2 a q y a q y 1 b q y b q y 1 end b q x 1 b q x b q x flag s i a q x 1 flag s i t flag s i a q x 1 z 1 end end end if z 0 if flag s i flag q for x 1 9 if a q x 0 a q x flag q b q x flag s i v 1 end end flag s i flag s i t flag q flag s i end end k s i k s i 1 end minmax 0 for q 1 4 if minmaxminmax 得出初始最优解 minminmax minmax ss s end end 子程序二 父代交叉变换 function D jiaocha f1 f2 交叉变 化 循环交叉操作 CX 选取 染色体 无需变 动部分基因 s randint 1 1 1 35 while f1 s f2 s s randint 1 1 1 35 end for p 1 34 D p 0 end z 0 j 1 D j s j j 1 for i 1 35 if f1 i f2 s D j i j j 1 z 1 end end if f2 D j 1 f1 s return end for m 1 34 z 0 for i 1 35 if f1 i f2 D j 1 w 0 for t 3 j if i D t 1 0 i D t 1 0 g1 D i f1 D i g2 D i f2 D i 11 end end f3 g1 f4 g2 c randint 1 1 1 100 if c 1 d1 randint 1 1 1 35 d2 randint 1 1 1 35 while d1 d2 d2 randint 1 1 1 35 end m f3 d1 f3 d1 f3 d2 f3 d2 m elseif c 2 d1 randint 1 1 1 35 d2 randint 1 1 1 35 while d1 d2 d2 randint 1 1 1 35 end m f4 d1 f4 d1 f4 d2 f4 d2 m end 子程序四 四者中选取最优二个体 function f1 f2 xuanze f1 f2 f3 f4 对父代 f1 f2 和子代 f3 f4 进行解码 得出 2 个 较优个体 成为下一代的父代 min1 0 min2 0 min3 0 min4 0 h 0 g 0 min1 tongbujinzhan f1 min2 tongbujinzhan f2 min3 tongbujinzhan f3 min4 tongbujinzhan f4 if min1 min2 h f1 if min2 min3 g f2 elseif min3 min2 g f3 elseif min4 min2 g f4 end elseif min2 min1 h f2 if min1 min3 g f1 elseif min3 min1 g f3 elseif min4 min1 g f4 end elseif min3 min1 h f3 if min