基于改进遗传算法作业调度问题的优化及应用

摘要

随着产业化的快速发展，企业仅依赖内部科技设备资源已无法满足生产需求，网络式资源共享迫在眉睫。有效的调度策略能提高设备资源利用率，降低用户对设备的使用成本，缩短等待时间，进而提高整个系统运行效率。由于考虑自身需求点的不同，企业注重生产效益，用户更关注作业加工完成需要的时间和使用成本。且对于需要加工的作业，其各工序在不同设备上分阶段进行。综合以上方面，作业调度策略已成为设备资源管理、分配，及平衡多个目标的关键因素。 针对设备资源共享环境下多用户预约设备问题，构建以用户提交作业在设备上完成花费总时间最短和使用成本最低为优化目标的数学模型。为对所建模型进行有效求解，本文以遗传算法作为算法框架，设计两种改进的遗传算法进行优化求解。文中分两种情况进行研究： (l)对于每个用户提交的作业只需在一台设备上加工完成的情况，本文设计一种基于排挤机制遗传算法的调度策略，运用归一化法及偏爱权重系数对优化目标进行处理，以此确定算法的适应度函数。在适应度函数中增加罚函数项处理约束冲突，以便在减小其被选择到下一代概率的同时，通过基因重组发现隐藏在不可行解周围的更好可行解。在改进遗传算法中加入有利于个体较优模式增长的启发式交叉操作，以及维持种群多样性的自适应变异操作和排挤机制，增强算法的搜索能力和寻优能力。 (2)对于每个用户提交的作业包含多个工序，需在多台设备上加工完成的情况，在求解过程中，需要考虑每个作业开始的加工时间和工序间的加工顺序，及不同用户的期望值等约束。本文设计了基于贪婪思想的初始解生成方式和主动解码方法，提出一种改进的非支配排序遗传算法。该算法运用快速非支配排序算法，精英选择策略加快算法的收敛速度，引入强度Pareto算法中层次聚类操作算子，进行同级个体的选择，保持Pareto前沿解分布的多样性，算法经过迭代优化得到一组非支配解集，再通过层次分析法得到问题决策的最优调度策略。 大型仪器服务平台系统主要是实现科技设备资源的共享，由于互联网的发展，系统在线用户数量逐渐增多。当同一时刻有较多用户预约设备时，会出现设备资源冲突，且不同用户的考虑和要求不同。因此，服务器端的作业调度方案，一方面影响网络设备资源的使用效能，另一方面也影响用户的满意度。针对该问题，采用本文设计的基于改进非支配排序遗传算法的调度策略，帮助用户生成满足多约束多目标的调度方案。

目录

第一个书签之前

插图目录

表格目录

第1章 绪论

1.1研究背景及意义

1.2国内外研究现状

1.3论文主要内容的组织

1.4本章小结

第2章 相关算法

2.1 遗传算法

2.1.1 遗传算法的发展前景

2.1.2 遗传算法的基本框架

2.1.4 遗传算法的基本操作

2.2 非支配排序遗传算法

2.2.1 多目标优化问题的数学描述

2.2.2 非支配排序遗传算法的发展

2.2.3 基本思想

2.2.4 基本流程

2.2.5 非支配排序遗传算法特性

2.3 SPEA算法

2.3.1 基本思想

2.3.2 算法流程

2.3.3 算法分析

2.4 聚类算法

2.4.1 聚类算法概述

2.4.2 层次聚类

2.5 本章总结

第3章 基于排挤机制遗传算法的作业调度策略

3.1 作业调度问题描述

3.1.1 作业调度问题描述

3.1.2 作业调度问题的数学优化模型

3.2 基于排挤机制遗传算法的作业调度策略

3.2.1 基于排挤机制遗传算法设计

3.2.2 适应度函数

3.2.3 初始种群的生成

3.2.4 选择及个体更新

3.2.5 启发式交叉

3.2.6 变异操作

3.2.7 局部搜索

3.3 实验数据与分析

3.4 本章总结

第4章 基于改进NSGA_II的作业调度策略

4.1 可分解的作业调度问题的描述

4.2 基于改进NSGA_II的作业调度策略

4.2.1 NSGA_II算法

4.2.2 快速非支配排序算法

4.2.3 编码和解码

4.2.4 交叉操作

4.2.5 变异操作

4.2.6 精英保留策略

4.2.7 选择操作

4.2.8 改进的NSGA_II

4.3 Pareto综合选优机制

4.4 实验测试与分析

4.5 本章总结

第5章 改进模型在大型仪器服务平台系统中的应用

5.1 大型仪器服务平台系统问题概述

5.2 模型应用

5.5 本章总结

第6章 总结和展望

6.1 论文总结

6.2 工作展望

致谢

参考文献

附录

附录A用户作业信息表

附录B 攻读硕士学位期间科研成果