An optimal ordering policy for situations with uncertainty in supply

A one-period inventory model where supply is a random variable with mean proportional to the quantity ordered has been considered. Under new better than used in expectation assumption on the supply variable, a strategy which maximizes a minimum profit has been suggested. An estimate for this maximin order quantity whenever the (customer) demand distribution is unknown has been proposed and almost sure convergence of this estimate to its true value with increasing sample size has been established.     

Note: On the greedy algorithm for optimal assembly

The greedy and balanced algorithms for the optimal assembly of arbitrary structure functions (not necessarily binary) are discussed. Conditions under which these algorithms yield optimal configurations are deduced. © 1992 John Wiley & Sons, Inc.     

基于频率优化组合的KBR系统时标误差校正

时标误差是K波段精密测距仪(KBR)的一个重要测距误差源,现有的时标误差校正方法依赖于对星间时标偏差的精确测量。针对目前我国星间时标偏差测量精度不能满足校正需求的问题,提出了基于双频优化组合的时标误差校正方法,推导了优化频率之间应该满足的定量关系。研究了双频优化组合的实现,指出原有的KBR系统无法实现频率优化,在此基础上设计实现了一种改进频率流程的KBR系统,并对新的时标误差校正方法进行了实验验证。实验结果表明,基于双频优化组合的时标误差校正方法和改进的KBR系统有效降低了对星间时标偏差测量精度的要求。     

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

An optimal critical level policy for inventory systems with two demand classes

Traditional inventory systems treat all demands of a given item equally. This approach is optimal if the penalty costs of all customers are the same, but it is not optimal if the penalty costs are different for different customer classes. Then, demands of customers with high penalty costs must be filled before demands of customers with low penalty costs. A commonly used inventory policy for dealing with demands with different penalty costs is the critical level inventory policy. Under this policy demands with low penalty costs are filled as long as inventory is above a certain critical level. If the inventory reaches the critical level, only demands with high penalty costs are filled and demands with low penalty costs are backordered. In this article, we consider a critical level policy for a periodic review inventory system with two demand classes. Because traditional approaches cannot be used to find the optimal parameters of the policy, we use a multidimensional Markov chain to model the inventory system. We use a sample path approach to prove several properties of this inventory system. Although the cost function is not convex, we can build on these properties to develop an optimization approach that finds the optimal solution. We also present some numerical results. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

An advanced dual algorithm with constraint relaxation for all-integer programming

In this article we present an all-integer cutting plane algorithm called the Reduced Advanced Start Algorithm (RASA). The technique incorporates an infeasible advanced start based on the optimal solution to the LP relaxation, and initially discards nonbinding constraints in this solution. We discuss the results of computational testing on a set of standard problems and illustrate the operation of the algorithm with three small examples.     

An integer programming algorithm for portfolio selection with fixed charges

A mean-variance portfolio selection model with limited diversification is formulated in which transaction and management costs are incorporated as the sum of a linear cost and a fixed cost. The problem is a fixed charge integer programming problem solved by hypersurface search using dynamic programming. Fathoming is performed in the forward pass of dynamic programming so that values of the state variable which correspond to infeasible solutions are eliminated from the tables. This logic permits the solution of problems with 20–30 possible investments.     

An efficient algorithm for the location-allocation problem with rectangular regions

The location-allocation problem for existing facilities uniformly distributed over rectangular regions is treated for the case where the rectilinear norm is used. The new facilities are to be located such that the expected total weighted distance is minimized. Properties of the problem are discussed. A branch and bound algorithm is developed for the exact solution of the problem. Computational results are given for different sized problems.     

An optimal recursive method for various inventory replenishment models with increasing demand and shortages

We establish various inventory replenishment policies to solve the problem of determining the timing and number of replenishments. We then analytically compare various models, and identify the best alternative among them based on minimizing total relevant costs. Furthermore, we propose a simple and computationally efficient optimal method in a recursive fashion, and provide two examples for illustration. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 791–806, 1997     

An asymptotically optimal inspection policy

An inspection model in life testing situations is discussed. The system under study is assumed to consist on n independent components all of which fail independently in an exponential fashion. Failures can be discovered only through inspection. The experimenter is assumed to lack the knowledge of the parameter of the exponential distribution. A stochastic sequential inspection policy is suggested which uses the data collected through experimentation to estimate the unknown parameter. It is shown that this policy is asymptotically optimal. Some numerical demonstrations are included.     

An algorithm for the solution of a location problem with metric constraints

In many location problems, the solution is constrained to lie within a closed set. In this paper, optimal solutions to a special type of constrained location problem are characterized. In particular, the location problem with the solution constrained to be within a maximum distance of each demand point is considered, and an algorithm for its solution is developed and discussed.     

