基于免疫遗传算法的网格工作流服务选择

随着OGSA(open grid service architecture)的提出,在网格环境中,如何进行服务的选择是一个热点问题.对于DAG(directed acyclic gragh)描述的网格工作流模型,考虑时间和费用两个Qos(quality of service)参数,即满足用户截止期的前提下,为工作流选择尽可能便宜的服务.对于一般遗传算法的求解问题时出现的早熟和退化现象,采用了免疫算子和遗传算子相结合的免疫遗传算法来进行搜索全局解,并且加入了自适应遗传交叉算子和疫苗提取来提高搜索能力.仿真试验证明文章的算法具有较好的解空间搜索性能.     

基于关键路径前瞻的工作流调度算法

为了进一步提高工作流调度的效率,对异构环境下的工作流调度算法进行研究,提出了一种基于关键路径前瞻算法(critical path lookahead algorithm,CPLA)的工作流调度算法.该算法在任务确定优先级阶段考虑了入口任务到当前任务的最长路径,以及当前任务到出口任务的最长路径;在资源选择阶段考虑了关键路径任务和非关键路径任务对调度结果的影响.使用随机生成的和真实世界的2种不同类型的有向无环图(directed acyclic graph,DAG)工作流来评估CPLA的性能,实验结果表明:CPLA能够有效地缩短调度长度,算法的效率、加速比、调度长度比等性能有所提高,并且算法的时间复杂度低于目前调度效果最好的Lookahead算法.     

运用改进的SPEA2算法优化网格工作流调度方法

提出了一种QoS约束的多目标优化的网格工作流调度算法ISPEA2,该算法基于表达结构丰富的AGWL网格工作流模型,在SPEA2算法中引入约束检测对网格工作流调度问题进行优化,克服了当前网格工作流调度算法中大多只考虑DAG结构的网格工作流、涉及QoS参数较少及将多QoS参数聚合成一个单目标函数进行优化调度的缺陷,可供决策者根据用户的实际需求从产生的Pareto优化解集中选择最终的满意解。通过与采用原SPEA2设计的网格工作流调度算法OSPEA2的比较,表明ISPEA2算法所获得的Pareto优化解集都是满足QoS约束的非支配解,且获得了更优的平均结果。     

负载均衡优先的改进优先级表调度算法

针对当前云计算环境下DAG任务调度时存在的负载失衡、任务调度效率不高的问题,提出了一种负载均衡优先的改进优先级表调度算法(LS-IPLB).算法将云计算集群中虚拟机的状态参数变化抽象成空间中的参数向量变化,给出实时衡量云计算集群的负载均衡性方法,并作为虚拟机选择权值的重要参数.同时以任务执行代价、任务的出度和任务间的通信代价作为参数计算任务优先级,并在任务调度时采用任务复制策略进一步优化调度过程.结果表明,LS-IPLB算法能有效缩短DAG任务图的完成时间,并实现了良好的负载均衡性.     

DAG任务模型的粒子群优化调度算法

在并行多处理器系统中,通常用有向无环图(DAG)表示任务之间的依赖关系.为了提高该任务模型调度算法的性能,基于粒子群优化算法,提出一种新的调度算法.算法将任务高度和粒子位置作为任务优先级,使用表调度策略生成有效的调度方案,在满足任务间依赖关系的条件下,使所有任务的完成时间最小.仿真实验结果表明,与遗传算法相比,所提出的算法提高了解的质量和收敛速度,特别适合于规模较大的多处理器任务调度.     

工期约束下加工型产品准确率串归约算法研究

完工时间和准确率是生产调度的两个重要属性,然而单属性优化算法只能完成单个属性的优化,无法动态平衡这些属性。针对此问题,提出了基于有向无环图的串归约优化算法。算法通过约束每个任务的活动区间并采用逆向迭代进行归约,达到每层选择最优服务的目的,从而实现了这两个属性的优化。实验表明,该算法可准确地得到一条完工时间和准确率相互平衡的优化路径,但其优化效率受限于完工截止期和任务数。最后,研究结论对生产调度多属性的优化提供了一定的参考。     

