成本约束的网格工作流时间优化方法

针对成本约束有向无环图DAG(directed acyclic graph)表示的网格工作流完工时间最小化问题,提出两个基于优先级规则的迭代启发算法.算法利用并行活动特征定义正向分层和逆向分层两个概念,将其分别引入最大收益规则MP(maximum profit),得到正分层最大收益规则MPTL(maximum profit with top level)和逆分层最大收益规则MPBL(maximum profit with bottom level).两规则每次迭代尽量以完工时间的最小增加换取总费用的最大降低,逐步将分层初始解构造为满足成本约束的可行解.模拟结果表明,两规则在获得较少迭代次数和运行时间的同时,能显著改进MP规则的平均性能,且MPBL优于MPTL.     

有准备时间无等待流水车间调度的搜索算法

利用迭代变化邻域搜索算法(IVNS)求解最小化总完工时间的有准备时间无等待流水车间调度问题.设计局部搜索算法需要考虑3个关键因素:所用邻域、解评估和局部最优的克服.因此,定义了3个较大规模邻域以扩大搜索范围.为加速解评估,利用目标增量来避免重新计算每个解的目标函数值,使相邻解比较只需常量时间,NEH插入算法的时间复杂度降低一阶.IVNS通过切换邻域和扰动重启,来克服局部搜索易于陷入局部最优解的缺点.通过与求解该问题的当前最好算法在5400个标准算上,以相同CPU时间进行的实算比较,实验结果统计分析验证了IVNS的寻优性能明显优于参照算法.     

基于工作流的Web服务组合多视图模型

基于工作流建模技术,提出一种包含个性化服务质量需求且具有多视图特性的服务组合模型,包括过程模型、资源模型、需求模型和服务组合相关数据。过程模型建立在活动网络图基础上,扩展了其表述能力,具有较好的可读性;资源模型考虑服务的功能和非功能特性,有很好的扩展性;需求模型采用定性和定量描述相结合的方式,来体现个性化的全局服务质量需求。基于该模型给出了一个服务组合建模的原型系统,初步验证了模型的可用性。     

DTD与Schema简介

XML是一种标示语言,具有较好的描述能力。介绍了XML的组成部分－文档类型定义DTD以及较有发展潜力的Schema。对DTD文档的引用、DTD元素属性和类型的说明进行了简单地说明。Schema自身的种种优点使得它极具发展潜力。     

基于串归约的网格工作流费用优化方法

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明:BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.     

基于扩展关键活动的工作流调度算法

服务资源分配和调度在开放网格服务架构环境中是一个复杂且具有挑战性的问题.为适应网格计算环境下服务资源的动态性和自治性,提出一个基于扩展关键活动的工作流调度算法,采用动态选择所需服务资源的策略,工作流完成时间和所需成本得到一定程度的平衡.实验结果表明该调度算法在完成时间、成本等方面可得到较满意的结果,能更好地满足用户实际需要.     

基于贝叶斯分类的网上书店潜在用户挖掘

以网上书店为例,利用贝叶斯分类预测技术,进行了发现潜在客户群体的研究,用随机选取的10组样本进行试验预测,预测准确率达96.5%,表明了该算法是有效的。     

网格环境下工作流的费用-时间调度算法

开放网格服务架构（OGSA）和计算经济模型的提出，使得动态的、不同QoS的服务支持下的资源调度成为一个复杂且具有挑战性的问题。该文提出了网格环境下基于费用-时间的工作流调度算法，该算法采用动态资源选择策略适应网格计算环境下的动态性和自治性。在追求较小的工作流完成时间的同时，对费用进行了优化。模拟结果显示该调度算法符合计算网格的复杂环境，能够更好地满足不同用户的实际需要。     

服务工作流的混合粒子群调度算法

服务工作流的时间-费用优化是一个基本且难以求解的问题.目前求解该问题的分层算法将工作流任务的截止时间限定在固定的时间窗口内,限制了算法的搜索范围,通过引入粒子随机极值扰动、位置回退、交叉繁殖等算子,将搜索范围扩大到整个解空间以大大提高获得最优解的概率;改进适合连续优化问题的有效粒子群算法,提出适合离散优化问题的混合粒子群(HPSO)算法.模拟实验结果表明HPSO将目前最好算法的性能平均提高了12.82%,对120个活动的工作流实例仅需要6.5s的时间.     

基于优先级规则的网格工作流调度

 网格资源需求的不断增长使价格成为资源进行竞争的有效手段,有向无环图DAG(Directed Acyclic Graph)表示的工作流时间费用优化问题是网格环境下一个重要问题.通常情况下,DAG应用调度属于NP-Hard问题.通过分析活动间的时序特征,给出时间耦合强度TCS (Time-dependent Coupling Strength)的定义,用于标识一个活动最大的时间耦合活动个数;将其作为优先级规则的一个重要信息和BF规则(Best Fit)结合,设计出时间耦合强度最适规则BFTCS ( Best Fit with Time-dependent Coupling Strength),用于启发式算法的改进阶段,逐步提高初始可行解的性能.模拟实验结果表明,相对现有的启发式算法,基于BFTCS规则的启发算法能获得最好的性能和较快的运行效率;最后讨论了问题参数对算法性能和效率的影响.