On efficiency of multistage channel with bargaining over wholesale prices

This article considers a multistage channel with deterministic price‐sensitive demand. Two systems for pricing decisions, that is, the bargaining system and the leader‐follower system, are compared. We characterize the necessary and sufficient conditions on the power structure, under which the solution of the bargaining system Pareto dominates that of the leader‐follower system. Also, under such conditions, we give a tight upper bound of channel efficiency of the bargaining system, which converges to 100% channel efficiency as the number of stages increases to infinity. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 449–459, 2016     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

An exact method for finding shortest routes on a sphere,avoiding obstacles

On the surface of a sphere, we take as inputs two points, neither of them contained in any of a number of spherical polygon obstacles, and quickly find the shortest route connecting these two points while avoiding any obstacle. The WetRoute method presented here has been adopted by the US Navy for several applications. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 374–385, 2016     

D-S证据理论应用中的一种验证方法

D-S证据理论是一种比概率论确定性弱的不确定性理论,它能将"不知道"和"不确定"两个认知学上的主要概念区别开来,在多传感器数据融合中具有广泛的应用前景.D-S证据理论在实际应用中却存在一个困难,当目标的个数较多时,需要计算的项数太多,容易造成漏项,引起计算错误.提出了一种确定计算项数的算法,作为验证计算结果的必要条件,并通过图解的方法找出需要计算的项.     

Doubly Stochastic Sequential Assignment Problem

This article introduces the Doubly Stochastic Sequential Assignment Problem (DSSAP), an extension of the Sequential Stochastic Assignment Problem (SSAP), where sequentially arriving tasks are assigned to workers with random success rates. A given number of tasks arrive sequentially, each with a random value coming from a known distribution. On a task arrival, it must be assigned to one of the available workers, each with a random success rate coming from a known distribution. Optimal assignment policies are proposed for DSSAP under various assumptions on the random success rates. The optimal assignment algorithm for the general case of DSSAP, where workers have distinct success rate distribution, has an exponential running time. An approximation algorithm that achieves a fraction of the maximum total expected reward in a polynomial time is proposed. The results are illustrated by several numerical experiments. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 124–137, 2016     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

A characterization of optimal base‐stock levels for a multistage serial supply chain

In this article, we present a multistage model to optimize inventory control decisions under stochastic demand and continuous review. We first formulate the general problem for continuous stages and use a decomposition solution approach: since it is never optimal to let orders cross, the general problem can be broken into a set of single‐unit subproblems that can be solved in a sequential fashion. These subproblems are optimal control problems for which a differential equation must be solved. This can be done easily by recursively identifying coefficients and performing a line search. The methodology is then extended to a discrete number of stages and allows us to compute the optimal solution in an efficient manner, with a competitive complexity. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 32–46, 2016     

A mutual primal-dual linear programming algorithm

A new primal-dual linear programming algorithm is exhibited. A proof is given that optimal solutions to both primal and dual problems (when such solutions exist) are found in a finite number of steps by this algorithm. A numerical example is included to illustrate the method.     

Note: A geometrical method of solving certain games

One of the diagrammatic methods for solving two-person 2 × n matrix games can be extended to solve m × n games where each column of the matrix is a concave function of the row number. This gives a simple proof of a theorem of Benjamin and Goldman that such games have solutions involving no more than two consecutive strategies for the row player, and no more than two strategies for the column player. Two extensions are discussed. © 1994 John Wiley & Sons, Inc.     

Capacity expansion and cost efficiency improvement in the warehouse problem

The warehouse problem with deterministic production cost, selling prices, and demand was introduced in the 1950s and there is a renewed interest recently due to its applications in energy storage and arbitrage. In this paper, we consider two extensions of the warehouse problem and develop efficient computational algorithms for finding their optimal solutions. First, we consider a model where the firm can invest in capacity expansion projects for the warehouse while simultaneously making production and sales decisions in each period. We show that this problem can be solved with a computational complexity that is linear in the product of the length of the planning horizon and the number of capacity expansion projects. We then consider a problem in which the firm can invest to improve production cost efficiency while simultaneously making production and sales decisions in each period. The resulting optimization problem is non‐convex with integer decision variables. We show that, under some mild conditions on the cost data, the problem can be solved in linear computational time. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 367–373, 2016     

纯引力轨道验证质量辐射计效应与气体阻尼耦合模型的数值分析

辐射计效应和气体阻尼是纯引力轨道验证质量的重要干扰力,是影响纯引力轨道构造水平的重要因素.在纯引力轨道飞行器中,这两种力分别描述了由腔体中温度梯度和验证质量相对运动引起的气体分子作用,两者从不同角度描述了气体分子作用力,均是气体分子作用力的一部分,而两者的耦合模型则可以反映验证质量受到的气体分子作用力总和.针对耦合模型形式复杂的特点,本文以内编队系统为例,利用数值方法分析了耦合模型中的影响因素,这些因素包括内卫星相对运动速度、内卫星半径、外卫星腔体半径、腔体平均温度、腔体温差和腔体平均压力等.对大量计算结果进行了数据拟合,给出了内卫星气体分子作用力与各物理参数关系的拟合公式,和原始计算结果相比,拟合误差在20％以内.     

Extensions and reductions in the von neumann model of an expanding economy

