Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.     

Optimal resource allocation and redistribution strategy in military conflicts with Lanchester square law attrition

We address the problem of optimal decision‐making in conflicts based on Lanchester square law attrition model where a defending force needs to be partitioned optimally, and allocated to two different attacking forces of differing strengths and capabilities. We consider a resource allocation scheme called the Time Zero Allocation with Redistribution (TZAR) strategy, where allocation is followed by redistribution of defending forces, on the occurrence of certain decisive events. Unlike previous work on Lanchester attrition model based tactical decision‐making, which propose time sequential tactics through an optimal control approach, the present article focuses on obtaining simpler resource allocation tactics based on a static optimization framework, and demonstrates that the results obtained are similar to those obtained by the more complex dynamic optimal control solution. Complete solution for this strategy is obtained for optimal partitioning of resources of the defending forces. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Optimal switchover times between two activities utilizing the same resource

The “gold‐mining” decision problem is concerned with the efficient utilization of a delicate mining equipment working in a number of different mines. Richard Bellman was the first to consider this type of a problem. The solution found by Bellman for the finite‐horizon, continuous‐time version of the problem with two mines is not overly realistic since he assumed that fractional parts of the same mining equipment could be used in different mines and this fraction could change instantaneously. In this paper, we provide some extensions to this model in order to produce more operational and realistic solutions. Our first model is concerned with developing an operational policy where the equipment may be switched from one mine to the other at most once during a finite horizon. In the next extension we incorporate a cost component in the objective function and assume that the horizon length is not fixed but it is the second decision variable. Structural properties of the optimal solutions are obtained using nonlinear programming. Each model and its solution is illustrated with a numerical example. The models developed here may have potential applications in other areas including production of items requiring the same machine or choosing a sequence of activities requiring the same resource. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 186–203, 2002; DOI 10.1002/nav.10008     

不确定失效阈值影响下考虑设备剩余寿命预测信息的最优替换策略

为了进一步提升设备维修决策的科学性,通过建立综合设备剩余寿命预测数据与不确定失效阈值的最优维修决策模型,实现了不可维修设备的最优替换策略.构建基于非线性Wiener过程的设备性能退化模型,并采用极大似然法估计退化模型参数;提出一种基于期望最大(Expectation Maximization,EM)算法的不确定失效阈值...     

Transportation problems with aggregated destinations when demands are uncertain

Transportation problems with uncertain demands are useful applied models themselves, and also they represent in a formal way the problem of estimating demands for use in deterministic models. We consider the effects of using a small, aggregate model of this type in place of a larger, more detailed one. Formulation of the aggregate objective function turns out to depend on how one chooses to use (disaggregate) the solution; several alternative methods are examined. Bounds are derived on the error induced by the approximation, thus facilitating comparison of alternative aggregations. We also consider the problem of estimating demands for an aggregate-level deterministic problem. In a specific sense, it is often not the case (as one might expect) that such aggregate demands are easier to estimate than the detailed demands. This is because aggregation and centralization are not the same thing.     

Warranty reserves for nonstationary sales processes

Estimation of warranty costs, in the event of product failure within the warranty period, is of importance to the manufacturer. Costs associated with replacement or repair of the product are usually drawn from a warranty reserve fund created by the manufacturer. Considering a stochastic sales process, first and second moments (and thereby the variance) are derived for the manufacturer's total discounted warranty cost of a single sale for single‐component items under four different warranty policies from a manufacturer's point of view. These servicing strategies represent a renewable free‐replacement, nonrenewable free‐replacement, renewable pro‐rata, and a nonrenewable minimal‐repair warranty plans. The results are extended to determine the mean and variance of total discounted warranty costs for the total sales over the life cycle of the product. Furthermore, using a normal approximation, warranty reserves necessary for a certain protection level, so that reserves are not completely depleted, are found. Results and their managerial implications are studied through an extensive example. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 499–513, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10023     

Generalized orienteering problem with resource dependent rewards

We introduce a generalized orienteering problem (OP) where, as usual, a vehicle is routed from a prescribed start node, through a directed network, to a prescribed destination node, collecting rewards at each node visited, to maximize the total reward along the path. In our generalization, transit on arcs in the network and reward collection at nodes both consume a variable amount of the same limited resource. We exploit this resource trade‐off through a specialized branch‐and‐bound algorithm that relies on partial path relaxation problems that often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the smuggler search problem (SSP) as an important real‐world application of our generalized OP. Numerical results show that our algorithm applied to the SSP outperforms standard mixed‐integer nonlinear programming solvers for moderate to large problem instances. We demonstrate model enhancements that allow practitioners to represent realistic search planning scenarios by accounting for multiple heterogeneous searchers and complex smuggler motion. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Sequencing independent jobs with a single resource

This paper examines problems of sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. A number of well-known results for single-machine problems which can be applied with little or no modification to the corresponding variable-resource problems are given. However, it is shown that the problem of minimizing the weighted sum of completion times provides an exception.     

Minimax resource allocation problems with ordering constraints

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high-tech industries confronted with large-scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.     

Multiperiod resource allocation with a smoothing objective

We consider a multiperiod resource allocation problem, where a single resource is allocated over a finite planning horizon of T periods. Resource allocated to one period can be used to satisfy demand of that period or of future periods, but backordering of demand is not allowed. The objective is to allocate the resource as smoothly as possible throughout the planning horizon. We present two models: the first assumes that the allocation decision variables are continuous, whereas the second considers only integer allocations. Applications for such models are found, for example, in subassembly production planning for complex products in a multistage production environment. Efficient algorithms are presented to find optimal allocations for these models at an effort of O(T²). Among all optimal policies for each model, these algorithms find the one that carries the least excess resources throughout the planning horizon. © 1995 John Wiley & Sons, Inc.     

