新的动态启发式网格任务调度算法

详细对比了传统Min-Min算法的高效特性和Max-Min算法的负载平衡特性,在原先提出以改善任务调度时间跨度性能为目标的网格任务自适应调度策略A-MM基础上,提出新的具有动态特性的启发式算法(Heuristic task scheduling algorithm based on Min-Min and Max-Min, H-MM),解决了A-MM不能动态执行的缺点.实验表明,H-MM在充分保留A-MM算法优点基础上实现了算法的动态执行特性,得到了更好的任务调度执行效果.     

异构网格环境下的可信依赖任务调度

针对异构网格环境下依赖任务调度过程中网格节点行为可信性考虑不足的问题,根据网格节点的历史行为表现,构建了一个动态信誉度评估策略,为确立任务需求与资源节点行为可信属性之间的隶属关系,定义了隶属度函数,建立了一种安全可信的网格任务调度新模型.为了实现该模型,提出一种依赖任务可信调度的粒子群进化算法.该算法通过深度值和关联耦合度的引入解决了任务间的约束关系;为克服传统粒子群算法解决离散问题时的不足,结合网格任务调度问题的具体特点,重新定义并设计了新的粒子进化方程;为预防算法陷入局部最优,引入了均匀扰动速度.仿真实验表明,该算法与同类算法相比,在相同条件下具有较高的执行效率和安全可信优化性能等.     

集群系统任务调度算法

任务调度是集群系统的关键技术之一,针对总线结构DAG模型下的任务调度问题,提出一种基于混沌改进的遗传模拟退火算法,简称Chaos-GSA。该算法在原有遗传模拟退火算法的基础上引入混沌系统,改进种群初始化方法和交叉、变异算子,提高算法的收敛速度,并在降温时考虑染色体资源平均利用率,使具有较大资源利用率的个体更容易被选择。实验结果表明:该算法与传统GSA算法相比,有明显的优越性,可以减少时间跨度,提高资源的利用率。     

一种动态自适应的网格负载平衡调度算法

根据计算机网络固有的层次结构特性，提出了基于层次结构的动态自适应的网格负载平衡调度算法，在下层结点上采用便于管理的集中式算法；而在高层结点上采用高效稳定的分布式渗透算法．该算法由于在结点的重载和轻载状态之间增加了一个缓冲状态——适度，使得系统的负载状态刻画得更为精确，从而使网格系统趋于平衡稳定；另外在负载迁移时也尽量地采取就近迁移的原则，使得系统开销和网络通讯量得以减少．     

基于系统效益的循环结构网格工作流调度算法

针对网格计算中的工作流,大部分只考虑DAG(Directed Acyclic Graph)工作流调度模型,本文对于含有更复杂的工作流结构(如循环、并行、分支等)进行了研究,并提出了一种任务优先级调度策略,用循环并行算法(LOOP-PARAL)解决了含有循环结构的网格工作流的任务调度问题,在满足用户QoS(Quarlity of Service)需求的同时,使系统的负载更加平衡,更加适合开放复杂的网格环境,提高了系统的性能.仿真实验证明了该算法的合理性和有效性.     

一种高速自适应分形图像编码算法

提出利用四叉树自适应图像划分、源块池柔性分类并结合人类视觉特性的高速分形图像编码算法．与其它同类算法相比，该算法在编码速度、压缩比和图像质量等方面均有显著提高．     

多域最小负载算法——Internet环境中的一种任务调度算法

提出了一种基于Ｉｎｔｅｒｎｅｔ环境的任务调度算法——多域最小负载算法．该算法使用多层调度策略实现可扩展性,以对应Ｉｎｔｅｒｎｅｔ数目巨大的网络和计算机,同时针对Ｉｎｔｅｒｎｅｔ环境下任务远程执行的通讯开销不能再被忽略以及存在消息传递的延迟等问题,提出了相应的解决办法．仿真的结果表明相对其它算法,多域最小负载算法有较佳的性能．     

基于最大相关熵的簇稀疏仿射投影算法

在系统辨识、回声消除、即时翻译系统中,背景噪声往往呈现出很强的脉冲特性,传统的自适应滤波算法对脉冲噪声的鲁棒性较差,而基于最大熵准则的自适应滤波算法可以有效地提高脉冲噪声环境下的自适应算法辨识性能.本文提出了一种基于最大相关熵准则的簇稀疏鲁棒仿射投影(Cluster-sparse robust affine projection,CS-RAP)算法,它可以用于辨识回声系统、卫星通信系统等簇稀疏系统.我们在基于最大相关熵准则的仿射投影算法的代价函数中引入权向量的混合L_(2,1)范数约束来利用系统的簇稀疏特性,采用基追踪法来推导CS-RAP算法.最后通过各种仿真实验,来验证提出的CS-RAP算法的鲁棒性和有效性.仿真结果表明,在脉冲噪声环境下,CS-RAP算法与其它相关算法相比具有更快的收敛速度和更低的估计偏差.     

