Scheduling and fair cost-optimizing methods for concurrent multiple DAGs with deadline sharing resources

为了进一步提高计算资源利用率,提出了工作流在分布式异构环境中的协同调度算法. 首先,提出反向异构最早完成时间优先(heterogeneous earliest finish time,HEFH)调度策略,可以快速求出多个工作流中每个子任务的近似最晚开始时间和子期限,并基于最晚开始时间定义了当前任务相对宽松度的衡量指标,通过对比选出所有工作流中优先级最高的任务,在现有资源中寻找具有最早完成时间的时隙进行映射,并在资源不足时根据子期限及时判定出过饱和现象,合理丢弃用HEFT算法单独调度具有最小时隙的工作流,达到吞吐量最大化. 结果表明:这种算法综合对比其他3种在吞吐量、浪费时隙率、公平度及时间复杂度方面有着较好性能.

     

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

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

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

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

资源约束下多项目调度的迭代算法

项目实施过程中往往涉及到不同项目之间的资源共享与冲突,因此在资源受限的情况下如何调度项目以满足不同项目的资源要求并缩短各项目工期是一个重要的问题．在对该问题进行分析的基础上,建立了资源约束下的多项目调度问题的数学模型,并在单项目调度迭代算法的基础上进行扩展和改进,设计了多项目调度的迭代算法．该算法结合了串行进度计划生成机制和逆向算法的优点．在保证项目任务紧前关系与资源约束的条件下,能够合理优化多项目的资源分配,从而有效地缩短多项目的总工期．通过具体实例的应用和与其他算法的比较,说明了迭代算法可以得到较好的项目进度计划．     

基于拓扑排序资源约束下多项目调度优化算法

多项目调度存在着工期和资源的竞争,调度时要考虑时序关系和资源受限两方面约束,启发式串行调度算法在每调度一个任务时都必须搜索项目的任务空间,为此提出了一种基于拓扑排序的多项目串行调度优化算法。此算法利用拓扑排序序列的特点保证任务时序关系,缩小调度时搜索空间,结合项目权重、向后影响度以及关键路径等优先规则进行资源分配和任务调度。通过具体实例验证了此算法可以求得项目调度的最优解并且能够有效地缩短调度计划生成时间。     

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

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

基于工作流的多型号产品生产计划与调度系统

为了实现多型号产品生产计划与调度过程的并行与信息有效集成,针对型号产品研制生产的特殊要求,提出了一种基于工作流的多型号产品生产计划与调度模型.建立了生产计划与调度过程模型、计划模型和组织模型,提出了一种基于协同理念的运行控制模型,详细描述了协同控制运行机制和相应的调度策略.利用Delphi6开发了多型号产品生产计划与调度管理系统.应用表明,该系统能够有效地提高生产计划与调度过程的监控能力,缩短型号研制生产周期.     

时间约束的高层次数据流调度方法

为了研究时间约束下的高层次数据流调度问题,提出了遗传算法和蚂蚁算法动态融合的解决方案.给出了时间约束调度中遗传算法的编码方法、交叉、变异和适应度函数以及蚂蚁算法中的概率选择方法和信息素的更新规则.为了找到遗传算法与蚂蚁算法的最佳切换时机,还解决了2个关键问题:遗传算法的动态结束条件和蚂蚁算法中初始信息素的产生.实验结果表明,该方法所用的平均资源数目比遗传算法少5.2%,比蚂蚁算法少4.9%;运行时间比遗传算法少44%,比蚂蚁算法少31%.     

基于生产甘特图的AGV资源约束调度方法

面对制造企业数字化、网络化和智能化转型升级需求,自动引导车(AGV)被广泛应用于生产作业的物流运输过程。在对多品种小批量工件任务的工艺路线规划基础上,迫切需要对各加工运输环节进行集成以更加符合实际生产的要求。针对有限AGV资源的柔性车间调度问题,构建了以最大完工时间、AGV数量和资源不均衡率最小化的多目标模型,采用基于生产甘特图的改进鲸鱼算法进行求解。首先,介绍了鲸鱼算法的基本原理;其次,设计了基于AGV数量、工序加工顺序和AGV编号的三段式编码方式将离散的数据转化为鲸鱼个体中的连续位置;最后,采用3种措施对算法进行改进：在初始化时通过反向学习策略获得较好的初始种群,而在迭代过程中分别加入自适应权重和变异因子,使算法的收敛精度和全局搜索能力得到提高。为验证算法的性能,用改进鲸鱼算法与基本鲸鱼算法、经典的NSGA-II求解上述模型。仿真结果表明,改进鲸鱼算法求解的质量较高且运行时间相较于NSGA-II缩短了21.6%。所提算法在有限AGV资源约束的智能化车间调度问题求解中有一定的实用价值。     

多资源约束下的多项目作业调度问题研究

分析了多资源约束下多项目作业调度问题的性质和特点,建立了以拖期最短为目标的数学模型.基于资源上作业排序形成的时序关系以及各项目内部作业间时序关系组成的新时序关系图,提出求解该问题的一般算法.为降低一般算法的计算量和复杂度,使算法能够应用到实际工程,将一般算法和规则相结合,提出一种启发式算法,给出具体的算法步骤.计算示例表明,给出的算法能有效求解多资源约束下多项目作业调度问题.