Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Exact analysis of (R,s, S) inventory control systems with lost sales and zero lead time

We study an (R, s, S) inventory control policy with stochastic demand, lost sales, zero lead‐time and a target service level to be satisfied. The system is modeled as a discrete time Markov chain for which we present a novel approach to derive exact closed‐form solutions for the limiting distribution of the on‐hand inventory level at the end of a review period, given the reorder level (s) and order‐up‐to level (S). We then establish a relationship between the limiting distributions for adjacent values of the reorder point that is used in an efficient recursive algorithm to determine the optimal parameter values of the (R, s, S) replenishment policy. The algorithm is easy to implement and entails less effort than solving the steady‐state equations for the corresponding Markov model. Point‐of‐use hospital inventory systems share the essential characteristics of the inventory system we model, and a case study using real data from such a system shows that with our approach, optimal policies with significant savings in inventory management effort are easily obtained for a large family of items.     

中立型泛函微分方程的周期解

综合利用D算子的性质及Horn不动点定理[8],研究了有限时滞中立型泛函微分方程的周期解的存在性问题,证明了解的一致最终有界性蕴含周期解的存在性,从而推广了著名的Yoshizawa周期解定理[3],同时推广了[1]和[2]的主要结果.     

The enumeration of all efficient solutions for a linear multiple-objective transportation problem

An algorithm is presented by which the set of all efficient solutions for a linear multiple-objective transportation problem can be enumerated. First the algorithm determines an initial efficient basic solution. In a second step all efficient basic solutions are enumerated. Finally, the set of all efficient solutions is constructed as a union of a minimal number of convex sets of efficient solutions. The algorithm is illustrated by a numerical example.     

Generating Pareto‐optimal boundary points in multiparty negotiations using constraint proposal method

In this paper a constraint proposal method is developed for computing Pareto‐optimal solutions in multiparty negotiations over continuous issues. Constraint proposal methods have been previously studied in a case where the decision set is unconstrained. Here we extend the method to situations with a constrained decision set. In the method the computation of the Pareto‐optimal solutions is decentralized so that the DMs do not have to know each others' value functions. During the procedure they have to indicate their optimal solutions on different sets of linear constraints. When the optimal solutions coincide, the common optimum is a candidate for a Pareto‐optimal point. The constraint proposal method can be used to generate either one Pareto‐optimal solution dominating the status quo solution or several Pareto‐optimal solutions. In latter case a distributive negotiation among the efficient points can be carried out afterwards. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 210–225, 2001     

Optimizing natural gas pipeline transmission with nonuniform elevation: A new initialization approach

In this paper, we develop an iterative piecewise linear approximation approach with a novel initialization method to solve natural gas pipeline transmission problems with the nonuniform network elevation. Previous approaches, such as energy minimization methods, cannot be applied to solve problems with the nonuniform network elevation because they exclude pressure range constraints, and thus provide solutions far from optimum. We propose a new initialization model that considers pressure range constraints and improves the optimality of the solutions and the computational efficiency. Furthermore, we extend the energy minimization methods and provide the necessary conditions under which the extended methods operate in networks with the nonuniform elevation. We test the performances of the methods with previously reported pipeline networks from the literature, with the open data set GasLib, and with our industrial collaborator. The initialization approach is shown to be more efficient than the method with fixed initial breakpoints. The newly proposed initialization approach generates solutions with a higher accuracy than the extended energy minimization methods, especially in large‐size networks. The proposed method has been applied to natural gas transmission planning by the China National Petroleum Corporation and has brought a direct profit increase of 330 million U.S. dollars in 2015‐2017.     

Bounded flexibility in days‐on and days‐off scheduling

This article presents a flexible days‐on and days‐off scheduling problem and develops an exact branch and price (B&P) algorithm to find solutions. The main objective is to minimize the size of the total workforce required to cover time‐varying demand over a planning horizon that may extend up to 12 weeks. A new aspect of the problem is the general restriction that the number of consecutive days on and the number of consecutive days off must each fall within a predefined range. Moreover, the total assignment of working days in the planning horizon cannot exceed some maximum value. In the B&P framework, the master problem is stated as a set covering‐type problem whose columns are generated iteratively by solving one of three different subproblems. The first is an implicit model, the second is a resource constrained shortest path problem, and the third is a dynamic program. Computational experiments using both real‐word and randomly generated data show that workforce reductions up to 66% are possible with highly flexible days‐on and days‐off patterns. When evaluating the performance of the three subproblems, it was found that each yielded equivalent solutions but the dynamic program proved to be significantly more efficient. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 678–701, 2013     

Bicriteria multiresource generalized assignment problem

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621–636, 2014     

The many-product cargo loading problem

An algorithm, based upon dynamic programming, is developed for a class of fixed-cost cargo loading problems. The problems can be formulated as integer programming problems, but cannot be efficiently solved as such because of computational difficulties. The algorithm developed has proved to be very efficient in an actual operations research study involving over 500 different cargo items, more than 40 possible stops and several types of transportation vehicles. A numerical illustration is provided.     

改进的前向信息修补算法及其应用

