多约束复杂工作流的调度优化

发布时间：2017-12-12 14:22

  本文关键词：多约束复杂工作流的调度优化

  更多相关文章： 单模态 多模态 可中断 项目调度 工作流调度

【摘要】：项目调度是广泛存在于生产制造、工业工程、计算机等系统的重要问题,项目各活动间的偏序关系、截止期等多种约束使得该类问题为典型的NP难问题。本文考虑有限可用资源的单一加工方式生产调度、可中断加工项目调度、多模态资源约束项目调度、具有准备时间和截止期约束的云工作流调度等问题,分析相应问题的特点,建立数学模型,提出有效的算法,为实际生产应用提供决策支持。论文的主要工作体现在：(1)不可中断单模态资源约束项目调度优化。建立最小化完工时间的不可中断单模态资源约束项目调度问题数学模型；将原问题分解为两个子问题：活动调度顺序确定和调度生成；提出改进粒子群算法优化活动序列,提出快速调度方法确定给定排列顺序下的活动开始时间,生成有效的调度方案。实验结果表明,本文所提方法可以为项目找到近似最优的调度方案,是有效解决该问题的方法之一。(2)可中断单模态资源约束项目调度优化。分析活动可中断加工模式对提高生产效率的影响,构建最小化完工时间的可中断资源约束项目调度问题模型；将允许一次中断的调度问题中的每个活动分成加工长度可动态调整的两个子活动,提出遗传算法优化活动调度顺序和子活动加工长度；提出基于资源管理链表的调度生成方法,根据资源可用情况动态调整各子活动加工长度。实验结果表明,在资源有限情况下允许活动可中断可以缩短项目完工时间。(3)多模态资源约束项目调度优化。考虑活动在多种加工模式下对资源需求和加工长度的不同,建立最小化完工时间的多模态资源约束项目调度问题的模型；将原问题分解为三个子问题：模式分配、活动排序和调度生成；提出离散的粒子群优化方法,采用两个协作群分别求解模式分配问题和活动排序问题,获得最优模式分配方案和最优活动序列,提出局部搜索策略进一步改善算法局部优化能力；设计正向／反向改进的调度生成方法。实验结果表明,两群协作优化方法可以找到问题的近似最优解,是求解该问题的有效方法。(4)云制造环境下具有准备时间和截止期约束工作流调度优化。根据云环境中资源的分散性和用户不同的截止期约束,以最小化工作流费用为目标,建立具有准备时间和截止期约束的云工作流调度模型；结合问题特征构造启发式方法生成初始解；构建变量的概率向量,将粒子群算法的全局优化思想引入分布估计算法,提出新的变量概率向量更新方法；提出混合分布估计算法求解工作流活动的服务选取方案。实验结果表明,本文所提算法可以有效降低工作流成本。
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18

【参考文献】

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

1 李伯虎;张霖;王时龙;陶飞;曹军威;姜晓丹;宋晓;柴旭东;;云制造——面向服务的网络化制造新模式[J];计算机集成制造系统;2010年01期

2 胡仕成,徐晓飞,李向阳;项目优化调度的病毒协同进化遗传算法[J];软件学报;2004年01期

，

本文编号：1282823