Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Iterative coloring extension of a maximum clique

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds, its successive neighbors are considered; in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. © 2001 John Wiley & Sons, Inc. Naval Research Logistic 48: 518–550, 2001     

综合系统多重递阶控制设计方法研究(一)空-空航炮的机身指向火控解算方法

为了满足综合系统多重递阶控制设计方法的需求,建立了空-空航炮的机身指向火控解算方法.该方法是在期望弹丸命中目标的情况下求解机身期望指向及其变化率.在某验证机的控制增稳系统上,采用所建立的火控解算方法以及综合系统多重递阶控制设计方法,设计了综合飞行/火力控制系统.仿真结果表明,所建立的空-空航炮机身指向火控解算方法较好地满足了综合飞行/火力控制系统的设计需求,获得了良好的综合控制系统动态性能.     

分布式麦克风阵列的声源定位

声定位探测技术的无源被动特性,使其在定位技术研究领域内独树一帜,时延估计和定位算法是支持这一技术的核心。DUET时延估计算法简单,通过对接收到的信息分段帧移加窗处理,能够有效识别有用语音信息,时延估计精度较高,在高噪声的环境中非常适用;球面定位算法是基于时延估计提出的,对麦克风的排列形式不固定,适用于任意排布的麦克风阵列,并且在时延估计精度较高的情况下,能够很准确地对声源目标进行定位。     

增量式神经网络聚类算法

神经网络模型具有强大的问题建模能力,但是传统的反向传播算法只能进行批量监督学习,并且训练开销很大。针对传统算法的不足,提出全新的增量式神经网络模型及其聚类算法。该模型基于生物神经学实验证据,引入新的神经元激励函数和突触调节函数,赋予模型以坚实的统计理论基础。在此基础上,提出一种自适应的增量式神经网络聚类算法。算法中引入"胜者得全"式竞争等学习机制,在增量聚类过程中成功避免了"遗忘灾难"问题。在经典数据集上的实验结果表明:该聚类算法与K-means等传统聚类算法效果相当,特别是在增量学习任务的时空开销方面具有较大优势。     

多级电磁线圈发射器时序触发策略研究

为优化多级同步感应线圈电磁发射器(SICEML)性能,以提高发射速度和能量转换效率为检验指标,以影响上述指标的触发时序为优化对象,采用遗传算法建立了单级同步感应线圈型电磁发射器触发位置优化数学模型,计算出了最佳触发位置,通过数值和有限元两种仿真系统对优化结果的正确性进行了验证;采用该方法对两级以及10级同步感应线圈型电磁发射器的触发时序进行了优化研究,并进行了仿真验证;为解决了仿真系统误差的问题,提出采用动子线圈在各级的触发位置和速度作为控制因素的双控触发方式,并研究分析了仿真过程中触发开关的随机抖动对出口速度误差的影响。     

考虑空间几何关系的反交会规避机动方法

针对具有自主接近能力的航天器开展反交会规避机动方法研究。建立仅测角相对导航模型,对完全不可观测机动进行定义,基于空间几何关系推导并证明了完全不可观测机动是不存在的。以施加规避机动后追踪器对逃逸器的测量值与未机动时的差异为优化目标,利用矢量乘积原理设计目标函数,建立优化模型并对变量约束进行分析,随后采用遗传算法对最优规避机动方向进行优化。给出的仿真算例结果表明:提出的规避机动方向计算方法能够使目标函数值达到最小,从而提升追踪器对逃逸器的状态估计难度,降低其估计精度。这为规避机动问题研究提供了一种新的视角,可为以主动接近航天器为新对象进行的规避研究提供有益借鉴。     

基于改进匈牙利算法的多技能人员调度方法

人员的优化配置对于提高装备制造效率具有重要意义。针对经典匈牙利算法不能解决具有并联环节的人员指派问题的不足,提出利用虚拟工作代替并联环节,将问题转化为典型的指派问题;通过判断虚拟工作的可实现性,迭代搜索得到最优解。以某多技能人员任务指派系统为例,详细介绍了该优化方法的步骤。优化结果很好地验证了改进算法的有效性。     

基于贝叶斯网络的空中目标威胁估计算法

联合作战条件下,指挥决策人员在海量描述战场态势的数据和信息面前往往会束手无策,无法快速作出正确的决策。贝叶斯网络模型是一种基于概率推理的网络化数学模型,能够通过一些变量的信息来获取其他的概率信息,从而解决不定性和不完整性问题。提出了一种基于贝叶斯网络的空中目标威胁估计算法,用空中威胁网络模型找到空中威胁目标各属性之间的潜在关系,并建立空中目标威胁估计算法,最后以一个实例来验证该空中目标威胁估计的计算过程和有效性。     

VNS和SA相结合的指挥控制资源部署

针对指挥控制资源部署问题,引入任务复杂度来定义决策实体的工作负载,并建立以最小化决策实体工作负载的均方根为目标的优化模型。针对传统的层次聚类法容易陷入局部最优,提出了一种变邻域搜索(Variable Neighborhood Search,VNS)和模拟退火(Simulated Annealing,SA)相结合的具有全局性的求解方法,使用VNS进行全局寻优,使用SA对VNS中的邻域进行局部寻优。最后通过一个联合作战案例的平台调度方案,验证了所提方法的优越性。