Batch scheduling on a two‐machine jobshop with machine‐dependent setup times

The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs (m ≥ 3) is known to be strongly NP‐hard even with no setup times. We focus in this article on the two‐machine case. We assume UET jobs and consider batching with batch availability and machine‐dependent setup times. We introduce an efficient \begin{align*}(O(\sqrt{n}))\end{align*} algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Benders' cuts guided large neighborhood search for the traveling umpire problem

This article introduces the use of Benders' cuts to guide a large neighborhood search to solve the traveling umpire problem, a sports scheduling problem inspired by the real‐life needs of the officials of a sports league. At each time slot, a greedy matching heuristic is used to construct a schedule. When an infeasibility is recognized first a single step backtracking is tried to resolve the infeasibility. If unsuccessful, Benders' cuts are generated to guide a large neighborhood search to ensure feasibility and to improve the solution. Realizing the inherent symmetry present in the problem, a large family of cuts are generated and their effectiveness is tested. The resulting approach is able to find better solutions to many instances of this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

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     

Flow shop scheduling with earliness,tardiness, and intermediate inventory holding costs

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work‐in‐process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig‐Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig‐Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near‐optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly ????‐hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near‐optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Higher‐order Markov chain models for categorical data sequences*

In this paper we study higher‐order Markov chain models for analyzing categorical data sequences. We propose an efficient estimation method for the model parameters. Data sequences such as DNA and sales demand are used to illustrate the predicting power of our proposed models. In particular, we apply the developed higher‐order Markov chain model to the server logs data. The objective here is to model the users' behavior in accessing information and to predict their behavior in the future. Our tests are based on a realistic web log and our model shows an improvement in prediction. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

空地协同反干扰目标交叉定位融合算法

传统双站交叉定位精度较高,但在基线及其延长线无法定位且在基线附近定位误差迅速增大;预警机测高交叉定位可实现全空域定位,但定位精度不高.针对这两种定位方法的优缺点,提出了基于传统交叉定位和预警机测高交叉定位的距离解算加权融合算法,并进行了仿真分析比较,证实了算法的有效性.     

单兵系统数据模型

讨论了单兵系统的体系结构和信息要素,并结合单兵系统在联合作战中的应用例子,对其业务过程和信息流进行初步分析。然后通过IDEF1X方法,设计单兵系统基于关系数据库的数据模型。最后讨论了模型的规范化问题,并给出检验数据模型的方法。     

含有多普勒频率的毫米波/红外融合滤波算法

由于毫米波雷达(MMV)和红外(IR)两种传感器在跟踪目标方面具有各自的优势,故使用两种传感器进行数据融合可以得到较单一传感器更高精度的目标数据,从而提高滤波精度。针对上述两种传感器的特点,对采样数据进行时空对准,结合UT变换思想,并在此基础上提出一种含有多普勒频率的无迹卡尔曼滤波(UKF)算法。新算法较单一MMV或者IR传感器滤波算法精度有了明显提高,并且较MMV/IR融合的传统扩展卡尔曼滤波(EKF)算法的精度也有提高。仿真结果证明了新算法的有效性和合理性。     

基于GA-SVDD的轴承性能退化评估

为解决因机械设备轴承损伤导致机械故障而无法正常工作的问题,提出了一种基于GA-SVDD的轴承性能退化定量评估方法。该方法采用遗传算法优化选择特征参量,并建立SVDD超球体模型,运用SVDD距离评估轴承的性能退化程度。实验分析表明：该方法能够有效地对轴承性能退化过程的细节进行描述,实现对待测样本退化程度的定量评估。