Dynamic Programming Applied to Ship Fleet Management

A ship fleet management problem is described which concerns the phasing out of a fleet of general cargo ships over a 10-year period with the possibility of premature sale and temporary replacement by charter ships. The objective is to determine a sale and replacement policy which maximizes long term company assets. The problem is tackled by selecting a priority order for sale and determining the optimal rate of replacement by dynamic programming. The method has been programmed and demonstrated good returns and is in current use by a shipping company for a variety of management functions.     

Technical Change and the Optimal Life of Assets

In this paper the effects of technical change on the optimal lives of assets are explored. The generality of the dynamic programming approach to the problem of optimal asset life determination is contrasted with the traditional and highly restrictive "equal life" solution. Some of the possible effects of different forms of technical change on costs are examined and numerical examples of these are solved by dynamic programming to illustrate the consequences for the optimal lives of assets. We hypothesize that the likely effect of technical progress is a lengthening of the optimal replacement cycle.     

Optimal replacement policies for a multicomponent reliability system

This paper studies a discrete time, infinite horizon, dynamic programming model for the replacement of components in a binary coherent system. Under quite general conditions, we show that it is optimal to follow a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. We also discuss the problem of computing such policies.     

The Repair Limit Replacement Method

In the repair limit replacement method when an item requires repair it is first inspected and the repair cost is estimated. Repair is only then undertaken if the estimated cost is less than the "repair limit". Dynamic programming methods are used in this paper as a general approach to the problem of determining optimum repair limits. Two problems are formulated and the cases of finite and infinite planning horizons and discounted and undiscounted costs are discussed. Methods are given for allowing for equipment availability and for the introduction of new types of equipment. An improved general formulation for finite time horizon, stochastic, dynamic programming problems is developed.     

Some Notes on Dynamic Programming and Replacement

In the first section a modification to Howard's policy improvement routine for Markov decision problems is described. The modified routine normally converges the more rapidly to the optimal policy. In the second section a particular form of recurrence relation, which leads to the rapid determination of improved policies is developed for a certain type of dynamic programming problem. The relation is used to show that the repair limit method is the optimal strategy for a basic equipment replacement problem.     

Application of multiobjective dynamic programming to regional natural resource management

The general multiobjective dynamic programming problem is reformulated as a classical dynamic programming problem that then can be solved by regular dynamic programming methods. It is shown that the method of differential dynamic programming is most applicable for solution of this problem, which has a higher dimension state space. A case study, the management of a large natural resource system, is presented and modeled next. Finally, the model is applied to the case of bauxite mining development in Hungary, and numerical results for this case are presented.     

Optimal replacement policy for multicomponent systems: An application to a dairy herd

We consider the problem of finding an optimal replacement policy for a system which has many components. The main difficulty in this problem is that there is an interaction among the items in the system. Thus, the optimal replacement decision for each item depends not only on its state, but also on those of the other items in the systems. This interaction is due to the the fact that the both the stock size and the supply of replacement items is limited. (Instead of an unlimited supply of standard replacement items as is implicitly assumed by most of the replacement models). In our application to dairy herd managenent the problem is further complicated by the fact that this limited supply is not exogenous to the process but is actually generated by it. This is due to the fact that almost all the replacement young cows are home grown. The traits of these young cows have genetic dependence on those of their parents. The dairy herd management problem is actually a special case of the joint replacement and inventory problem, where the groups of cows are the stock of replacement items. At each point of time the decision problem is to find the optimal composition of items from the available population of items. An exact derivation of the optimal replacement policy for such problems is very complicated because the optimal decisions for each period depends on the state of the whole stock, and of all the available replacement components. This leads to a dynamic programming problem with a very large number of state variables which is not feasible to solve numerically due to the great amount of computer time involved.This paper presents a practical method for obtaining an approximate solution for the above described problem. The computational difficulty caused by the tremendously large dimensionality of the state variable is overcome by means of an iterative method which combines simulation and Dynamic Programming approach to compute successive linear approximations of the value function.     

An Example of Problem Embedding in Deterministic Dynamic Programming

A criticism sometimes made of dynamic programming is that in deterministic problems, optimal decisions are calculated which are never needed, as the decisions relate to states which never arise. In this paper we describe how some of these "redundant" calculations have been used, in a certain problem, to derive a working rule of general validity.The problem concerns the installation and replacement of an item of electrical equipment at a large number of sites, to meet a known load at each site which increases exponentially at a known rate.     

Dynamic programming: An interactive approach

An interactive approach to the formulation, modeling, analysis, and solution of discrete deterministic dynamic programming problems is presented. The approach utilizes APL both as the mathematical and the programming language. The interactive capabilities of APL and the simple one-to-one correspondence between the programming and the mathematical language provide an extremely convenient environment for dynamic programming investigations in general and for teaching/learning purposes in particular. The approach is illustrated by a simple model and a numerical example.     

Allocation of dependent divisional resources

A resource allocation problem is considered with resources that are dependent in the sense that an allocation to an activity requires the application of several resources, except for certain activities which are divisional in the sense that an allocation to such an activity requires the use of only a single resource. Return and cost functions are assumed to be continuous and increasing, and the allocation variables are continuous. Conditions are given for the replacement of the continuous problem by an associated problem with discrete variables and a single constraint, and to a given degree of accuracy. The associated problem can be efficiently solved by dynamic programming. Certain divisional resource allocation problems with discrete variables and several linear constraints are shown to be equivalent to a discrete problem with a single constraint. A numerical example is given.     

Multitime Dynamic Programming for Curvilinear Integral Actions

