多处理机调度问题的粒子群优化算法

建立了多处理机调度问题数学模型,结合遗传算法的思想提出了粒子群算法来解决多处理机调度问题。经过比较测试,4种粒子群算法的效果都比较好,特别是交叉策略A和变异策略A的混合粒子群算法是最好的且简单有效的算法。

关于多处理机调度问题的量子粒子群算法研究

对多处理机调度问题建立数学模型,提出了将量子计算和粒子群算法相结合的方法来解决这类调度问题,该方法不仅寻优速度快,而且提高了进化后期算法的收敛精度。通过对比测试,体现了量子粒子群算法的有效性。

多处理机调度问题的蚁群优化算法

传统蚁群算法存在收敛速度慢、计算时间长、易陷入局部最优解等方面的缺陷。通过对蚁群信息素更新、策略选择、参数选择等各方面进行改进,提出一种更加高效的多处理机调度蚁群优化算法。实验证明:与其他优化算法相比,该算法能在较短的时间内找到更好的调度策略,具有较好的收敛性和有效性及优良的全局优化性能。

一种求解多处理机调度问题的α-平坦化调度算法

在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。

利用组合型交叉熵实现多处理机调度的算法

为提高大型多处理机调度的效率与稳定性,提出一种利用组合型交叉熵实现多处理机调度的方法。该方法依据处理机与作业的约束关系,将处理机调度问题表示为使目标函数最小化的线性0-1整数规划模型,采用组合型交叉熵算法对该模型进行优化求解。利用组合型交叉熵算法对多处理机问题的具体事例进行测试,与模拟退火算法和蚁群算法的测试结果对比分析。结果表明:组合交叉熵算法的优化速度是蚁群算法的6.1倍,是模拟退火的29.5倍,该算法稳定性高,收敛速度快,运行时间短,在解决大型多处理机问题时效率明显高于模拟退火算法和蚁群算法。

基于剪枝算法解决多处理机调度问题的算法研究

针对当前算法求解多处理机调度问题的不足,从剪枝策略的角度提出了一种笨人算法。笨人算法的思路是:不断排除最差解,直到剩下唯一解。这种剪枝算法至少保证当前的选择不是最差的,并且对计算过程的最大复杂度作了一个估计。经过实验分析,对于N×N的MSP,多数情况下,笨人算法比贪心算法、遗传算法、差分进化算法的表现更为稳定和优秀,是一种有效的算法,也为相关问题的研究提供了一种新的思路。

一种混合粒子群与蚁群算法在多处理机调度中的应用研究

提出了一种基于蚁群优化和粒子群优化的混合算法以解决多处理机调度问题。这种混合算法利用蚁群算法和粒子群优化算法的特性,可以显著提高计算效率,具有较大的实用价值。

PGR机中多处理机调度的研究

多处理机调度是多处理机系统中一个非常关键的问题．本文提出了多处理机调度的一种动态负载分担模型，并以并行图归约机ＰＧＲ为背景．设计了一个分布式动态调度算法ＡＵＴＯ．经过详细地模拟之后，用Ｏｃｃａｍ语言实现在ＰＧＲ机仿真实验系统上．模拟和实现结果都证明动态负载分担模型是一个非常有效的多处理机调度策略．在本文中给出了部分模拟和实现结果．

一种求解多处理机调度问题的自适应蚁群算法

将蚁群算法应用于求解多处理机调度问题,提出一种自适应蚁群算法.算法以最小化makespan为调度目标,根据蚂蚁留下的信息素指导蚁群在解空间展开全局搜寻,将任务分配在恰当的机器上,并通过自适应调整阈值实现全局探索与精细查找的平衡.实验结果表明算法具有较好的优化性能.

多处理机调度问题的差分算法

将Karmarkar和Karp关于数的划分问题的差分算法推广到多处理机调度问题,并通过统计检验的结果表明,这种差分算法在通常情形下具有比较好的平均性能。

混合遗传算法及在多处理机调度问题中的应用