Robust shortest path problems with two uncertain multiplicative cost coefficients

We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual‐variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a K ‐shortest paths finding algorithm that may be efficient in many real cases. An application in hazardous materials transportation is discussed, and the solution methods are illustrated by numerical examples. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Optimal selection with alternative information

This article examines the problem of optimally selecting from several unknown rewards when there are given alternative, costly sources of information. The optimal rule, indicating the information to be purchased and the reward to be selected, is specified as a function of the decision maker's prior probabilities regarding the value of each alternative. The rule is surprisingly complex, balancing prior beliefs, the “informativeness” of the relevant information system, and the cost of acquiring information.     

Contracts and coordination: Supply chains with uncertain demand and supply

Considering a supply chain with a supplier subject to yield uncertainty selling to a retailer facing stochastic demand, we find that commonly studied classical coordination contracts fail to coordinate both the supplier's production and the retailer's procurement decisions and achieve efficient performance. First, we study the vendor managed inventory (VMI) partnership. We find that a consignment VMI partnership coupled with a production cost subsidy achieves perfect coordination and a win‐win outcome; it is simple to implement and arbitrarily allocates total channel profit. The production cost subsidy optimally chosen through Nash bargaining analysis depends on the bargaining power of the supplier and the retailer. Further, motivated by the practice that sometimes the retailer and the supplier can arrange a “late order,” we also analyze the behavior of an advance‐purchase discount (APD) contract. We find that an APD with a revenue sharing contract can efficiently coordinate the supply chain as well as achieve flexible profit allocation. Finally, we explore which coordination contract works better for the supplier vs. the retailer. It is interesting to observe that Nash bargaining solutions for the two coordination contracts are equivalent. We further provide recommendations on the applications of these contracts. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 305–319, 2016     

Optimal project compression with due-dated events

The paper proposes an algorithm for the determination of the solution of the activities to be shortened and the amount by which they are to be shortened in order to minimize the total cost of project completion. This cost involves a linear penalty for tardienss of a set of key events and a linear cost of activity compression from its normal duration. The procedure is a generalization of the work of Fulkerson.     

具有良好相关特性的码序列

扩频序列是扩频通信中最重要的部分。本文讨论了三类新型的代数型非线性扩频序列的生成方法,序列特性以及它们在扩频通信中的应用。     

带费用的校对问题的最优停止

本文用逼近的方法给出了校对问题中Poisson模型与二项模型的最优停止规则,并得出了二项模型中参数π具有先验分布β(a,b),a>0,b>0时报酬序列的结构。     

Adaptive competitive decision in repeated play of a matrix game with uncertain entries

This study is concerned with a game model involving repeated play of a matrix game with unknown entries; it is a two-person, zero-sum, infinite game of perfect recall. The entries of the matrix ((pij)) are selected according to a joint probability distribution known by both players and this unknown matrix is played repeatedly. If the pure strategy pair (i, j) is employed on day k, k = 1, 2, …, the maximizing player receives a discounted income of β^{k - 1} X_ij, where β is a constant, 0 ≤ β ? 1, and X_ij assumes the value one with probability p_ij or the value zero with probability 1 - p_ij. After each trial, the players are informed of the triple (i, j, X_ij) and retain this knowledge. The payoff to the maximizing player is the expected total discounted income. It is shown that a solution exists, the value being characterized as the unique solution of a functional equation and optimal strategies consisting of locally optimal play in an auxiliary matrix determined by the past history. A definition of an ?-learning strategy pair is formulated and a theorem obtained exhibiting ?-optimal strategies which are ?-learning. The asymptotic behavior of the value is obtained as the discount tends to one.     

不确定多属性决策的单目标优化方法研究

运用神经网络的非线性映射和遗传算法的寻优特性,建立了不确定多属性决策的单目标优化模型。把属性值区间作为遗传算法染色体的搜索范围,用训练好的神经网络计算适应度。用不同的适应度函数来计算综合属性值区间数的下界和上界,然后对方案进行排序。算例结果表明,该方法是可行的。     

不确定数据流多维建模方法*

由于不确定数据流应用的出现,给传统的精确、静态数据环境下的多维建模带来了巨大挑战。针对不确定数据流动态、无限和不确定等特征,提出了一种不确定数据流多维模型。该模型中引入了不确定对象来描述不确定事实元组,并且通过定义时间维度的层次时间窗口,很好地反映了数据流的动态性和无限性,最后还对此多维不确定数据流模型的基本代数操作和分析代数操作进行了形式化定义,为不确定数据流多维查询与分析提供了理论依据。     

Time-cost tradeoffs in uncertain empirical research projects

This paper explores the relationship between research project cost and expected time to completion under various scheduling strategies; it assumes that many potential technical approaches to the research problem can be identified; and that each approach has a low but finite subjective probability of success. It is shown that under a variety of assumptions, expected time to project completion can be reduced, but that as a result expected project cost rises at an increasing rate. Some cases in which this convex time-cost tradeoff relationship might not hold generally are identified. When the time-cost tradeoff function is convex, the desirability of concurrent as opposed to series scheduling of approaches depends crucially upon the depth of the stream of benefits expected to be realized upon successful project completion. The deeper the benefit stream is, the more desirable concurrent scheduling is.