Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Approximate dynamic programming methods for an inventory allocation problem under uncertainty

We propose two approximate dynamic programming methods to optimize the distribution operations of a company manufacturing a certain product at multiple production plants and shipping it to different customer locations for sale. We begin by formulating the problem as a dynamic program. Our first approximate dynamic programming method uses a linear approximation of the value function and computes the parameters of this approximation by using the linear programming representation of the dynamic program. Our second method relaxes the constraints that link the decisions for different production plants. Consequently, the dynamic program decomposes by the production plants. Computational experiments show that the proposed methods are computationally attractive, and in particular, the second method performs significantly better than standard benchmarks. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options

This article generalizes the dynamic and stochastic knapsack problem by allowing the decision‐maker to postpone the accept/reject decision for an item and maintain a queue of waiting items to be considered later. Postponed decisions are penalized with delay costs, while idle capacity incurs a holding cost. This generalization addresses applications where requests of scarce resources can be delayed, for example, dispatching in logistics and allocation of funding to investments. We model the problem as a Markov decision process and analyze it through dynamic programming. We show that the optimal policy with homogeneous‐sized items possesses a bithreshold structure, despite the high dimensionality of the decision space. Finally, the value (or price) of postponement is illustrated through numerical examples. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 267–292, 2015     

Designing and pricing menus of extended warranty contracts

Extended warranties provide “piece of mind” to a consumer in that product failures which occur after the base warranty expires are rectified at little or no cost. They also provide an additional source of revenue for manufacturers or third‐party providers, such as retailers or insurance providers, and help cultivate consumer loyalty. In this article, we analyze a number of extended warranty contracts which differ in design, including restrictions on deferrals and renewals. With the use of dynamic programming, we compute the optimal strategy for a consumer with perfect information and determine the optimal pricing policy for the provider given the consumer's risk characterization. We also provide insight into when different contracts should be issued. Finally, we illustrate how profits can be dramatically increased by offering menus of warranty contracts, as opposed to stand alone contracts, with the use of integer programming. Surprisingly, risk‐taking consumers provide the greatest benefit to offering menus. These insights can help a company develop a comprehensive warranty planning strategy for given products or product lines. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two‐machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnsos order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP‐hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Modeling the operation of multireservoir systems using decomposition and stochastic dynamic programming

Stochastic dynamic programming models are attractive for multireservoir control problems because they allow non‐linear features to be incorporated and changes in hydrological conditions to be modeled as Markov processes. However, with the exception of the simplest cases, these models are computationally intractable because of the high dimension of the state and action spaces involved. This paper proposes a new method of determining an operating policy for a multireservoir control problem that uses stochastic dynamic programming, but is practical for systems with many reservoirs. Decomposition is first used to reduce the problem to a number of independent subproblems. Each subproblem is formulated as a low‐dimensional stochastic dynamic program and solved to determine the operating policy for one of the reservoirs in the system. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

模糊优选动态规划在稀缺军事资源配置中的应用

在对稀缺军事资源配置问题进行数学描述的基础上,建立起评价指标相对优属度计算模型,实现了局部优选。在此基础上,通过分配目标综合评价模型实现了对局部优选数据的综合处理,最后建立资源分配的动态规划模型实现了对方案的优选。最后通过实例演示了解决该类问题的具体方法和步骤,对部队建设具有一定的参考和应用价值。     

Optimal patrol to uncover threats in time when detection is imperfect

Consider a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes. An attack takes a random amount of time to complete. The patroller takes one time unit to move to and inspect an adjacent node, and will detect an ongoing attack with some probability. If an attack completes before it is detected, a cost is incurred. The attack time distribution, the cost due to a successful attack, and the detection probability all depend on the attack node. The patroller seeks a patrol policy that minimizes the expected cost incurred when, and if, an attack eventually happens. We consider two cases. A random attacker chooses where to attack according to predetermined probabilities, while a strategic attacker chooses where to attack to incur the maximal expected cost. In each case, computing the optimal solution, although possible, quickly becomes intractable for problems of practical sizes. Our main contribution is to develop efficient index policies—based on Lagrangian relaxation methodology, and also on approximate dynamic programming—which typically achieve within 1% of optimality with computation time orders of magnitude less than what is required to compute the optimal policy for problems of practical sizes. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 557–576, 2014     

Scheduling a maintenance activity on parallel identical machines

We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Scheduling with centralized and decentralized batching policies in concurrent open shops

This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The batching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo‐polynomial time algorithms for some problems that are NP‐hard in the ordinary sense. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17–27, 2011     

随机动态规划的混合算法研究

