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

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

网络并行计算系统中基于多处理机任务的资源调度模型

简要描述了网络并行计算系统中任务调度问题和经典的多处理机任务调度研究现状,并将两者结合到一起建立网络并行计算系统中的新型调度模型,较详细地论述了多处理机任务的定义,然后还讨论了该模型求解的近似调度策略及其近似优化问题,给出了其特例Pm｜fix｜Cmax问题的最优调度的时间跨度下界。     

网络并行环境下多处理机任务的调度

随着网络技术的不断发展，网络上可供共享的资源越来越丰富，集群技术的兴起更是扩展了并行计算的环境．这种环境下系统中很多任务依赖于多种资源(或多个处理机)，称这样的任务为多处理机任务．本文研究基于多处理机任务的调度模型Pm{fix}Cmax,当m≥3时，这类调度问题是强NP—难的，所以只能寻求有好的逼近性能的多项式时间近似算法．文中给出了当m＝4或5时线性时间的近似调度算法，优于目前已有的最好结果，最后我们还讨论了当k≥3时的一般调度问题．     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

基于设施选址问题的费用分配问题的近似算法

许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。     

通过交互式移位-插入-删除进行基因组排序的较快算法

多染色体基因组进化问题中常见的重组事件就是移位(translocation),对此已有很多研究成果.但事实上更为普遍的情况是2个基因组包含不同基因,这需要考虑插入和删除事件.对于"通过移位-插入-删除进行基因组排序(简称SG-TID)"这个问题,此前已有一个求解移位-删除(或者移位-插入)序列的近似算法,以及求解SG-TID问题的启发式算法.在给出了移位-插入-删除距离的表达公式后,给出了在增加O(n)存储空间的条件下,O(n2)时间内求解该问题的精确算法.该算法比此前给出的算法要快.     

并行任务调度的近似算法

并行任务调度不论是从理论上还是应用上近年来都倍受关注。但是目前出现的大量算法很难应用于实际,基于此,论文探讨了典型的调度问题P3｜fix｜Cmax,这类问题是强NP-难的。论文在Goemans的研究基础上,给出了一个很简单的线性算法,构造出调度性能为9/8的半规则调度,改进了Goemans的7/6的结果。     

一类分批排序问题的复杂性分析及近似算法

探讨了分批排序问题，分析了极小化加权总完工时间问题1｜B,rj=∈{0,r}｜∑ωjCj 的复杂性，证明了此问题的NP-完备性，并对一类特定问题进行了研究。给出了解决问题的近似算法。证明了其可行性，进而对算法的性能进行了分析，结果表明算法有效地降低了计算复杂度。     

多服务中心设置问题局部搜索算法的分析与实验

讨论了多服务中心设置问题的局部搜索近似算法及其在实际计算中表现出的新性质。首先对局部搜索算法求解多服务中心设置问题的实际近似性能比给出了一个针对性分析结果,然后编程实验对局部搜索求解算法的求解时间和求解质量进行了探讨。     

最小k-击中集问题的一个随机近似算法

Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质.     

应用团划分方法改进多处理机任务近似调度

研究多处理机任务调度模型P_m|fix,p_j=1|C_max,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先（LWF）算法相比,该算法花费时间较长,近似比性能要好。     

具有优先链约束的网格作业多资源调度问题

网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型P_m|fix,p=1,chain|C_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的。     

有中断时间代价的一致并行机抢先调度问题

提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|C_max):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|C_max的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.     

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

研究多处理机任务调度模型P_m|fix,p_j=1|C_max,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。其更一般的问题是P_m|fix|C_max,在网络并行计算、多播系统及工程规划等领域都有广泛的应用。该问题早已证明为NP难问题,而且也不存在常数近似算法。基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2m+1,优于已有文献中2m的目前最好结果。     

An efficient simple metaheuristic for minimizing the makespan in two-machine no-wait job shops

This paper examines the problem of scheduling two-machine no-wait job shops to minimize makespan. The problem is known to be strongly NP-hard. A two-phase heuristic is developed to solve the problem. Phase 1 of the heuristic transforms the problem into a no-wait flow shop problem and solves it using the well known Gilmore and Gomory algorithm. Phase 2 of the heuristic improves the solution obtained in phase 1 using a simple tabu search algorithm. Computational results show that the proposed heuristic performs extremely well in terms of both solution quality and computation time. It finds an optimal solution to about 90% of the problem instances and the average deviation from the lower bond for the other problem instances is infinitesimal.     

一种基于任务全局迁移的静态调度算法

任务调度是分布实时系统中的一个关键问题.TDS等典型算法在优化条件下可得到该问题调度长度上的最优解.但是TDS等算法在节点分配时存在节点选择范围和节点执行时间范围的局限,无法最小化算法所需处理器数目.任务全局迁移调度算法GTT（global task-transferring）在保证调度长度最优的前提下,从全局范围内选择并调度任务节点,有效利用了处理器,可最小化调度所需处理器数目.优化条件下对各种算法的调度实验表明,GTT算法在加速比和效率上比TDS等同类算法有显著提高.GTT算法的时间复杂度是O（d ｜ V｜^ 2）.这里｜V｜是DAG图中的节点数,d是图中各节点入度或出度的最大值.     

基于改进遗传算法的网格任务调度算法

网格任务调度是一个NP完全问题,它关注大规模的资源和任务调度,要求采用的调度算法能够具有高效性.遗传算法被证明是解决这类小规模问题的有效算法,随着任务数和资源数的增加,遗传算法表现出慢速收敛的缺点.为了克服其缺点,提出将Min-min算法与遗传算法相结合的改进遗传算法,从而设计出很好的选择和交叉算子,提高了算法搜索能力和收敛速度.仿真结果表明该算法能更有效解决网格任务调度问题.     

基于两阶段调度的制造单元协同调度算法研究

针对单元制造问题,提出了一种基于两阶段的调度算法,通过过程分解和算法优化两方面实现问题求解。调度过程分为“预调度”和“整体调度”两个阶段,对大规模调度进行调度,不仅有效地降低了问题规模,同时制造单元调度结果对实际生产具有现实意义;调度算法采用了“精确”计算和“近似”求解相结合的方式,既提高计算效率又兼顾了全局优化目标。数值实验结果表明了的这一设计思路的有效性。