This paper justifies dynamic programming PDEs for optimal control problems with performance criteria involving curvilinear integrals. The main novel feature, relative to the known theory, is that the multitime dynamic programming PDEs are now connected to the multitime maximum principle. For the first time, an interesting and useful connection between the multitime maximum principle and the multitime dynamic programming is given, characterizing the optimal control by means of a PDE system that may be viewed as a multitime feedback law.     

A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

Optimal Replacement Planning by Geometric Programming

Geometric programming (GP) is suggested as an analytical toolfor solving replacement problems with infinite time horizon.The GP solution method is described and explained through theformulation and solution of a typical replacement problem. Asimple example is worked out to demonstrate the pint that GPhas potential as an appropriate mathematical tool for the analysisof certain types of replacement problems.     

New approach for nonseparable dynamic programming problems

A general class of nonseparable dynamic problems is studied in a dynamic programming framework by introducingkth-order separability. The solution approach uses multiobjective dynamic programming as a separation strategy forkth-order separable dynamic problems. The theoretical grounding on which the optimal solution of the original nonseparable dynamic problem can be attained by a noninferior solution of the corresponding multiobjective dynamic programming problem is established. The relationship between the overall optimal Lagrangian multipliers and the stage-optimal Lagrangian multipliers and the relationship between the overall weighting vector and the stage weighting vector are explored, providing the basis for identifying the optimal solution of the original nonseparable problem from among the set of noninferior solutions generated by the envelope approach.This work was supported in part by NSF Grant No. CES-86-17984. The authors appreciate the comments from Dr. V. Chankong and the editorial work by Mrs. V. Benade and Dr. S. Hitchcock.     

When to rebuild or when to adjust scorecards

Data-based scorecards, such as those used in credit scoring, age with time and need to be rebuilt or readjusted. Unlike the huge literature on modelling the replacement and maintenance of equipment there have been hardly any models that deal with this problem for scorecards. This paper identifies an effective way of describing the predictive ability of the scorecard and from this describes a simple model for how its predictive ability will develop. Using a dynamic programming approach one is then able to find when it is optimal to rebuild and when to readjust a scorecard. Failing to readjust or rebuild a scorecard when they aged was one of the defects in credit scoring identified in the investigations into the sub-prime mortgage crisis.     

Non-Serial Dynamic Programming — A Survey

Interest in non-serial dynamic programming is deeply rooted in real life applications. Since the initial efforts in the early 1960's, however, a number of scattered treatments of this interesting field of dynamic programming has emerged. This paper traces the development of non-serial dynamic programming from the basic theory underlying dynamic programming to the latest applications of non-serial dynamic programming. The works of such major contributors as Nemhauser, Wilde, Beightler, Bertele and Brioschi are critically examined and recent relevant computational advances are discussed. The paper is concluded with a few examples of various applications of non-serial dynamic programming together with some crystal ball gazing into future applications. An extensive list of references is also included.     

Dynamic programming and minimum risk paths

This paper addresses the problem of computing minimum risk paths by taking as objective the expected accident cost. The computation is based on a dynamic programming formulation which can be considered an extension of usual dynamic programming models: path costs are recursively computed via functions which are assumed to be monotonic. A large part of the paper is devoted to analyze in detail this formulation and provide some new results. Based on the dynamic programming model a linear programming model is also presented to compute minimum risk paths. This formulation turns out to be useful in solving a biobjective version of the problem, in which also expected travel length is taken into consideration. This leads to define nondominated mixed strategies. Finally it is shown how to extend the basic updating device of dynamic programming in order to enumerate all nondominated paths.     

Optimal investment strategies and risk measures in defined contribution pension schemes

In this paper, we derive a formula for the optimal investment allocation (derived from a dynamic programming approach) in a defined contribution (DC) pension scheme whose fund is invested in n assets. We then analyse the particular case of n=2 (where we consider the presence in the market of a high-risk and a low-risk asset whose returns are correlated) and study the investment allocation and the downside risk faced by the retiring member of the DC scheme, where optimal investment strategies have been adopted. The behaviour of the optimal investment strategy is analysed when changing the disutility function and the correlation between the assets. Three different risk measures are considered in analysing the final net replacement ratios achieved by the member: the probability of failing the target, the mean shortfall and a value at risk (VaR) measure. The replacement ratios encompass the financial and annuitisation risks faced by the retiree. We consider the relationship between the risk aversion of the member and these different risk measures in order to understand better the choices confronting different categories of scheme member. We also consider the sensitivity of the results to the level of the correlation coefficient.     

一类有序样品聚类的动态规划方法

变结构特征的识别在经济计量模型建立中具有重要价值 .本文用动态规划方法讨论了一类社会经济系统模型结构变化点的问题 ,并通过实例进行了验证 .文中引进了线性模型来划分变结构模型 ,并编写出用动态规划方法聚类的计算程序 .大量模拟计算表明该方法实用性强 ,算法简便 ,便于应用 .     

Book review of Orthogonal Systems and Convolution Operators,Operator Theory: Advances and Applications,Robert L. Ellis and Israel Gohberg,Birkhäuser Verlag,Basel-Boston-Berlin 2003, Volume 140. ISBN 3-7643-6929-9.

In this note we investigate a time-discrete stochastic dynamic programming problem with countable state and action spaces. We introduce an approximation procedure for a numerical solution by decomposition of the state and also of the action space. The minimal value functions and the optimal policies of the Markovian Decision .Processes constructed by clustering of both spaces are calculated by dynamic programming. Bounds for the minimal value functions will be obtained and convergence theorems are proved.