前向信息修补算法可以对离散动态贝叶斯网络的缺失数据进行预测,该算法只适用于所有观测节点是相互独立的网络,却不能处理观测节点有依赖关系网络的缺失数据。针对该算法的这一缺陷,提出了改进的前向信息修补算法,在分析离散动态贝叶斯网络的缺失数据具有二种基本形式的基础上,推导出了每种形式的相应预测公式。继而构建了用于识别威胁源离散动态贝叶斯网络的模型。仿真实验验证了改进的前向信息修补算法的有效性。     

NORX算法中非线性组件的移位参数选取准则研究

NORX算法是进入凯撒竞赛第三轮的15个认证加密候选算法之一,该算法的唯一非线性组件由异或、与和移位操作组成。从非线性逼近和循环分析两个密码学性质研究移位参数的选取准则,证明了可变移位函数的非线性逼近概率为三值函数,并得到了移位参数取1时具有最佳的非线性逼近性质;给出了可变移位函数的循环概率表达式,并证明了对于任意非零的移位参数其最大循环概率均相同。由上述分析结果可知,NORX算法中非线性组件的移位参数取1时达到了最佳的非线性逼近和循环性质。该结果可应用于NORX算法的安全性分析中,同时也能为设计类似算法提供理论指导。     

一类时滞微分方程正周期解的存在性

讨论了一类生物模型正周期解的存在性问题,利用Mawhin延拓定理得到了系统存在正周期解的一个充分条件。而且,当系统为无穷时滞时,结论也是成立的。     

Interval estimation of a global optimum for large combinatorial problems

Consider an “intractable” optimization problem for which no efficient solution technique exists. Given a systematic procedure for generating independent heuristic solutions, we seek to obtain interval estimates for the globally optimal solution using statistical inference. In previous work, accurate point estimates have been derived. Determining interval estimates, however, is a considerably more difficult task. In this paper, we develop straightforward procedures which compute confidence intervals efficiently in order to evaluate heuristic solutions and assess deviations from optimality. The strategy presented is applicable to a host of combinatorial optimization problems. The assumptions of our model, along with computational experience, are discussed.     

单组点堆中子动力学方程的解析解

针对有外加中子源单组点堆中子动力学方程组的快速求解问题,提出了常数变易法和同伦分析方法,通过理论推导获得了单组点堆中子动力学方程组解析解,然后对3种不同刚性情况下的阶跃反应性引入的例子进行了求解和数值分析,验证了所得解析解的正确性。     

火炮火控系统命中解的分布和存在性

定义了火控系统中问题联立方程应满足的“基本假设”,从理论上讨论了在“基本假设”条件下诸命中解的分布特性 ,证明临近的命中解 (如果存在的话 )是唯一的 ,给出了临近解存在的充分必要条件。用一个简单的实例表出不同目标速度下诸命中解分布的实验数据     

An exact network flow formulation for cell‐based evacuation in urban areas

In the literature two common macroscopic evacuation planning approaches exist: The dynamic network flow approach and the Cell–Transmission–Based approach. Both approaches have advantages and disadvantages. Many efficient solution approaches for the dynamic network flow approach exist so that realistic problem instances can be considered. However, the consideration of (more) realistic aspects (eg, density dependent travel times) results in non‐linear model formulations. The Cell‐Transmission‐Based approach on the other hand considers realistic traffic phenomena like shock waves and traffic congestion, but this approach leads to long computational times for realistic problem instances. In this article, we combine the advantages of both approaches: We consider a Cell‐Transmission‐Based Evacuation Planning Model (CTEPM) and present a network flow formulation that is equivalent to the cell‐based model. Thus, the computational costs of the CTEPM are enormously reduced due to the reformulation and the detailed representation of the traffic flow dynamics is maintained. We investigate the impacts of various evacuation scenario parameters on the evacuation performance and on the computational times in a computational study including 90 realistic instances.     

人车目标的自动识别

对单人、人群、机动车三类目标的特征进行了分析,找出了它们之间的不同之处,提出了对这三类目标进行分类识别的方法,并经现场检验,证明这种方法是有效的。     

A heuristic for capacity expansion planning with multiple facility types

A capacity expansion model with multiple facility types is examined, where different facility types represent different quality levels. Applications for the model can be found in communications networks and production facilities. The model assumes a finite number of discrete time periods. The facilities are expanded over time. Capacity of a high-quality facility can be converted to satisfy demand for a lower-quality facility. The costs considered include capacity expansion costs and excess capacity holding costs. All cost functions are nondecreasing and concave. An algorithm that finds optimal expansion policies requires extensive computations and is practical only for small scale problems. Here, we develop a heuristic that employs so-called distributed expansion policies. It also attempts to decompose the problem into several smaller problems solved independently. The heuristic is computationally efficient. Further, it has consistently found near-optimal solutions.     

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     

An experimental comparison of solution algorithms for the single-machine tardiness problem

A basic problem in scheduling involves the sequencing of a set of independent tasks at a single facility with the objective of minimizing mean tardiness. Although the problem is relatively simple, the determination of an optimal sequence remains a challenging combinatorial problem. A number of algorithms have been developed for finding solutions, and this paper reports a comparative evaluation of these procedures. Computer programs for five separate algorithms were written and all were run on a data base designed to highlight computational differences. Optimizing algorithms developed by Emmons and by Srinivasan appeared to be particularly efficient in the comparative study.