基于复杂网络理论的复杂调度问题求解方法研究

论文摘要

调度作为资源分配的一种手段在各个领域都得到了广泛的重视。现实中的调度对象通常具有动态性,随机性,以及不确定性等特点,本文中把该类调度对象称为复杂调度对象,而相应的调度问题则称为复杂调度问题。调度规则由于其简单灵活的特点,被广泛采用于求解复杂调度问题。当前的调度规则大多源于生产实际,缺少一种系统化的方法。复杂网络作为研究复杂系统结构的一种新兴的理论为调度提供了新的契机。本文通过给复杂调度对象建立复杂网络模型,从而将复杂调度问题转换成复杂网络上的节点遍历问题,并且在复杂网络的框架下提出了系统化设计调度规则的方法。最后将这些调度规则用于求解多资源独立任务复杂调度问题取得了不错的效果。本文的研究内容以及创新点主要包括以下几个方面:根据现实的复杂系统特点从三种不同的视角提出了三个多特征复杂网络模型,包括区域固定局部世界模型,能力固定局部世界模型,以及基于博弈的动态演变模型。首次给出了复杂调度对象的网络化描述,将复杂调度问题转换成复杂调度网络上的节点遍历问题,这为解决实际复杂调度问题提供了新的视角和方法。通过某种映射关系可以把调度目标转换成复杂调度网络的某个全局特征,从而将复杂调度网络的局部特征作为设计调度规则的启发式信息。比如网络平均度值以及平均功效和复杂调度问题之间就存在某种关联,而节点度值,节点聚类系数,以及本文提出的节点冗余度均可作为设计调度规则的启发式信息。给出了复杂调度网络建模的具体步骤,并且通过这些步骤在基于一些假设的基础上给四类复杂调度对象,多资源独立任务每个事件所需资源数服从均匀分布调度对象,多资源独立任务每个事件所需资源数服从幂律分布调度对象,多资源非独立任务每个事件所需资源数服从均匀分布调度对象,以及多资源非独立任务每个事件所需资源数服从幂律分布调度对象,构建了各自的复杂调度网络模型,并对这些复杂调度网络进行了结构特征分析。提取了三种基于复杂调度调度网络结构的调度规则,主要包括基于节点度值,聚类系数,以及冗余度的调度规则,并将它们用于求解多资源独立任务复杂调度问题,相比几种经典的调度规则而言,取得了不错的效果。

论文目录

• 致谢
• 摘要
• Abstract
• 插图目录
• 附表目录
• 第1章 绪论
• 1.1 引言
• 1.2 调度系统
• 1.2.1 调度的定义与分类
• 1.2.2 调度对象建模
• 1.2.3 调度算法
• 1.3 复杂网络理论
• 1.3.1 研究历程
• 1.4 本文的研究动机
• 1.5 本文研究内容及其结构组织
• 1.6 本文创新点
• 第2章 复杂调度对象的网络化描述
• 2.1 引言
• 2.2 复杂调度对象的网络化描述方法
• 2.2.1 复杂调度对象的数学描述
• 2.2.2 复杂调度对象的网络化描述方法
• 2.2.3 复杂调度问题的网络化描述
• 2.3 现实复杂调度对象的网络化描述
• 2.3.1 机场登机门分配调度网络
• 2.3.2 网格计算调度网络
• 2.3.3 钢锭初轧过程调度网络
• 2.3.4 运动会赛程安排调度网络
• 2.4 本章小结
• 第3章 复杂调度网络特征提取
• 3.1 引言
• 3.2 局部特征和全局特征
• 3.3 与复杂调度问题相关的网络局部和全局特征
• 3.3.1 节点度值
• 3.3.2 聚类系数
• 3.3.3 网络功效
• 3.3.4 冗余度
• 3.4 网络全局特征和节点遍历问题的具体关联
• 3.4.1 平均度值和网络上节点遍历问题的关联
• 3.4.2 平均功效与网络上节点遍历问题的关联
• 3.4.3 一个简单的类比
• 3.5 本章小结
• 第4章 复杂调度网络建模方法
• 4.1 引言
• 4.2 复杂调度网络建模目的
• 4.3 复杂调度网络建模步骤
• 4.4 多资源复杂调度网络建模
• 4.4.1 多资源独立任务复杂调度网络建模
• 4.4.2 多资源非独立任务复杂调度网络建模
• 4.5 本章小结
• 第5章 基于网络结构特征的调度规则
• 5.1 引言
• 5.2 调度规则
• 5.3 基于网络结构特征的调度规则设计步骤
• 5.4 基于网络结构特征的调度规则设计
• 5.4.1 完全随机调度规则
• 5.4.2 基于度值的调度规则
• 5.4.3 基于聚类系数的调度规则
• 5.4.4 基于冗余度的调度规则
• 5.5 本章小结
• 第6章 计算机仿真实验
• 6.1 引言
• 6.2 调度对象描述
• 6.3 调度网络建模
• 6.4 计算机仿真实验设计
• 6.5 仿真结果分析
• 6.6 本章小结
• 第7章 结论与展望
• 7.1 结论
• 7.2 展望
• 7.2.1 提取具有应用价值的网络特征
• 7.2.2 构建更符合实际的复杂调度网络模型
• 7.2.3 利用网络结构设计调度规则
• 7.2.4 分块调度
• 7.2.5 复杂调度网络鲁棒性测试
• 参考文献
• 作者简历