求解一类订单调度问题的遗传算法研究

摘要

订单调度问题可以简单描述为：每个订单包括k(k≤m)种不同的作业，每台机器能且只能加工某一特定的作业，每个订单的作业必须连续加工直至完成，每个订单的完成时间是订单中所有作业的最大完成时间。所以，订单调度研究的是一组作业的整体完工情况。因为订单调度问题类型众多，模型复杂，并且大部分被证明为NP-hard难题，因此寻找多项式时间最优解是不可能的。国内外众多学者尝试发展启发式算法求解订单调度问题，可以求得较优解，而遗传算法作为一种人工智能优化算法，具有自适应性、并行性和全局优化的特点，所以本文尝试将遗传算法应用于一类订单调度模型，研究了专门机环境下以最小化总(加权)完工时间优化目标的订单调度模型，并将其与启发式算法进行性能比较。
　　 文章首先详细地描述了订单调度问题，建立了总完工时间和总加权完工时间情况下订单调度问题的数学模型；然后针对这两个数学模型的特点，完成了遗传算法的编码设计、适应度函数设计、遗传算子参数的优选、遗传因子的基因操作等，并运用Matlab强大的数值计算能力和库函数编写优化程序；接下来介绍了这两个模型的五个启发式规则；之后采用数值仿真实验的方法，将遗传算法与启发式规则的求解结果进行比较研究，在这个过程中考虑了不同订单数量和机器数量的情况；最后的研究结果表明，遗传算法与启发式规则相比更为有效，适用于订单调度模型，但仍存在一些不足，值得进一步研究。论文最后对遗传算法在订单调度中的应用前景进行了展望。

目录

文摘

英文文摘

声明

1绪论

1.1研究背景

1.2研究意义

1.3订单调度问题

1.3.1调度问题

1.3.2订单调度产生背景

1.3.3订单调度问题描述和分类

1.3.4订单调度模型应用

1.3.5订单调度研究综述

1.4论文研究方法和技术路线

1.5论文的主要工作和结构

2遗传算法简介

2.1遗传算法的产生与发展

2.2遗传算法的原理和特点

2.2.1遗传算法的原理

2.2.2遗传算法的主要特点

2.3遗传算法的流程

2.4遗传算法参数选择与操作设计

2.4.1编码

2.4.2适应度函数

2.4.3算法参数

2.4.4遗传算法操作设计

2.5本章小结

3 PDm||∑Cj问题的优化调度遗传算法研究

3.1 PDm||∑Cj模型描述

3.2遗传算法分析与设计

3.2.1遗传算法编码设计

3.2.2适应度函数

3.2.3算法参数的选取

3.2.4遗传算子的基因操作

3.2.5确定算法的终止条件

3.3订单调度问题中遗传算法的最优参数设计

3.3.1种群数目的优选

3.3.2交叉概率Pc的优选

3.3.3变异概率Pm的优选

3.4.PDm||∑Cj模型的启发式规则

3.4.1 STPT规则

3.4.2 SMPT规则

3.4.3 SMCT规则

3.4.4 SPTL规则

3.4.5 ECT规则

3.5遗传算法性能分析

3.5.1比较研究描述

3.5.2订单数n=10时调度算法比较分析

3.5.3订单数n=20时调度算法比较分析

3.5.4订单数n=50时调度算法比较分析

3.6本章小结

4 PDm||∑wjCj问题的优化调度遗传算法研究

4.1订单调度问题PDm||∑wjCj

4.2遗传算法分析与设计

4.3 PDm||∑wjCj模型的启发式规则

4.3.1 WSTP规则

4.3.2 WSMP规则

4.3.3 WSMC规则

4.3.4 WSPL规则

4.3.5 WECT规则

4.4遗传算法性能分析

4.4.1比较研究描述

4.4.2订单数n=10时调度算法比较分析

4.4.3订单数n=20时调度算法比较分析

4.4.4订单数n=50时调度算法比较分析

4.5本章小结

5总结与展望

5.1总结

5.2展望

致谢

参考文献

附 录