On online bin packing with LIB constraints

In many applications of packing, the location of small items below large items, inside the packed boxes, is forbidden. We consider a variant of the classic online one‐dimensional bin packing, in which items allocated to each bin are packed there in the order of arrival, satisfying the condition above. This variant is called online bin packing problem with LIB (larger item in the bottom) constraints. We give an improved analysis of First Fit showing that its competitive ratio is at most , and design a lower bound of 2 on the competitive ratio of any online algorithm. In addition, we study the competitive ratio of First Fit as a function of an upper bound (where d is a positive integer) on the item sizes. Our upper bound on the competitive ratio of First Fit tends to 2 as d grows, whereas the lower bound of two holds for any value of d. Finally, we consider several natural and well known algorithms, namely, Best Fit, Worst Fit, Almost Worst Fit, and Harmonic, and show that none of them has a finite competitive ratio for the problem. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

基于蚁群算法的被动目标定位算法

通过对蚁群算法的研究,用蚁群算法成功解决了无源测向定位中消除虚假点,对真实交点进行正确聚类的难题.并通过Matlab 仿真实验证明了该算法的有效性.同时该算法具有目标关联确率高、计算速度快、鲁棒性强等优点.     

支持并行工程的造船分段作业计划系统

针对传统造船模式下,车间作业计划与工艺设计串行工作方式的缺点,基于并行工程的原理,提出了分段作业计划与工艺设计的集成运行模式,为实现造船CAPP系统与PPC系统的集成化和并行化提供了实现的基础。针对集成模式的特点,建立了分段作业计划系统资源优化的数学模型,应用遗传算法解决了针对任意分段装配工艺方案的多资源平衡优化问题,可以得到每项作业最优的开工时间,同时能够给出多种资源的最优分布结果,满足了多工艺方案之间资源利用率的比较。最后,给出了计算实例,计算机模拟结果说明了这一方法的有效性。     

Hamilton系统辛算法的Nekhoroshev稳定性分析

研究辛算法应用于Hamilton系统时的Nekhoroshev稳定性,利用辛映射的插值定理,得到了辛算法的插值定理,进而把它应用到凸Hamilton系统,得到了辛算法的Nekhoroshev稳定性,即辛算法在指数长时间内的稳定性。     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

人工免疫在军事领域的应用

人工免疫学是继神经网络、进化计算之后新的智能计算研究领域和研究热点.为探讨人工免疫可运用的军事领域,给相关科研工作者提供新方法、新思路,对生物免疫系统的一些概念进行了介绍,简要分析了生物免疫系统中的免疫机制,人工免疫系统基本特征,然后着重分析了该学科在信息系统安全、防御系统设计、目标识别、故障诊断、优化、火力分配等方面中的应用.     

Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.     

Reliability inference for field conditions from accelerated degradation testing

Accelerated degradation testing (ADT) is usually conducted under deterministic stresses such as constant‐stress, step‐stress, and cyclic‐stress. Based on ADT data, an ADT model is developed to predict reliability under normal (field) operating conditions. In engineering applications, the “standard” approach for reliability prediction assumes that the normal operating conditions are deterministic or simply uses the mean values of the stresses while ignoring their variability. Such an approach may lead to significant prediction errors. In this paper, we extend an ADT model obtained from constant‐stress ADT experiments to predict field reliability by considering the stress variations. A case study is provided to demonstrate the proposed statistical inference procedure. The accuracy of the procedure is verified by simulation using various distributions of field stresses. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

基于MUSIC算法的罗兰C接收机天地波自动识别方法研究

针对常规罗兰C接收机天地波识别方法不能有效利用信号能量的缺点,根据天波到来时间的估计与合成信号频率的分离相似的特点,提出了一种基于多信号分类算法估计天波延迟的方法.该方法在低信噪比条件下可分离出地波和天波,并能根据天波的延迟变化实时地选择接收机采样基准点的最佳位置.计算机仿真结果表明,该方法可以用于天地波的自动识别,能增加基准点处的信噪比,因而能显著提高罗兰C接收机的性能.     

多目标的分布式协同进化MDO算法

通过引入非优超排序和排挤的多目标处理机制 ,将分布式协同进化MDO算法的能力扩展到多目标的多学科设计优化问题。多目标的分布式协同进化MDO算法在保持各学科充分自治和各学科并行设计优化协同的基础上 ,通过一次运行即可获得具有良好分布的多个Pareto最优解 ,逼近整个Pareto最优前沿。应用于导弹气动 /发动机 /控制三学科两目标设计优化问题 ,与约束法计算结果的对比表明算法能够有效逼近该问题的Pareto最优前沿 ,为设计决策提供了丰富的信息