A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production

This article considers the order batching problem in steelmaking and continuous‐casting production. The problem is to jointly specify the slabs needed to satisfy each customer order and group all the slabs of different customer orders into production batches. A novel mixed integer programming model is formulated for the problem. Through relaxing the order assignment constraints, a Lagrangian relaxation model is then obtained. By exploiting the relationship between Lagrangian relaxation and column generation, we develop a combined algorithm that contains nested double loops. At the inner loop, the subgradient method is applied for approximating the Lagrangian dual problem and pricing out columns of the master problem corresponding to the linear dual form of the Lagrangian dual problem. At the outer loop, column generation is employed to solve the master problem exactly and adjust Lagrangian multipliers. Computational experiments are carried out using real data collected from a large steel company, as well as on large‐scaled problem instances randomly generated. The results demonstrate that the combined algorithm can obtain tighter lower bound and higher quality solution within an acceptable computation time as compared to the conventional Lagrangian relaxation algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Concave envelopes of monomial functions over rectangles

The construction of convex and concave envelopes of real‐valued functions has been of interest in mathematical programming for over 3 decades. Much of this interest stems from the fact that convex and concave envelopes can play important roles in algorithms for solving various discrete and continuous global optimization problems. In this article, we use a simplicial subdivision tool to present and validate the formula for the concave envelope of a monomial function over a rectangle. Potential algorithmic applications of this formula are briefly indicated. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A sequential dynamic pricing model and its applications

Consider a sequential dynamic pricing model where a seller sells a given stock to a random number of customers. Arriving one at a time, each customer will purchase one item if the product price is lower than her personal reservation price. The seller's objective is to post a potentially different price for each customer in order to maximize the expected total revenue. We formulate the seller's problem as a stochastic dynamic programming model, and develop an algorithm to compute the optimal policy. We then apply the results from this sequential dynamic pricing model to the case where customers arrive according to a continuous‐time point process. In particular, we derive tight bounds for the optimal expected revenue, and develop an asymptotically optimal heuristic policy. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Development programs for one‐shot systems using multiple‐state design reliability models

Design reliability at the beginning of a product development program is typically low, and development costs can account for a large proportion of total product cost. We consider how to conduct development programs (series of tests and redesigns) for one‐shot systems (which are destroyed at first use or during testing). In rough terms, our aim is to both achieve high final design reliability and spend as little of a fixed budget as possible on development. We employ multiple‐state reliability models. Dynamic programming is used to identify a best test‐and‐redesign strategy and is shown to be presently computationally feasible for at least 5‐state models. Our analysis is flexible enough to allow for the accelerated stress testing needed in the case of ultra‐high reliability requirements, where testing otherwise provides little information on design reliability change. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Smalltalk-80 的形式语义研究

Smalltalk-80是原型的面向对象程序设计语言和环境。本文简要地介绍了Smalltalk-80的基本概念和抽象文法,给出了其形式模型,并基于该模型描述了Smalltalk-80的静态指称语义和动态指称语义。     

无人战斗机航路规划圆切线算法

通过对无人战斗机低空进入敌防区面临的各种威胁进行分析,建立了适用于圆切线算法的威胁场模型;由于可行方向法对威胁圆叠加时规划出的航路效果不理想,提出了圆的切线算法理论作为此航路规划方法的改进,采用随机产生威胁场的方法来模拟多变的战场环境,并且进行了理论分析,最后得出仿真结果.仿真证明,将两种方法结合规划出的飞行航线在航程上是比较理想的,而且路径规则的效果也得到了很大的提高.     

Optimal stopping in software testing

In this paper we address the problem of how to decide when to terminate the testing/modification process and to release the software during the development phase. We present a Bayesian decision theoretic approach by formulating the optimal release problem as a sequential decision problem. By using a non‐Gaussian Kalman filter type model, proposed by Chen and Singpurwalla (1994), to track software reliability, we are able to obtain tractable expressions for inference and determine a one‐stage look ahead stopping rule under reasonable conditions and a class of loss functions. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

基于随机提前期的备件携行量计算方法

舰艇出海执行任务期间,需要携行一定种类和数量的物资自给。文中研究了这种单级供应条件下,如何确定备件最优携行量的问题。建立了以服务水平为目标,以资源为约束的目标规划模型,模型考虑了随机提前期和备件重要度。提出一种基于边际效费比的增量法用于求解这个模型。最后,给出一个算例并得到了一些结论。     

配套装备器材的库存与运输集成优化研究

针对我军配套装备器材订货的特点,在考虑库存容量空间限制与整套装备的最低期望满足率两种约束条件下,建立了配套装备器材的库存与运输优化模型,并应用改进的动态规划方法进行求解。结果表明：应用库存与运输的优化模型,在保障军事目标实现的前提下,有效地降低了物流成本。