一个新型ASIP编译器的设计和实现

为了满足专用指令处理器(ASIP)存储器约束和代码执行的实时性要求，提出了一种同时考虑代码选择和寄存器分配的代码综合生成算法，同步处理代码生成的子问题.该算法基于最优化原理，把无环有向图（DAG）的所有节点构造成一个调度矩阵，把寻找代码优化的问题转化成在调度DAG中寻找一条优化路径，大大降低了算法的时间复杂度.并应用算法构造了一个编译器后端，测试表明，该算法能够正确地生成目标代码，和传统的分步优化算法相比，减小了目标代码的空间尺寸，降低了寄存器溢出的几率.     

基于活动的工作流关键路径算法

计算关键路径是研究工作流时间问题的重要步骤,现有算法大多是基于工作流控制结构的规约与化简的,对工作流模型要求较高,不能计算控制结构的"部分覆盖",限制了其应用.首先给出一个描述活动延迟的工作流模型,然后将工作流网看作一个M/M/1队列网,讨论工作流活动在各种结构中的到达率与时间延迟,提出一种基于活动的关键路径算法.算法降低了对工作流模型结构的要求,解决了控制结构"部分覆盖"的计算问题,提高了算法的实用性.     

基于多核处理器平台的公平调度算法

为了减少多核处理器系统全局调度算法中共享L2cache抖动,在Pfair调度算法基础上提出一种新的Cache感知的软实时公平调度算法.通过对WSS(work set size)、子任务截止时间和任务负载建立多因素优先级模型,并将此优先级模型应用到改进后的Pfair算法中,该算法的调度决策在系统负载较重的系统中对WSS具有自适应性.模拟实验结果显示:在对称4核和8核处理器系统中,该算法任务丢失率低,且在系统负载重时能够减少共享L2cache抖动,其整体调度性能优于传统的G-EDF(global-earliest deadline first)调度算法和Pfair调度算法.     

基于新颖性排名和多服务质量的云工作流调度算法

针对现有研究未能综合考虑以用户成本和系统利用率为目标进行优化调度的问题,提出基于新颖性排名和多服务质量(QoS)目标的云工作流调度算法.将资源节点执行任务的频度、任务的等待时间和执行时间作为因子加入推荐模型;使用模拟退火算法训练得到推荐模型,计算出优先级因子;调度器根据优先级因子表进行调度并对其进行更新.在CloudSim平台上进行模拟调度仿真实验,结果证明:所提出算法的任务执行时间优于Q值学习(Qlearning)算法,且用户成本和系统使用率的综合指标更好.     

基于资源分组的多约束云工作流调度算法

已有的云工作流调度算法采用全局搜索方式进行资源选取,存在计算成本高、对大规模云系统适应性差的问题。该文提出了基于资源分组的多约束云工作流调度算法,采用有向无环图的方法,对云工作流中的多任务之间的执行顺序和数据交换等属性进行量化建模;使用模糊聚类方法实现基于资源多维特征的分组处理,降低工作流任务到资源匹配过程中的搜索空间;并引入执行时间和成本预算约束,将工作流的任务调度问题转化为有约束条件的极小极大问题进行快速求解。仿真测试表明,该算法显著降低了任务执行完成时间和成本。     

基于时间Petri网的铁通调度指挥系统建模与分析

在分析了铁通调度指挥系统(TDS)建模存在的问题后,本文提出了基于时间Petri网的铁通调度指挥系统工作流模型.在此模型中,用时间Petri网表示工作流模型,并分析了基本结构的时序关系.利用在线性时间复杂度内解决时间推理问题的线性推理规则,本文用时间Petri网建立了TDS停机停线的工作流模型.最后,对TDS停机停线的时间性能进行了分析.     

一种自治愈的QoS感知的Web服务组合方法

