基于启发式最短路径的PAC任务调度算法

发布时间：2017-08-07 15:39

  本文关键词：基于启发式最短路径的PAC任务调度算法

  更多相关文章： PAC实时系统 混合任务调度 最短路径算法 启发式搜索

【摘要】：近年来,可编程自动化控制器(PAC)作为覆盖工业常规控制的通用型自动化平台,其概念一经提出便得到广泛关注与研究。PAC系统是一种典型的混合任务实时系统,包括人机交互接口、PLC控制和运动控制等多种功能模块,对系统内部的任务调度机制具有特定需求。研究了实时系统的任务调度理论,对于任务调度理论中调度算法这一重要的研究内容,分别从算法分类、调度策略和性能评估标准等方面展开讨论；阐述了已经提出的各类调度算法,介绍了该领域的研究现状；指出了实时系统任务调度理论研究在实际应用中所面临的问题。针对当前实时系统中不同类型任务共存、部分任务之间具有时序相关性等特点,建立了混合关联任务系统的数学描述模型；对任务执行序列的选择问题进行抽象,将其转化为在状态空间树中寻找状态节点之间最短路径的问题；提出了一种基于启发式搜索的最短路径(SPA)任务调度算法,证明了该算法中启发式代价评估函数的构造条件,讨论了算法的适用性,解决了混合关联任务集的实时调度问题。根据PAC实时系统的应用需求和具体特点,以功能为单位对PAC系统进行了任务划分,建立了任务时间约束集,构造了启发式代价评估函数,描述了SPA算法的设计流程图、伪代码和数据结构；在PAC系统的实时内核中实现了SPA任务调度算法,以四轴并联机器人系统作为实例分析及算法性能验证平台,实验测试结果表明该算法的实际运行效果与理论分析预期一致,具有较高的工业应用价值。
【关键词】：PAC实时系统 混合任务调度 最短路径算法 启发式搜索
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-12
• 1.1 课题研究背景8-9
• 1.1.1 PAC系统及其实时调度需求8-9
• 1.1.2 实时系统任务调度研究意义9
• 1.2 国内外研究现状9-10
• 1.3 论文内容及结构10-12
• 2 实时系统任务调度理论12-19
• 2.1 实时系统概念12-13
• 2.1.1 实时系统特征12
• 2.1.2 实时系统分类12-13
• 2.2 任务调度理论13-18
• 2.2.1 任务调度概述13-15
• 2.2.2 经典任务调度算法15-16
• 2.2.3 混合任务调度算法16-18
• 2.3 本章小结18-19
• 3 启发式搜索最短路径调度算法19-31
• 3.1 混合任务系统建模19-22
• 3.1.1 任务模型描述19-20
• 3.1.2 任务切换条件20-21
• 3.1.3 任务调度目标21-22
• 3.2 任务调度问题转化22
• 3.3 代价评估函数构造22-24
• 3.4 SPA任务调度算法24-30
• 3.4.1 SPA算法描述24-26
• 3.4.2 SPA算法示例26-29
• 3.4.3 SPA算法适用性29-30
• 3.5 本章小结30-31
• 4 基于SPA算法的PAC任务调度31-37
• 4.1 PAC系统任务划分31-32
• 4.2 任务时间约束集32-35
• 4.3 代价评估函数35
• 4.4 算法数据结构35-36
• 4.5 本章小结36-37
• 5 实例分析与性能测试37-45
• 5.1 四轴并联机器人系统37-38
• 5.2 调度实例分析38-42
• 5.3 关键性能测试42-44
• 5.4 本章小结44-45
• 结论45-46
• 参考文献46-49
• 攻读硕士学位期间发表学术论文情况49-50
• 致谢50-51

【参考文献】

中国期刊全文数据库 前6条

1 段渊;;实时系统中单处理器调度算法的优化设计研究[J];运筹学学报;2013年02期

2 彭瑜;;试论传统PLC、现代PLC和PAC的渊源和区别[J];电气时代;2006年09期

3 姚鑫骅;潘雪增;傅建中;陈子辰;;数控系统的混合任务模型及其最优调度算法研究[J];浙江大学学报(工学版);2006年08期

4 王永吉,陈秋萍;单调速率及其扩展算法的可调度性判定[J];软件学报;2004年06期

5 王强,王宏安,金宏,戴国忠;实时系统中的非定期任务调度算法综述[J];计算机研究与发展;2004年03期

6 何军,孙玉方;提高软非周期任务响应性能的调度算法[J];软件学报;1998年10期

中国博士学位论文全文数据库 前4条

1 杨磊;基于工业以太网的数控系统实时性问题研究[D];中国科学技术大学;2014年

2 巴巍;实时系统动态优先级任务调度算法的研究[D];大连理工大学;2010年

3 姚鑫骅;数控实时系统调度理论及应用研究[D];浙江大学;2006年

4 王立刚;开放式混合实时系统中的调度方法研究[D];中国科学技术大学;2006年

中国硕士学位论文全文数据库 前1条

1 赵公怡;单处理器环境下实时调度算法研究[D];湖南大学;2011年

，

本文编号：635402