基于目标增量的无等待流水调度算法研究

文摘

英文文摘

声明

第1章绪论

1.1研究背景与意义

1.2组合优化的相关概念

1.3相关问题研究现状

1.3.1调度问题概述

1.3.2基本调度算法

1.3.3无等待流水调度算法

1.3.4研究现状总结

1.4研究内容

1.5论文结构安排

第2章无等待流水调度模型

2.1传统目标函数计算方法

2.2优化目标Flowtime的等价转化

2.2.1最大左移长度

2.2.2机器m上完工时间距离及目标函数

2.2.3通用机器完工时间距离及目标函数

2.3优化目标Makespan的等价转化

2.4 Makespan与Flowtime舣优化目标等价转化

2.5本章小节

第3章最小化Makespan无等待调度混合遗传算法

3.1最大完工时间增量性质与方法

3.1.1基本操作目标增量性质

3.1.2扩展目标增量性质

3.1.3基本目标增量方法

3.2算法混合策略

3.2.1混合算法结构与优化策略

3.2.2混合遗传算法

3.3最小化Makespan无等待调度问题混合遗传算法IIHG

3.3.1个体编码

3.3.2初始种群生成

3.3.3进化算子

3.3.4算子概率动态更新策略

3.3.5局部搜索

3.3.6收敛判断与再生机制

3.3.7 IIHG算法描述

3.4模拟实验结果

3.5本章小结

第4章基于目标增量的最小化Flowtime无等待调度启发式算法

4.1总完工时间增量性质与方法

4.1.1机器m上目标增量性质与方法

4.1.2目标增量性质与方法的推广

4.2基于总完工时间增量的复合启发式算法OICF1

4.2.1生成初始解

4.2.2迭代构造解

4.2.3 OICH1算法描述

4.2.4实例说明

4.2.5模拟实验结果

4.3基于总完工时间增量的复合启发式算法OICH2

4.3.1 LGS算法

4.3.2 OICH算法描述

4.3.3模拟实验结果

4.4本章小结

第5章最小化Flowtime无等待调度智能优化算法

5.1基本智能局部搜索策略

5.2基于最小化总完工时间增量的快速迭代贪婪算法FIG

5.2.1初始解生成

5.2.2分段式重构策略

5.2.3迭代全局搜索

5.2.4个体接收准则

5.2.5 FIG算法描述

5.2.6模拟实验结果

5.3基于动态选择机制的混合遗传算法DSHG

5.3.1初始种群生成

5.3.2动态选择策略

5.3.3进化策略

5.3.4改进变邻域局部搜索

5.3.5 DSHG算法描述

5.3.6模拟实验结果

5.4基于轮转扰动的微型进化算法MEA

5.4.1初始种群生成

5.4.2进化策略

5.4.3局部搜索

5.4.4 MEA算法描述

5.4.5模拟实验结果

5.5本章小结

第6章多目标优化的无等待流水调度问题

6.1基本概念

6.2基本操作目标增量性质

6.3基于目标增量的多目标混合遗传算法OlMoGA

6.3.1初始种群生成

6.3.2适应度分配

6.3.3个体选择机制

6.3.4进化算子

6.3.5精英保留机制

6.3.6局部／全局搜索

6.3.7 OIMOGA算法描述

6.4.模拟实验结果

6.5本章小结

第7章总结与展望

7.1主要研究工作

7.2进一步研究方向

参考文献

致谢

攻读博士学位期间发表的论文

攻读博士学位期间参加的科研项目