针对遗传算法存在收敛速度较慢,易陷入局部极值的缺点,通过算法混合,提出一种基于混沌及差分演化的混合遗传算法。该算法利用混沌运动的遍历性和内在随机性择优产生初始群体,借鉴差分进化算法中的繁殖策略,使染色体在解空间中更有效的搜索最优解。最后将该混合遗传算法应用于多处理机调度问题中,实验表明,该混合算法具有较高的优化效率,能寻找到更好的优化结果。

粒子群优化多处理机任务调度算法

提出基于粒子群优化的多处理机调度算法,采用列表调度,同时把粒子群的矢量表达方式转换为基于调度优先级的模型。调度结果显示能提高全局搜索能力,加快进化速度,优于模拟退火等启发式算法结果。

基于差分进化算法多处理机任务调度研究

本文主要基于现代启发式差分算法讨论多处理机调度,多处理机调度是NP组合优化问题,目前多采用启发算法。差分进化算法是最近提出的进化算法,主要根据父代个体之间矢量差构造下一代,是一种全局优化搜索方式。本文考虑采用差分进化矢量优先级模型描述调度顺序进行调度,与模拟退火算法比较得到较好调度结果。

独立多处理机任务静态调度问题的近似算法

研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的2m+1近似算法和问题Pm|fix|Cmax的2 m近似算法,优于目前已有文献的最好结果.

任意处理时间的多处理机任务调度近似算法

研究多处理机任务调度模型Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为(2m)^(1/2),优于E.Bampis等人给出的3m^(1/2)的结果。

云计算环境下多截止期工作调度算法研究

随着大数据对人们生活的影响逐渐增大,数据存储和计算需求不断增加,云计算的兴起有效地满足了这一需求。在实时性要求较高的云计算系统中,来自客户端的资源请求被视为具有截止期限和一定收益的两阶段工作,云服务器被视为两阶段机器。不同资源请求的截止期限通常不同,如果云中心能在资源请求的截止期限之前完成该请求,就可以获得相应的收益。现有的以收益最大化作为优化目标的两阶段工作调度均是在一个公共截止期限制下进行的,而实际情况往往是不同的资源请求可能有不同的截止期限。基于当前云计算应用和数据中心数据处理的需求,建立了云计算系统中工作调度的新数学模型。首次提出了具有多个截止期的两阶段工作在多处理机上的调度问题,并给出了一个近似比为(3 k+ε)的多项式时间近似算法。当机器数目为固定常数时,近似比进一步降低为(k+ε),其中k是一个固定常数,即截止期的个数,ε是大于0的任意常数。针对特殊的T-处理时间大于R-处理时间模型,在单个两阶段机器上,给出了一个近似比为2的伪多项式时间近似算法,进一步降低了算法的近似比。

混合变邻域和声搜索的独立任务调度问题研究

结合和声搜索和变邻域搜索算法的特点,提出混合的和声变邻域搜索算法,并将混合算法用于解决多处理机独立任务调度问题。混合算法采用列表调度方法对和声解进行编码,把和声分量转换为基于优先级的独立任务调度模型,利用变邻域搜索算法对和声解进行局部搜索以提高和声算法的搜索效率和解质量,利用模拟退火算法中的Metropolis准则作为新解接受准则,防止算法陷入局部极值。仿真实验对比结果表明,混合算法在解决独立任务的多处理机调度中具有更强的全局搜索能力和更快的收敛速度,并且能够跳出局部极小获得更高质量的解。

优先约束的混合实时任务动态调度算法

为了对较大规模问题在短时间内给出满意的解并调度随机到达的非周期任务,提出了一种动态混合调度算法。在第一个截止期限错失时刻,通过分析系统的运行情况,推导出具有优先约束的实时任务可调度的充分条件。在系统运行前,判定周期任务的可调度性,预分配足够的处理机。当非周期任务到达系统时,在保证周期任务可调度的前提下重新给周期任务和非周期任务分配处理机。该算法具有多项式时间复杂性,适合解决较大规模的多处理机调度问题。实验结果表明,该算法有效提高了处理机的利用率和非周期任务的接收率。

P_4|fix|C_(max)问题的最优规则调度算法

多处理机任务调度问题Pm|fix|Cmax(m3)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.