Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Single‐machine scheduling with deadlines to minimize the total weighted late work

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.     

目标宽频带RCS的快速算法研究

目标宽带RCS预估算法一直是计算电磁学的一个研究热点,本文分别研究了渐近波形估计技术（AWE）与最佳一致逼近技术在宽频带RCS预估领域内的应用。首先,介绍了传统矩量法计算RCS的原理,并分析了两种快速算法的计算过程。然后,采用这两种技术,分别计算了简易飞机模型的RCS值,并对这两种方法进行比较。计算结果表明相比传统的矩量法,这两种方法在不影响精度的前提下大大提高了计算效率。同时,相比渐近波形估计技术,最佳一致逼近技术在节省内存,节约时间方面更具优势。最后,采用最佳一致逼近理论,结合电磁计算软件,实现较大尺寸目标的宽频带RCS的计算。     

A dual criteria sequencing problem with earliness and tardiness penalties

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than . © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020     

用线性规划法设计复系数FIR滤波器

讨论了在复Chebyshev逼近意义下设计复系数FIR滤波器问题。直接把复Chebyshev逼近问题离散化成有限维线性规划问题 ,再用单纯形法求解这种方法一直被认为只能设计实系数滤波器 ,而且计算量大、收敛速度慢。本文从直接离散化出发 ,推导出一种求解此问题的改进的单纯形算法 ,适用于设计复系数滤波器 ,极大地减小了计算量 ,提高了收敛速度。并证明了它与通过求解半无限线性规划的对偶问题而得到的改进的单纯形法是等价的。最后给出了算法的仿真结果     

Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

高超声速飞行器组合导航系统研究

为提高高超声速飞行器的导航精度,在SINS/GPS位置、速度组合导航模型基础上增加了GPS姿态信息,推导了姿态算法中姿态角误差与平台误差角的关系。通过理论分析说明了其可消除数学模型误差,提高系统的姿态精度,并以此建立了SINS/GPS组合导航系统姿态、位置、速度观测方程。通过仿真验证了该算法的有效性,结果表明SINS/GPS姿态、位置、速度组合导航可以有效提高高超声速飞行器导航定位精度。     

Approximation algorithms for capacitated stochastic inventory systems with setup costs

We develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014     

面向监督学习的稀疏平滑岭回归方法

岭回归是监督学习中的一个重要方法,被广泛用于多目标分类和识别。岭回归中一个重要的步骤是定义一个特殊的多变量标签矩阵,以实现对多类别样本的编码。通过将岭回归看作是一种基于图的监督学习方法,拓展了标签矩阵的构造方法。在岭回归的基础之上,进一步考虑投影中维度的平滑性和投影矩阵的稀疏性,提出稀疏平滑岭回归方法。对比一系列经典的监督线性分类算法,发现稀疏平滑岭回归在多个数据集上有着更好的表现。另外,实验表明新的标签矩阵构造方法不会降低原始岭回归方法的表现,同时还可以进一步提升稀疏平滑岭回归方法的性能。