基于工作流的服务质量（QoS）感知的Web服务组合是Web服务领域的一个研究热点,其目标是选择一个满足QoS约束且QoS效用最大的组合服务。该文给出了常见工作流的一种形式化定义方法及虚拟任务的合成规则,从而提出了一种基于top-k优选策略的Web服务组合方法,其核心思想是递归运用虚拟任务的合成规则将原工作流转换成一个虚拟任务,并在每次合成虚拟任务时,仅为其保留k个优选的服务或组合服务实例。该文还提出了一种新的寻找替换服务的方法以支持自治愈性。仿真实验分析了k值对效用的影响、算法的效用与时间开销以及可替代性能。     

基于约束有向图面向XML的工作流建模

针对传统建模方法建模复杂且构建的模型通用性差等缺点,提出基于约束有向图的建模方法,通过对有向图的节点和连接弧的约束解决有向图在过程建模时描述能力不足的问题,保留了其直观性;给出了将构建的工作流模型转换为基于XML描述形式的具体方法,增强了模型的通用性。     

改进CS算法结合决策树的云工作流调度

对云计算环境下工作流任务调度的现有方案进行分析,针对存在运行时间长、资源利用率低等不足,提出一种结合改进型布谷鸟搜索算法和决策树的工作流任务调度方案。首先,根据工作流任务属性分配截止期限;其次,利用改进型布谷鸟搜索算法将工作流分割成多个子工作流,最小化数据依赖性,再利用决策树选择出满足任务QoS约束的资源;最后,根据任务的计算时间、排队时间和通信延迟的总和来判断是否满足截止期限约束,以此配置相应的资源。实验结果表明,该方案具有较短的总运行时间和较高的任务完成率。     

基于Web Service及工作流技术的物流系统应用集成方案

物流企业内部及企业之间应用系统的集成问题已成为当前物流行业信息化的关键。本文分析了Web服务技术应用集成问题,利用工作流技术提出一种解决方案,该方案中应用以Web服务形式提供给工作流系统集成,同时给出基于此方案具体的体系结构以及工作流管理系统中的流程执行步骤。     

用自我隔离工作流解决并发问题的探讨

串行作为隔离标准非常适用于传统事务,但会对工作流并发施加过多的限制。使用语义信息可以弱化或丢弃这些限制,但在并发控制中使用语义信息会让规范与管理工作流变得更复杂。自我隔离工作流会在数据库中设置和取消约束。在工作流隔离中使用约束带来2个好处:1)用SQL断言的表达能力,一个工作流设计者能做到精确的指明隔离请求;2)约束可以加到数据库的数据项或任务状态信息上完成工作流的并发控制。     

基于扩展时间工作流网的工作流过程建模

工作流管理系统中时间约束意义重大.为了在工作流模型中引入时间因素,对模型的时间性能进行评估,提出一种基于扩展时间工作流网模型.通过对模型进行形式化定义,描述了模型到工作流过程模型的映射,并针对工作流网模型存在的4种基本逻辑结构,提出一种时间线性简化规则;运用此简化规则,对工作流网模型进行压缩,以便计算所建模型的时间性能.最后结合一个工作流实例,运用提出的简化规则对约束上的常量时间进行了初步分析.     

改进多目标进化算法的云工作流调度

针对云计算和云存储资源复杂变化的定价机制给云工作流调度带来了极大的挑战问题,建立了考虑定价机制的多目标云工作流调度模型。针对云工作流调度问题的特点,设计了一种实数编码机制,使得现有的基于实数编码的交叉算子能够直接用于求解云工作流调度问题,从而避免了现有组合优化方法需要进行解的可行性修正的问题。进一步在MOEA/D算法框架下,设计了一种启发式局部搜索策略,提出了一种新的进化多目标云工作流调度算法。仿真试验结果表明,与目前主流的进化多目标优化算法相比,该算法在求得帕累托最优解集的宽广性和均匀性上具有明显的优势,且算法稳定性更好。该方法对于云平台资源利用率的提升具有重要的应用价值。