针对随机条件下动态规划模型的主要特点,运用智能算法混合编程理论,设计了一种探索多阶段决策问题的智能混合算法.该算法首先将问题转化成一族同类型的一步决策子问题,然后利用随机模拟和遗传算法,依据训练样本形成的训练神经元网络,在单步决策中寻求最优策略和最优目标值,逐个求解,再据初始状态逆序求出最优策略序列和最优目标值.仿真结果表明,该算法具有一定的通用性,初始设计点可以随机产生,其计算精度不因函数的非线性强弱而受影响,对目标和约束的限制较少,可应用于多种形式的随机多阶段决策优化问题,较好地满足了随机动态规划模型求解和优化的要求.     

Optimal path finding in direction,location, and time dependent environments

This article examines optimal path finding problems where cost function and constraints are direction, location, and time dependent. Recent advancements in sensor and data‐processing technology facilitate the collection of detailed real‐time information about the environment surrounding a ground vehicle, an airplane, or a naval vessel. We present a navigation model that makes use of such information. We relax a number of assumptions from existing literature on path‐finding problems and create an accurate, yet tractable, model suitable for implementation for a large class of problems. We present a dynamic programming model which integrates our earlier results for direction‐dependent, time and space homogeneous environment, and consequently, improves its accuracy, efficiency, and run‐time. The proposed path finding model also addresses limited information about the surrounding environment, control‐feasibility of the considered paths, such as sharpest feasible turns a vehicle can make, and computational demands of a time‐dependent environment. To demonstrate the applicability and performance of our path‐finding algorithm, computational experiments for a short‐range ship routing in dynamic wave‐field problem are presented. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

基于可能性决策的敌对危机行动预测与仿真

可能性决策能较好地应对军事领域常常出现的概率难以获得,或者强调“出奇制胜”而有意规避概率风险的情形,是解决知识不完备情况下敌对行动预测的有力手段。从可能性理论基本公理体系出发,结合动态规划方法,提出并证明可能性决策的最优化定理,给出多步条件下可能性决策的实现算法,结合危机条件下敌对行动预测的范例和仿真分析,与传统概率风险决策进行比较,体现可能性决策的优越性,为该方法的推广应用创造条件。     

Scheduling maintenance and semiresumable jobs on a single machine

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999     

动态规划在消防增援调度中的应用

由于各消防中队一般规模较小，对于较大规模的火灾需要多个消防队共同救护，此时若能够实现增援调度的最优化可以提高这些同时出现的火灾被全部扑灭的概率。利用多阶段动态规划对增援调度进行了研究，并分析了具体案例。通过分析得出此方法有助于改善消防资源分配状况，以实现最大程度地减小经济损失。     

Integrated capacity,demand, and production planning with subcontracting and overtime options

Models for integrated production and demand planning decisions can serve to improve a producer's ability to effectively match demand requirements with production capabilities. In contexts with price‐sensitive demands, economies of scale in production, and multiple capacity options, such integrated planning problems can quickly become complex. To address these complexities, this paper provides profit‐maximizing production planning models for determining optimal demand and internal production capacity levels under price‐sensitive deterministic demands, with subcontracting and overtime options. The models determine a producer's optimal price, production, inventory, subcontracting, overtime, and internal capacity levels, while accounting for production economies of scale and capacity costs through concave cost functions. We use polyhedral properties and dynamic programming techniques to provide polynomial‐time solution approaches for obtaining an optimal solution for this class of problems when the internal capacity level is time‐invariant. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

基于动态规划的猎雷具识别路径优化算法

路径长度、海流方向给猎雷具航渡、操控带来的时间消耗,是影响目标识别效率的主要因素。单纯运用动态规划算法只能解决猎雷具最短识别路径的问题,而无法顾全猎雷具在操控方面的时间损耗,从而在提升作战效率上得不偿失。本文基于动态规划算法,优化了识别路径的解算模型,并在模型解算前,提出了目标位置的预处理条件,简化了模型的解算步骤;在模型解算后,提出了识别路径的修正方法,完善了模型的解算结果。     

Robust shortest path planning and semicontractive dynamic programming

In this article, we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit‐evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra‐like algorithm for problems with nonnegative arc lengths.© 2016 Wiley Periodicals, Inc. Naval Research Logistics 66:15–37, 2019     

一种基于0-1整数规划的全局数据分布优化方法

数据分布是影响并行程序在分布主存多处理机上执行性能的重要因素.针对分布主存多处理机中的数据分布问题,提出了一种基于0-1整数规划、利用数据变换技术进行有效数据分布的方法.该方法通过数据变换技术改变数据的存储布局,以使得数据能被有效地分布,并且该方法还利用数据分布图描述程序被并行的情况及其所含数组被访问的情况,并将全局数据分布优化问题转换为求解数据分布图中最优路径的问题,从而可用0-1整数规划求解最优路径问题.该方法能对多个嵌套循环中具有仿射数组下标的任意维数组进行有效的数据分布,并且也能使嵌套循环的并行度尽可能地大.另外,该方法也考虑了偏移常量的对准问题,从而能使数据通信量尽量地小.实验结果验证了该方法的有效性.