The knapsack problem with a minimum filling constraint

We study a knapsack problem with an additional minimum filling constraint, such that the total weight of selected items cannot be less than a given threshold. The problem has several applications in shipping, e‐commerce, and transportation service procurement. When the threshold equals the knapsack capacity, even finding a feasible solution to the problem is NP‐hard. Therefore, we consider the case when the ratio α of threshold to capacity is less than 1. For this case, we develop an approximation scheme that returns a feasible solution with a total profit not less than (1 ‐ ε) times the total profit of an optimal solution for any ε > 0, and with a running time polynomial in the number of items, 1/ε, and 1/(1‐α). © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

基于三维虚拟营区的设备实时信息集成

虚拟现实技术已广泛应用于营区、校园、社区等区域虚拟景观的展现,但大部分只重视静态模型信息展示,对设备信息特别是设备动态实时信息的展现涉及较少。提出了一种在三维虚拟营区中全面展现设备信息的方法。该方法将各设备管理系统数据与三维数据融合共用,通过图元接口来实现设备动态信息展示。在基于Stamp三维信息平台和3ds Max构建的虚拟营区中进行验证,实现了营区供水、供电、环境监测、安防等设备信息的综合展现。     

Production scheduling with history‐dependent setup times

We consider a parallel‐machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history‐dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times—a regular setup time and a major setup time that becomes necessary after several “hard‐to‐clean” jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

一类无穷次多项式系统极限环研究

利用平面自治系统的极限环理论和分支理论研究了一类无穷次多项式系统,并讨论了该系统极限环的存在性和唯一性。应用所得结论,推广并改进了前人的结果。     

正切函数的契比协夫逼近及其系数的加速计算法

本文给出正切函数的有理展开和契比协夫展开式系数的加速计算方法;同时在YH-1机上进行了数值试验,结果表明:用现在的系数来计算正切函数,其精度比原来正切函数的精度可提高30%左右。     

低轨预警自由段弹道估计的多项式逼近算法

低轨单星对自由段弹道的估计是天基预警系统需解决的关键技术之一.建立了低轨预警卫星对自由段弹道的观测模型,针对极大似然估计批处理算法的大运算量问题,给出了一种多项式逼近算法,由观测数据的逼近多项式在一些特定采样点的值形成伪观测数据,以伪观测数据代替原观测数据进行弹道估计.仿真表明,精度与极大似然估计相当,运算量显著降低.     

带任意泛函约束的多项式再生核的计算

讨论多项式再生核的构造与计算,指出了带任意泛函约束的多项式再生核可由带初值约束的再生核取两次投影余项而得到,并建立了具体的计算方法.     

基于多项式设计法的小推力轨迹设计

形状逼近法是小推力轨迹设计中的一种有效方法,然而现有的方法大都假定运动轨迹为某一特定的形状,而且没有考虑推力加速度的约束限制。针对小推力轨道交会问题,提出一种基于多项式的轨迹设计方法。结合极坐标系,建立基于多项式的三自由度轨迹运动模型,将轨迹设计问题转化为求解多项式的系数问题;根据运动模型推导轨迹的动力学特性,建立约束方程,并以消耗燃料最少作为性能指标,采用序列二次规划的方法对多项式的系数进行寻优计算。该方法不仅能求解多个形状设计参数不确定性问题,而且还能满足推力加速度的约束限制。仿真验证了该方法的正确性和可用性,该方法可为任务设计初步阶段的轨迹设计和燃料消耗预估提供一定的技术参考。     

Minimal LST representations of MAP(n)s: Moment fittings and queueing approximations

A Markovian arrival process of order n, MAP(n), is typically described by two n × n transition rate matrices in terms of rate parameters. While it is straightforward and intuitive, the Markovian representation is redundant since the minimal number of parameters is n² for non‐redundant MAP(n). It is well known that the redundancy complicates exact moment fittings. In this article, we present a minimal and unique Laplace‐Stieltjes transform (LST) representations for MAP(n)s. Even though the LST coefficients vector itself is not a minimal representation, we show that the joint LST of stationary intervals can be represented with the minimum number of parameters. We also propose another minimal representation for MAP(3)s based on coefficients of the characteristic polynomial equations of the two transition rate matrices. An exact moment fitting procedure is presented for MAP(3)s based on two proposed minimal representations. We also discuss how MAP(3)/G/1 departure process can be approximated as a MAP(3). A simple tandem queueing network example is presented to show that the MAP(3) performs better than the MAP(2) in queueing approximations especially under moderate traffic intensities. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 549–561, 2016     

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.