一种启发式多路径QoS路由算法

针对一般Qos路由算法没有考虑网络负载平衡以及与传统路由算法共存的问题，设计并实现了多路径QoS路由算法．该算法应用启发式搜索策略，计算出多条满足QoS要求的路由，并根据实际网络负载情况自适应调整路由策略、动态选路，以平衡网络负载，减少网络局部拥塞．仿真实验结果表明：该算法提高了网络资源利用率，并能与传统算法良好共存，具有较好的网络性能．     

一类椭圆型变分不等式的修正代数多重网格解法及并行计算

提出了一种修正的代数多重网格解法,来求解具有对称二阶椭圆算子的变分不等式的有限元离散问题.该方法基于离散椭圆型变分不等方程的线性互补性,运用积极集策略,对Gauss-Sidel光滑迭代后的近似解进行一个后处理,以满足不等式约束,从而解决了标准代数多重网格法在求解自适应网格上的变分不等式时不收敛的问题.数值实验表明了该算法在一致网格和h-自适应网格上的计算有效性和健壮性.为了减少计算时间,根据该修正算法内在的并行度,提出了一个并行计算格式,数值结果给出了该并行的加速比和效率.     

A short note on the approximability of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints

研究关于有固定工件序约束的单机最小化最大流程排序问题模型.在该模型中,有些固定工件已事先安排好,其余的自由工件之间的加工顺序满足给定的序约束.工件之间不允许抢先中断,在同一时间,机器最多只能加工一个工件.其目标是使得最大流程达到最小.该问题即使是对没有序约束的特殊情形也已被证明是NP-困难的.给出了该问题的一个线性时间的2-近似算法,并且证明了除非P=NP,对任意的δ>0,该问题甚至没有拟多项式时间的(2-δ)-近似算法.     

带并行工件的平行机排序问题的一个新近似算法

讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能比明显地小.     

由经济驱动的网格资源管理和调度的研究

网格计算经济模型是把经济学的概念应用到网格资源管理和调度的模型,基于计算经济模型的网格资源管理与调度策略借鉴人类社会竞争的市场机制,根据用户的Q oS(Q ua lity of Serv ice)需求进行资源管理与任务调度,不仅使资源所有者和资源消费者都能实现各自的经济目标,而且使资源消费者使用轻负载和廉价的资源,达到整个网格资源整体的全局最优、合理利用.     

中庸算法——一种基于环型结构的并行调度算法

给出了分布式系统中的一种基于环结构的并行调度算法，以下称为中庸算法，并从理论上证明了该算法能够达到较好的负载平衡、最大限度的减少任务的迁移和通信、最大程度的计算本地化 并举例进行了说明     

两台可中断同类机可拒绝半在线排序问题的近似算法

研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1,+∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为s+2s+1,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界(s+1)2s2+s+1,上下界的最大差距在s=1时达到0.167.     

基于树状结构的RIPS并行调度算法

给出了分布式系统中的一种基于树结构的并行调度算法 RIPS,该算法通过在任务调度算法中引入并行技术 ,使其既具备了静态调度和动态调度的优越性 ,又能克服二者的不足 ,并从理论上证明了该算法能够达到较好的负载平衡、最大限度减少任务的迁移和任务间通信、最大程度计算本地化 ,并举例进行了说明 .     

带有到达时间和拒绝费用工件的同类机排序问题

研究了工件带有拒绝费用的m台同类机在线排序问题,m台机器的速度分别为s₁=s₂=…=s_m-1=1,s_m=s,当工件到达时,可以接收加工,占用一定的加工时间,也可以拒绝,付出相应的罚值. 目标是被接收工件的最长完工时间（makespan）与被拒绝工件的总罚值之和最小. 对工件2次到达时间问题（零时刻和r时刻各到达一批工件）设计了在线算法H,并证明该算法的竞争比为4-（2s）/（s+m-1）.     

带服务等级的同速机排序问题Multifit型算法研究

考虑一般情况下带服务等级的同速机排序问题.预先赋予每台机器和每个任务一个服务等级(grade ofservice)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.这个问题最初由HWANG等提出并研究,HWANG等给出了一个最坏情况界为2-1m-1的算法.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过32+(1/2)k,其中k是算法中预先给定的迭代次数.