多学科设计计算服务选择及调度方法研究

论文摘要

复杂产品设计通常要需要机械、控制、电子等众多学科领域的知识,其过程是一个复杂系统。该系统包括多个子系统,从系统的角度出发,复杂产品设计的优劣不单单取决于单个子系统的优劣,还取决于这些子系统间的交互的协调性。因此需要进行多学科之间的协同设计优化。在多学科设计中的一个重要的方向就是要解决设计任务间的协同问题,计算服务的调度就成了需要优化的重要环节。计算服务调度问题在绝大多数应用中是NP-hard问题。它一般可以描述为：把一个任务集分配给一组服务器上,在一定约束条件下,如何安排计算任务和处理机之间的映射,以达到使总的执行时间最小的目标,即达到负载平衡。因此研究计算任务的调度问题具有重要的现实意义。本文在分析了任务调度的现状和各种研究方法的基础上,提出了一种解决多约束混合任务调度问题的基于启发式规则和遗传算法的混合算法。制定了一种先选择后调度的两步式解决方案。设计了一种无变异操作的简化遗传算法来实现任务的选择,并对遗传算法中的选择和重插入策略进行了改进。运用调度规则对选择的结果进行调度,把调度结果以甘特图的形式显示出来。采用MATLAB语言对算法进行了编程实现。通过大量的仿真运算和数据比较证明,该算法具有很好的综合性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 国内外现状
• 1.2.1 任务调度问题的描述
• 1.2.2 调度问题的分类和策略
• 1.2.3 任务调度问题的研究情况
• 1.3 遗传算法在任务调度中的应用
• 1.4 本课题的主要内容
• 第2章 遗传算法理论基础
• 2.1 引言
• 2.2 遗传算法的理论基础
• 2.2.1 模式定理
• 2.2.2 积木块假设
• 2.3 遗传算法的基本步骤和处理流程
• 2.4 遗传算法中基本概念
• 2.5 编码
• 2.6 适应度函数
• 2.6.1 适应度函数的作用
• 2.6.2 适应度函数的设计主要满足的条件
• 2.6.3 适应度函数的种类
• 2.7 遗传算法的基因操作
• 2.7.1 选择
• 2.7.2 交叉
• 2.7.3 变异
• 2.8 控制参数选择
• 2.9 本章小结
• 第3章 计算任务调度问题的分析和建模
• 3.1 任务调度问题模型分析
• 3.1.1 问题描述
• 3.1.2 模型的输入与输出
• 3.1.3 目标函数与约束条件
• 3.2 任务选择的设计
• 3.2.1 无约束的任务选择
• 3.2.2 考虑机器和任务之间约束的任务选择
• 3.2.3 考虑机器和任务、任务之间约束的任务选择
• 3.3 任务调度的设计
• 3.4 任务调度问题模型建立
• 3.5 计算任务调度问题的一些特例
• 3.6 本章小结
• 第4章 计算任务调度系统的实现
• 4.1 系统的构架及各模块功能简介
• 4.2 系统各模块实现
• 4.2.1 软件注册
• 4.2.2 参数保存
• 4.2.3 优先级生成
• 4.2.4 任务执行
• 4.2.5 图形显示
• 4.3 系统功能验证
• 4.4 系统实现的关键技术
• 4.4.1 模块化设计
• 4.4.2 MATLAB可视化界面技术
• 4.5 本章小结
• 第5章 实验仿真及结果分析
• 5.1 无约束问题
• 5.1.1 简单问题的手动运算和算法验证
• 5.1.2 复杂问题的算法运算和分析
• 5.2 有机器和任务间约束（STM）的问题
• 5.2.1 初始算法的验证
• 5.2.2 改进后算法的验证
• 5.3 有机器和任务、任务和任务约束（STM、MTM）的问题
• 5.3.1 简单问题的手动运算和算法验证
• 5.3.2 复杂问题的算法运算和改进
• 5.4 与其他算法性能的比较
• 5.5 本章小结
• 第6章 结论与建议
• 6.1 结论
• 6.2 建议
• 参考文献
• 致谢