时序约束下科学工作流的动态调度研究

随着分布计算技术的迅速发展,利用广域分布的计算资源构建并执行科学工作流,已成为当前学术界和工业界关注的热点问题.为满足用户和计算控制机制的需求,往往需定义科学工作流的时序约束.但是,由于任务处理时间具有不确定性,在运行过程中容易出现时序违反.为保证科学工作流的正确执行,迫切需要能根据实时运行状态自动实现动态调度的方法.针对已有研究方法的不足,本文提出了一种基于遗传蚁群混合算法的科学工作流动态调度优化方法.首先,建立了时序约束下的科学工作流动态调度模型,该模型综合考虑了科学工作流的时间与成本优化目标,并融合了基于概率的时序约束满足性需求;然后,采用改进的遗传蚁群混合算法实现模型求解.该算法通过设计提高种群搜索导向性及保持种群多样性的策略,从求解精度及求解速度两方面提高了求解效率.最后,通过与现有方法的多组实验对比,说明了本文算法的优越性.     

基于高级对象Petri网的工作流过程建模研究

通过对当前工作流过程建模方法的总结,提出这些方法的不足之处,展望了过程建模的发展动向.在基本的有色 Petri 网系统定义的基础上,引入面向对象技术和时间映射机制,提出了一种基于高级对象Petri 网的建模方法,以提高模型的可重用性,加强对动态流程的描述能力,降低建模过程的复杂度,解决临界资源的共享问题.通过一个具体实例阐述了如何建立高级对象 Petri 网模型,并通过活性分析算法,验证模型对流程描述的正确性和有效性.     

基于路径QoS加权分解的工作流调度算法

采用有向无环图DAG(Directed Acyclic Graph)描述的工作流在QoS约束下的调度问题是一类典型的NP难问题。分析了DAG工作流调度问题的调度目标,提出了一种基于路径QoS加权分解的工作流调度算法,通过将工作流的全局QoS约束分解为单个任务的局部QoS约束,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。在对整个DAG工作流的QoS约束进行分解时,算法对工作流的每条路径的QoS约束进行分解,并以任务可选能力服务间的单位QoS增益之和作为权值,将单条路径的QoS约束分解到组成路径的每个任务。仿真结果表明,与其他基于QoS分解的DTL、DBL等算法相比,该算法具有更高的调度效率,能够找到更好的调度方案。     

基于改进微粒群的分布式工作流调度优化

为了提高分布式工作流的执行效率,通过研究微粒群算法PSOA的机理,结合分布式服务工作流调度的特点,提出了基于整数二进制编码的微粒群算法IBPSOA.IBPSOA采用服务类、服务实例作为整数-二进制编码方式,重新定义了微粒群算法的加/减法和乘法,增加了特殊的绝对值运算,速度与位置的更新加快了向最佳目标收敛的速度,实现了工作流优化调度.通过仿真实验和原型系统的运行,验证了IBPSOA算法是解决分布式计算环境下工作流调度优化问题的一个有效途径.     

基于Petri网和UML活动图工作流建模比较

在工作流建模中Petri网和UML活动图各自发挥了十分重要的作用，然而对于其建模的适应性却没有充分的研究。通过对工作流管理系统的分析，认为工作流管理系统具有响应性、协作性和开放性特点。在给定适合工作流建模的UML活动图语义基础上，讨论了工作流建模的几个关键要素在Petri网和UML活动图下的建模比较，通过分析认为，Petri网更适合于封闭，主动系统的建模，UML活动目能够较为充分的适应开放、响应型系统的建模。Petri网较适合对稀有资源的建模．因此UML活动图更适合工作流这种开放，响应型系统建模。     

基于最短时间碎片的在线生产调度算法研究

针对订单型企业的在线生产调度问题,文章通过统计每个设备上允许插入工序的时间区间,提出了基于最短时间碎片的启发式在线生产调度算法.该算法的主要思路是将工序的先后约束关系和在同一设备上的先后执行关系统一建模为无圈有向图,从而依据最短时间碎片将新订单的调度过程转化为在有向图中添加顶点和有向边的过程.仿真实验结果表明该算法可以在保证订单交付期的前提下实现排产任务,并尽可能少地变更已排产工序在设备上的相对位置;在订单频繁到达时,调度的设备利用率较高,达到了约94%;此外,算法运行较快,适用于较大规模在线生产调度问题的求解.     

基于动态任务合成的多星观测调度方法

合成观测可以提高卫星的观测效率,研究了遥感卫星的动态合成观测调度问题.分析了卫星对多个任务合成观测的条件,在此基础上,建立了任务需求度、资源竞争度以及任务合成中的最小侧摆、最小数据冗余启发式,提出了基于动态任务合成的多星观测调度启发式算法.仿真实例表明,此方法可以有效提高卫星的观测效率.     

一类多卫星动态调度问题的建模与求解方法

卫星调度是空间资源管理的重要内容之一，其本身也是一类复杂的资源分配问题。基于动态约束满足理论，针对卫星初始调度方案执行过程中卫星资源出现故障的情况，建立了多卫星动态调度模型，提出了求解模型的启发式搜索方法。最后，以地球资源观测卫星调度问题为例，对模型和算法进行了验证。     

面向能耗的云工作流调度优化

云工作流调度直接决定了整个云工作流系统的性能,已成为一个重要研究内容.针对当前缺乏有效的面向能耗的云工作流调度优化方法,研究建立了面向能耗的云工作流过程模型、资源模型,提出了基于负载的能耗计算方法和面向能耗的云工作流调度优化算法.提出的方法考虑了能耗因素,在进行任务优先级计算及任务选择时不仅考虑了文件在不同虚拟机间传输的速度差异、同时考虑了虚拟机与本地共享数据库间的文件传输等因素,并从云工作流任务分配、主机负载和主机功耗关系的角度,进行能耗的计算与调度优化,更符合实际情况、使用范围更广.数值案例和仿真实验表明了提出的方法是可行的和有效的.     

