MapReduce同类机排序问题的改进算法

研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3~(1/2)/3的近似算法.上述结果是对已有文献的改进.     

Analysis of the generalized Camassa and Holm equation with the improved element-free Galerkin method

In this paper, we analyze the generalized Camassa and Holm （CH） equation by the improved element-free Galerkin （IEFG） method. By employing the improved moving least-square （IMLS） approximation, we derive the formulas for the generalized CH equation with the IEFG method. A variational method is used to obtain the discrete equations, and the essential boundary conditions are enforced by the penalty method. Because there are fewer coefficients in the IMLS approximation than in the MLS approximation, and in the IEFG method, fewer nodes are selected in the entire domain than in the conventional EFG method, the IEFG method should result in a higher computing speed. The effectiveness of the IEFG method for the generalized CH equation is investigated by numerical examples in this paper.     

一个混合协调分配机制下自私调度问题的社会无序代价分析

自私调度问题是一类应用于互联网和云计算的特殊调度问题.不同于传统调度问题,它的每个工件是一个自私的参与者,可以自主地选择一台机器加工以谋求自身加工费用最小化.针对机器可以自由选择WSPT机制或PS机制的混合协调分配机制自私调度问题,通过设计一个该问题的松弛线性规划,然后写出该线性规划的对偶规划.比较上述两个规划的最优目标值,以及该自私调度问题的最优社会费用和混合Nash均衡解的最差社会费用这四个数值,分析出该自私调度问题的混合社会无序代价为4.     

应用于图形处理的一个混合流水作业排序问题的多项式时间近似策略

由于早期的图形处理器浮点运算能力不强,所以在处理图形问题时一般由中央处理器处理数据运算环节,然后再由图形处理器进行图像处理.但是最近几年图形处理器的浮点运算能力得到很大提高,相信很快就能胜任原先只有中央处理器才能完成的图形问题中的数据运算任务,为此前瞻性的研究在这样一种新情况下如何合理调度中央处理器和图形处理器来更快的处理图形问题是很有必要的.事实上该问题其实相当于一个两阶段两台处理器的混合流水作业问题:有两台处理器和一批需要加工的工件,每个工件都包含两个任务,前一个任务是为第二个任务做准备的.第一个任务可以选择在任何一台处理器上处理,而第二个任务则必须当第一个任务完成后,在第二台处理器上处理,目标是尽可能早的处理完所有工件.对于该问题,设计了一个多项式时间近似策略(PTAS)来给出最优调度方案.     

工件可预处理的单台机排序问题

考虑一个工件可预处理的单机排序问题．要求在所有工件能够按时完工的前提下,使得预处理工件的费用最小,证明了对于一般情况,该问题是NP-难的,并给出了动态规划算法．进一步,得到当每个工件的预处理费用都相同时该问题是多项式可解的,并给出了强多项式时间算法．