This paper introduces an extension of the v. Neumann model of an expanding economy. In addition to the conventional nonnegative input and output matrices A₁, B₁ representing technology, two matrices A₂, B₂ represent socio-political evaluations and show that there exist solutions to the 4-matrix model. The proof is based on an extension of a constructive proof given by O. Morgenstern and G. L. Thompson. It is shown that this proof is valid only under an additional assumption. The transformation of v. Neumann models (taking consumption into account) into 1 or 2 games is shown and adds an additional condition to M. Morishima's model to guarantee a solution. The equivalence of the v. Neumann model to a maximization problem under a (efficiency) constraint is presented. It is shown that E. Malinvaud's maximality and efficiency criterion - if based on the same assumptions (model) - are equivalent and specify the assumptions which will make the MT-model efficient. The economic evaluation is considered to be of utmost importance.     

Resequencing with parallel queues to minimize the maximum number of items in the overflow area

This article treats an elementary optimization problem, where an inbound stream of successive items is to be resequenced with the help of multiple parallel queues in order to restore an intended target sequence. Whenever early items block the one item to be currently released into the target sequence, they are withdrawn from their queue and intermediately stored in an overflow area until their actual release is reached. We aim to minimize the maximum number of items simultaneously stored in the overflow area during the complete resequencing process. We met this problem in industry practice at a large German automobile producer, who has to resequence containers with car seats prior to the assembly process. We formalize the resulting resequencing problem and provide suited exact and heuristic solution algorithms. In our computational study, we also address managerial aspects such as how to properly avoid the negative effects of sequence alterations. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 401–415, 2016     

The distribution of recoverable inventory items from a repair center when the number of consumption centers is large

This paper considers real-time decision rules for an inventory system where items are repaired than “used up.” The problem is to decide which user in the system has the greatest need for the newly available inventory items coming out of repair. The main result shows that two published approahes, the Transportation Time Look Ahead policy and METRIC, are optimal when the number of users gets large. A useful byproduct of the proof is a lower bound on the average backorder rate for a repair-inventory system of any size.     

Minimal LST representations of MAP(n)s: Moment fittings and queueing approximations

A Markovian arrival process of order n, MAP(n), is typically described by two n × n transition rate matrices in terms of rate parameters. While it is straightforward and intuitive, the Markovian representation is redundant since the minimal number of parameters is n² for non‐redundant MAP(n). It is well known that the redundancy complicates exact moment fittings. In this article, we present a minimal and unique Laplace‐Stieltjes transform (LST) representations for MAP(n)s. Even though the LST coefficients vector itself is not a minimal representation, we show that the joint LST of stationary intervals can be represented with the minimum number of parameters. We also propose another minimal representation for MAP(3)s based on coefficients of the characteristic polynomial equations of the two transition rate matrices. An exact moment fitting procedure is presented for MAP(3)s based on two proposed minimal representations. We also discuss how MAP(3)/G/1 departure process can be approximated as a MAP(3). A simple tandem queueing network example is presented to show that the MAP(3) performs better than the MAP(2) in queueing approximations especially under moderate traffic intensities. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 549–561, 2016     

考虑仿真可信度的舰炮虚拟校射

为利用仿真模型在有限校射样本的条件下对校射补偿量进行合理估计,对考虑仿真可信度的舰炮虚拟校射方法进行了研究。对自适应加权贝叶斯估计方法进行了研究,一方面对仿真先验可信度的计算方法进行了分析,另一方面对考虑先验可信度的自适应加权贝叶斯估计算法进行了研究。在此基础上,结合舰炮虚拟校射的原理和需求,建立了舰炮虚拟校射诸元误差自适应加权贝叶斯估计模型。仿真验证表明:自适应加权贝叶斯估计方法能够利用试验数据对仿真模型的可信度进行有效验证并进一步实现对目标分布的有效估计;所设计的校射方法能够综合利用仿真模型和校射样本的优势,实现对诸元误差的合理估计,达到有效提高校射精度的目的。     

A note on first passage times in birth and death and nonnegative diffusion processes

Consider a birth and death process starting in state 0. Keilson has shown by analytical arguments that the time of first passage into state n has an increasing failure rate (IFR) distribution. We present a probabilistic proof for this. In addition, our proof shows that for a nonnegative diffusion process, the first passage time from state 0 to any state x is IFR.     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Analysis of the greedy approach in problems of maximum k-coverage

In this paper, we consider a general covering problem in which k subsets are to be selected such that their union covers as large a weight of objects from a universal set of elements as possible. Each subset selected must satisfy some structural constraints. We analyze the quality of a k-stage covering algorithm that relies, at each stage, on greedily selecting a subset that gives maximum improvement in terms of overall coverage. We show that such greedily constructed solutions are guaranteed to be within a factor of 1 − 1/e of the optimal solution. In some cases, selecting a best solution at each stage may itself be difficult; we show that if a β-approximate best solution is chosen at each stage, then the overall solution constructed is guaranteed to be within a factor of 1 − 1/e^β of the optimal. Our results also yield a simple proof that the number of subsets used by the greedy approach to achieve entire coverage of the universal set is within a logarithmic factor of the optimal number of subsets. Examples of problems that fall into the family of general covering problems considered, and for which the algorithmic results apply, are discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 615–627, 1998     

Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017