集装箱码头装卸系统集成调度的建模与优化

为提高集装箱码头作业效率,在码头集装箱卡车作业能力充足的条件下,对集装箱码头作业装卸系统集成调度问题进行了研究.针对集装箱码头装卸作业的特点,提出了装卸作业的预定义顺序约束、作业次序依赖的设备调整时间及岸桥碰撞干涉约束等,并在此基础上建立了整数规划模型.针对这一模型设计了两阶段启发式算法对问题进行求解.通过在数值实验中将结果与低界相比较,证明该算法效果良好.特别对于规模较大的问题,算法也可以进行有效的求解.     

测量调度的建模和分析

通过研究一个大型网络测量系统中测量任务的调度问题，建立了形式化的测量调度模型，规范地定义了测量任务分布，资料耗费和资源分配等概念，基于该模型，分析了大规模测量调度的分解，测量调度的拓扑约束和资源约束，以及测量任务排队等问题，为网络测量系统的用户或管理员较好地规划组件配置，资源分配和测量任务分布奠定了基础。     

有新任务插入的多星动态调度模型与算法研究

对地观测卫星动态调度问题是一类复杂的调度问题.在对动态调度的要求进行分析的基础上,针对有新任务插入的多星动态调度问题的特点,建立了多星动态调度模型,提出了一种基于自由度规则的动态启发式求解算法.分别设计了基于最大自由度的退出启发式规则和基于自由度比例的退出启发式规则,采用深度有限搜索策略进行迭代搜索.仿真实例分析表明,基于自由度规则的动态启发式求解算法能够较好地解决有新任务插入的多星动态调度问题.     

混合Flow Shop的调度仿真系统及其算法分析

研究了混合Flow Shop的调度问题，调度目标为最小化工件的最大完成时间。文中给出了调度仿真系统的设计，系统由数据库、算法和控制中心用户接口三个模块组成；在算法模块中，排序算法包括了由Flow Shop扩展到混合Flow Shop的多数算法，设备分配采用最先可用机器优先规则。另外，基于CDS虚拟机和Palmer斜度指标的启发式算法，提出了一种改进的CDS算法用于工件排序。在正在开发的混合Flow Shop调度仿真系统中实现了上述所有算法，仿真分析表明改进的CDS算法优于其他启发式算法。     

基于Petri网的产品设计过程工作流结构化建模与仿真

产品设计过程的工作流管理是产品设计的核心管理过程,直接影响着项目的开发周期和整体效益.为实现对产品设计过程工作流动态性和不确定性的管理与控制,在研究工作流结构化建模相关问题的基础上,提出基于Petri网的产品设计过程工作流结构化建模方法,定义了基于Petri网结构化建模的七种基本结构模块,确定了顺序、重叠、迭代、耦合、分支和连接模式为工作流结构化建模核心模式.以某办公楼的设备详细设计过程为例,进行工作流结构化建模和仿真分析,验证基于Petri网的产品设计过程工作流结构化建模方法的正确性和有效性.     

基于颜色Petri网的多agent动态调度建模与分析

多agent系统是一个典型的分布式系统,其任务调度策略的性能对于整个系统的性能有重要的影响。调度策略研究领域中一个重要问题是如何动态可视化地呈现调度过程。颜色Petri网结合了Petri网和高级程序语言的优点,拥有严格的数学理论基础,能够对分布式系统进行图形化的模拟。提出了一种基于层次颜色Petri网的多agent调度过程建模方法,该方法对多agent任务处理的全过程进行了建模,模型中通过不同角色的agent对任务进行动态分解和调度,利用Petri网仿真工具,能够在调度过程中考察所提出的调度策略与已有调度策略相比所具有的优点,而且通过对调度简化模型的状态空间进行分析,证明了调度策略的正确性和合理性。目前这种基于Petri网的形式化的可视仿真方法和模型评价方法是其它验证方法难以实现的。     

基于着色Petri网的复杂产品开发多项目调度建模研究

建立多项目调度模型已经成为复杂产品开发多项目计划和控制的基础。分析了复杂产品开发多项目调度的特点，指出目前已经提出的多项目调度建模方法不能全面的体现和描述上述特点，提出了用着色Petri网建立多项目调度模型的具体思路和方法，即在着色Petri网颜色定义的基础上，利用着色网的颜色、层次等特点描述多项目调度的相似性、开放性争层次性，利用着色网的守卫函数、孤函数和双向孤等方法描述多项目调度的冲突性、技术关联性争遮代性，文章简要阐述了模型实例和分析方法，最后给出结论和下一步工作。     

基于Petri网和GASA的JSP动态分类调度研究

针对车间作业的加工受到机床、操作工人等双资源制约条件下出现多种扰动的JSP调度问题,提出了基于受控Petri网和GASA对不同扰动进行分类处理的新方法。首先通过构建带有控制器的Petri网模型使系统的运行满足期望的目标,然后基于该模型把遗传算法和模拟退火算法相结合,以最小化最大完工时间为目标,基于机床故障修复时间、工人离岗时间及取消订单包含任务的多少进行分类调度,然后根据扰动恢复后剩余任务的多少决定是否进行再次调度,避免大范围调整造成的生产不稳定状态,最大限度的维持车间的生产能力。最后通过实例验证了算法的有效性和可行性。