An absolute approximation algorithm for scheduling unrelated machines

Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 ? 1/m)p_max, p} is presented, where p_max is the largest job processing time and p is the mth element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p_max. The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm²) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A heuristic for maximizing the number of on‐time jobs on two uniform parallel machines

We consider the problem of maximizing the number of on‐time jobs on two uniform parallel machines. We show that a straightforward extension of an algorithm developed for the simpler two identical parallel machines problem yields a heuristic with a worst‐case ratio bound of at least . We then show that the infusion of a “look ahead” feature into the aforementioned algorithm results in a heuristic with the tight worst‐case ratio bound of , which, to our knowledge, is the tightest worst‐case ratio bound available for the problem. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

高分辨率雷达目标一维距离像的编码识别算法

文中提出了一种高分辨率雷达目标一维距离像的识别算法。该算法借用图像处理方法,先对雷达目标的一维距离像进行编码,经过傅里叶变换提取一组形状特征。这组特征精确地描述了一维距离像曲线的走向。而后,利用人工神经网络技术对一定姿态角变化范围内的这组形状特征进行识别。实验结果表明,可以获得良好的识别效果。该算法为雷达目标一维距离像识别算法的实时处理提供了一条有效途径。     

果蝇算法和5种群智能算法的寻优性能研究

截止到目前为止进化式算法主要有遗传算法、蚁群算法、鱼群算法、免疫算法、粒子群算法.这些算法已经被广泛地用于寻优,但都有各自的缺点,导致其不易被用于解决实际问题.某学者提出了一种新群智能算法——果蝇算法.对该算法的起源进行分析,并将该算法与其他算法对比,通过仿真分析各个算法寻优性能.重点分析果蝇算法的寻优性能,得出果蝇算法简单、参数少、易调节、计算量小、寻优精度较高,从而较容易被用于解决实际问题,对于复杂问题算法可能不稳定.指出该算法的缺点,提出应改进的地方,对其应用前景作了概括.     

舰船固定磁场分量分离的一种新方法

为了准确了解舰船的固定磁场分布,进而对舰船磁性防护作出指导,用等效磁偶极子的方法对舰船固定磁场分量分离的方法进行了研究,通过对固定磁场垂直分量总和的曲线进行分析,根据磁偶极子组合产生磁场规律的先验知识,选择最佳的磁偶极子的排列方式,然后对磁偶极子磁矩范围进行估计,最后利用遗传算法这种全局优化算法求出磁源的参数,进而分离出固定磁场各个分量。仿真计算结果表明,该方法能够比较好地搜索到磁偶极子的最佳数目、位置和磁矩,可以用于舰船固定磁场的分离。     

Interval scheduling: A survey

In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A m‐parallel crane scheduling problem with a non‐crossing constraint

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

多核数字信号处理器矩阵乘卷积算法性能评测

矩阵乘卷积算法能够为各种卷积配置提供高性能基础实现,是面向给定芯片进行卷积性能优化的首要选择。针对国防科技大学自主研制的飞腾异构多核数字信号处理器(digital signal processor, DSP)芯片的特征以及矩阵乘卷积算法自身的特点,提出了一种面向多核DSP架构的高性能并行矩阵乘卷积实现算法ftmEConv。该算法由输入特征图转换、卷积核转换、矩阵乘以及输出特征图转换这四个均运行在通用多核DSP上的并行化部分构成,通过有效挖掘通用DSP核中功能单元的潜力来提升各个部分的性能。实验结果表明,ftmEConv实现了高达42.90%的计算效率,与芯片上的其他矩阵乘卷积算法实现相比,获得了高达7.79倍的性能加速。     

基于微分平坦的高超声速滑翔飞行器轨迹规划

针对高超声速滑翔飞行器再入轨迹规划问题,提出了一种基于微分平坦理论的三自由度轨迹生成方法。在分析纵向运动简化模型的微分平坦属性基础上,将纵向参考轨迹规划问题映射到平坦输出空间,消除微分动力学约束的同时降低系统设计的维数,进而提高求解效率;采用全局插值多项式参数化平坦输出函数,将问题转换为非线性规划问题求解;设计比例-微分反馈控制律跟踪纵向参考轨迹,同时采用航向角误差走廊控制侧向运动,实现三自由度轨迹生成。仿真分析表明所提出的方法能够较快生成满足多种约束且性能优化的飞行轨迹。     

复杂线型小水线面双体船兴波阻力数值计算方法研究

将分段幂多项式拟合方法与线性兴波阻力理论相结合,提出一种针对复杂线型小水线面双体船的兴波阻力数值计算方法,该方法应用于常规小水线面双体船的兴波阻力计算,表明该方法能在常规的幂多项式拟合方法的基础上进一步提高计算精度,同时也验证了该方法的正确性,将该方法的计算结果与复杂线型小水线面双体船剩余阻力的试验结果相比,两者吻合较好,证明了该方法用于复杂线型小水线面双体船的兴波阻力计算是可行的。