An iterative algorithm for the multifacility minimax location problem with euclidean distances

An iterative solution method is presented for solving the multifacility location problem with Euclidean distances under the minimax criterion. The iterative procedure is based on the transformation of the multifacility minimax problem into a sequence of squared Euclidean minisum problems which have analytical solutions. Computational experience with the new method is also presented.     

一种单平台的无源被动定位算法

提出了一种对匀速扫描雷达的单站被动定位方法 ,主要论述了该定位方法的数学模型 ,仿真分析结果表明该算法有较好的定位精度     

Single‐warehouse multi‐retailer inventory systems with full truckload shipments

We consider a multi‐stage inventory system composed of a single warehouse that receives a single product from a single supplier and replenishes the inventory of n retailers through direct shipments. Fixed costs are incurred for each truck dispatched and all trucks have the same capacity limit. Costs are stationary, or more generally monotone as in Lippman (Management Sci 16, 1969, 118–138). Demands for the n retailers over a planning horizon of T periods are given. The objective is to find the shipment quantities over the planning horizon to satisfy all demands at minimum system‐wide inventory and transportation costs without backlogging. Using the structural properties of optimal solutions, we develop (1) an O(T²) algorithm for the single‐stage dynamic lot sizing problem; (2) an O(T³) algorithm for the case of a single‐warehouse single‐retailer system; and (3) a nested shortest‐path algorithm for the single‐warehouse multi‐retailer problem that runs in polynomial time for a given number of retailers. To overcome the computational burden when the number of retailers is large, we propose aggregated and disaggregated Lagrangian decomposition methods that make use of the structural properties and the efficient single‐stage algorithm. Computational experiments show the effectiveness of these algorithms and the gains associated with coordinated versus decentralized systems. Finally, we show that the decentralized solution is asymptotically optimal. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

An adaptive forecasting algorithm and inventory policy for products with short life cycles

Products with short life cycles are becoming increasingly common in many industries, such as the personal computer (PC) and mobile phone industries. Traditional forecasting methods and inventory policies can be inappropriate for forecasting demand and managing inventory for a product with a short life cycle because they usually do not take into account the characteristics of the product life cycle. This can result in inaccurate forecasts, high inventory cost, and low service levels. Besides, many forecasting methods require a significant demand history, which is available only after the product has been sold for some time. In this paper, we present an adaptive forecasting algorithm with two characteristics. First, it uses structural knowledge on the product life cycle to model the demand. Second, it combines knowledge on the demand that is available prior to the launch of the product with actual demand data that become available after the introduction of the product to generate and update demand forecasts. Based on the forecasting algorithm, we develop an optimal inventory policy. Since the optimal inventory policy is computationally expensive, we propose three heuristics and show in a numerical study that one of the heuristics generates near‐optimal solutions. The evaluation of our approach is based on demand data from a leading PC manufacturer in the United States, where the forecasting algorithm has been implemented. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

An absolute approximation algorithm for scheduling unrelated machines

Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 ? 1/m)p_max, p} is presented, where p_max is the largest job processing time and p is the mth element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p_max. The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm²) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

An approximative algorithm for the fixed charge problem

This paper describes an approximate solution method for solving the fixed charge problem. This heuristic approach is applied to a set of test problems to explore the margin of error. The results indicate that the proposed fixed charge simplex algorithm is capable of finding optimal or near optimal solutions to moderate sized fixed charge problems. In the absence of an exact method, this heuristic should prove useful in solving this fundamental nonlinear programming problem.     

一种面向多核处理器的高效并行PCA-SIFT算法

提出一种面向多核处理器的并行PCA-SIFT算法,采用数据级并行方法实现并行的特征提取和特征点匹配,将计算任务分配到各个DSP核并行处理,充分开发多核处理器的多级并行性.实验结果表明,并行PCA-SIFT算法对各种不同图像形变的图像具有良好的适应性,具有接近串行PCA-SIFT算法的图像匹配能力,平均加速比达3.12.     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

An improved algorithm for the dynamic lot-sizing problem with learning effect in setups

The dynamic lot-sizing problem with learning in setups is a variation of the Wagner-Whitin lot-sizing problem where the setup costs are a concave, nondecreasing function of the cumulative number of setups. This problem has been a subject of some recent research. We extend the previously studied model to include nonstationary production costs and present an O(T²) algorithm to solve this problem. The worst-case complexity of our algorithm improves the worst-case behavior of the algorithms presently known in the literature. © 1993 John Wiley & Sons, Inc.