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

发布时间：2024-02-02 17:57

　　随着产业化的快速发展,企业仅依赖内部科技设备资源已无法满足生产需求,网络式资源共享迫在眉睫。有效的调度策略能提高设备资源利用率,降低用户对设备的使用成本,缩短等待时间,进而提高整个系统运行效率。由于考虑自身需求点的不同,企业注重生产效益,用户更关注作业加工完成需要的时间和使用成本。且对于需要加工的作业,其各工序在不同设备上分阶段进行。综合以上方面,作业调度策略已成为设备资源管理、分配,及平衡多个目标的关键因素。针对设备资源共享环境下多用户预约设备问题,构建以用户提交作业在设备上完成花费总时间最短和使用成本最低为优化目标的数学模型。为对所建模型进行有效求解,本文以遗传算法作为算法框架,设计两种改进的遗传算法进行优化求解。文中分两种情况进行研究:(1)对于每个用户提交的作业只需在一台设备上加工完成的情况,本文设计一种基于排挤机制遗传算法的调度策略,运用归一化法及偏爱权重系数对优化目标进行处理,以此确定算法的适应度函数。在适应度函数中增加罚函数项处理约束冲突,以便在减小其被选择到下一代概率的同时,通过基因重组发现隐藏在不可行解周围的更好可行解。在改进遗传算法中加入有利于个体较优模式增长的启发...

【文章页数】：79 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第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.3 本章总结
第6章 总结和展望
    6.1 论文总结
    6.2 工作展望
致谢
参考文献
附录
    附录A 用户作业信息表
    附录B 攻读硕士学位期间科研成果



本文编号：3892925