Markov decision processes with restricted observations: Finite horizon case

In this article we consider a Markov decision process subject to the constraints that result from some observability restrictions. We assume that the state of the Markov process under consideration is unobservable. The states are grouped so that the group that a state belongs to is observable. So, we want to find an optimal decision rule depending on the observable groups instead of the states. This means that the same decision applies to all the states in the same group. We prove that a deterministic optimal policy exists for the finite horizon. An algorithm is developed to compute policies minimizing the total expected discounted cost over a finite horizon. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 439–456, 1997     

Optimal policies for stochastic clearing systems with time-dependent delay penalties

We study stochastic clearing systems with a discrete-time Markovian input process, and an output mechanism that intermittently and instantaneously clears the system partially or completely. The decision to clear the system depends on both quantities and delays of outstanding inputs. Clearing the system incurs a fixed cost, and outstanding inputs are charged a delay penalty, which is a general increasing function of the quantities and delays of individual inputs. By recording the quantities and delays of outstanding inputs in a sequence, we model the clearing system as a tree-structured Markov decision process over both a finite and infinite horizon. We show that the optimal clearing policies, under realistic conditions, are of the on-off type or the threshold type. Based on the characterization of the optimal policies, we develop efficient algorithms to compute parameters of the optimal policies for such complex clearing systems for the first time. We conduct a numerical analysis on the impact of the nonlinear delay penalty cost function, the comparison of the optimal policy and the classical hybrid policy (ie, quantity and age thresholds), and the impact of the state of the input process. Our experiments demonstrate that (a) the classical linear approximation of the cost function can lead to significant performance differences; (b) the classical hybrid policy may perform poorly (as compared to the optimal policies); and (c) the consideration of the state of the input process makes significant improvement in system performance.     

Optimal reject allowance with constant marginal production efficiency

A job shop must fulfill an order for N good items. Production is conducted in “lots,” and the number of good items in a lot can be accurately determined only after production of that lot is completed. If the number of good items falls short of the outstanding order, the shop must produce further lots, as necessary. Processes with “constant marginal production efficiency” are investigated. The revealed structure allows efficient exact computation of optimal policy. The resulting minimal cost exhibits a consistent (but not universal) pattern whereby higher quality of production is advantageous even at proportionately higher marginal cost.     

A semieconomic method for the determination of optimal lot sizes

The construction of lot sizes usually depends upon factors influencing homogeneity. When these factors are not a function of lot quantity, it is possible to determine an optimal lot size. The optimization process balances the cost of sampling against the expected cost of lot rejection for some specified procurement quantity. The rationale for balancing the two costs is contingent upon the fact that rejection criteria waivers frequently occur when the lot size is large. This concept implies that the lot size should be as small as possible, whereas the cost of sampling drives the lot size up. Hence, trade-offs may be made. The formulation is termed a semieconomic one because it combines a pure economic objective function with a pure statistical constraint. This constraint is necessary because the nature of the items under study dictates that the cost of accepting defective material cannot be explicitly stated. The paper presents the formulation, describes when it should be used, derives a good analytical approximation under certain assumptions and gives various ramifications when it is used.     

Designing a screening experiment for highly reliable products

Within a reasonable life‐testing time, how to improve the reliability of highly reliable products is one of the great challenges to today's manufacturers. By using a resolution III experiment together with degradation test, Tseng, Hamada, and Chiao (1995) presented an interesting case study of improving the reliability of fluorescent lamps. However, in conducting such an experiment, they did not address the problem of how to choose the optimal settings of variables, such as sample size, inspection frequency, and termination time for each run, which are influential to the correct identification of significant factors and the experimental cost. Assuming that the product's degradation paths satisfy Wiener processes, this paper proposes a systematic approach to the aforementioned problem. First, an intuitively appealing identification rule is proposed. Next, under the constraints of a minimum probability of correct decision and a maximum probability of incorrect decision of the proposed identification rule, the optimum test plan (including the determinations of inspection frequency, sample size, and termination time for each run) can be obtained by minimizing the total experimental cost. An example is provided to illustrate the proposed method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 514–526, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10024     

Sensitivity analysis on responsive pricing and production under imperfect demand updating

This paper examines three types of sensitivity analysis on a firm's responsive pricing and responsive production strategies under imperfect demand updating. Demand has a multiplicative form where the market size updates according to a bivariate normal model. First, we show that both responsive production and responsive pricing resemble the classical pricing newsvendor with posterior demand uncertainty in terms of the optimal performance and first‐stage decision. Second, we show that the performance of responsive production is sensitive to the first‐stage decision, but responsive pricing is insensitive. This suggests that a “posterior rationale” (ie, using the optimal production decision from the classical pricing newsvendor with expected posterior uncertainty) allows a simple and near‐optimal first‐stage production heuristic for responsive pricing. However, responsive production obtains higher expected profits than responsive pricing under certain conditions. This implies that the firm's ability to calculate the first‐stage decision correctly can help determine which responsive strategy to use. Lastly, we find that the firm's performance is not sensitive to the parameter uncertainty coming from the market size, total uncertainty level and information quality, but is sensitive to uncertainty originating from the procurement cost and price‐elasticity.     

Stochastic allocation of inspection capacity to competitive processes

Optimal allocation and control of limited inspection capacity for multiple production processes are considered. The production processes, which operate independently but share inspection capacity, are subject to random failures and are partially observed through inspection. This study proposes an approach of stochastic allocation, using a Markov decision process, to minimize expected total discounted cost over an infinite time horizon. Both an optimal model and a disaggregate approximation model are introduced. The study provides some structural results and establishes that the control policy is of a threshold type. Numerical experiments demonstrate a significantly decreased amount of computational time required for the disaggregate approach when compared to the optimal solution, while generating very good control policies. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 78–94, 2002; DOI 10.1002/nav.1049     

Capacitated selection problem

Optimizing the selection of resources to accomplish a set of tasks involves evaluating the tradeoffs between the cost of maintaining the resources necessary to accomplish the tasks and the penalty cost associated with unfinished tasks. We consider the case where resources are categorized into types, and limits (capacity) are imposed on the number of each type that can be selected. The objective is to minimize the sum of penalty costs and resource costs. This problem has several practical applications including production planning, new product design, menu selection and inventory management. We develop a branch‐and‐bound algorithm to find exact solutions to the problem. To generate bounds, we utilize a dual ascent procedure which exploits the special structure of the problem. Information from the dual and recovered primal solutions are used to select branching variables. We generate strong valid inequalities and use them to fix other variables at each branching step. Results of tests performed on reasonably sized problems are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 19–37, 1999     

Selection of the optimal setup policy

A model is developed taking into consideration all the costs (namely cost of sampling, cost of not detecting a change in the process, cost of a false indication of change, and the cost of readjusting detected changes) incurred when a production process, using an unscheduled setup policy, utilizes fraction-defective control charts to control current production. The model is based on the concept of the expected time between detection of changes calling for setups. It is shown that the combination of unscheduled setups and control charts can be utilized in an optimal way if those combinations of sample size, sampling interval, and extent of control limits from process average are used that provide the minimum expected total cost per unit of time. The costs of a production process that uses unscheduled setups in conjunction with the appropriate optimal control charts are compared to the costs of a production process that uses scheduled setups at optimum intervals in conjunction with its appropriate control charts. This comparison indicates the criteria for selecting production processes with scheduled setups using optimal setup intervals over unscheduled setups. Suggestions are made to evaluate the optimal process setup strategy and the accompanying optimal decision parameters, for any specific cost data, by use of computer enumeration. A numerical example for assumed cost and process data is provided.     

Optimal scheduling of reader—systems

We consider a reader—writer system consisting of a single server and a fixed number of jobs (or customers) belonging to two classes. Class one jobs are called readers and any number of them can be processed simultaneously. Class two jobs are called writers and they have to be processed one at a time. When a writer is being processed no other writer or readers can be processed. A fixed number of readers and writers are ready for processing at time 0. Their processing times are independent random variables. Each reader and writer has a fixed waiting cost rate. We find optimal scheduling rules that minimize the expected total waiting cost (expected total weighted flowtime). We consider both nonpreemptive and preemptive scheduling. The optimal nonpreemptive schedule is derived by a variation of the usual interchange argument, while the optimal schedule in the preemptive case is given by a Gittins index policy. These index policies continue to be optimal for systems in which new writers enter the system in a Poisson fashion. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 483–495, 1998     

A closed-from approach for multi-item inventory grouping

The problem of optimally coordinating the replenishments of the many items in stock with one another is dealt with in this article. Specifically, it considers this coordination based on classifying the items into a few groups with common order cycles for all the items in a particular group. Assuming that the cumulative distribution by value of the inventory can be characterized by a Pareto function of the type f(n) = n/(an + b), (a, b > 0), it establishes that the optimal boundaries of the groups can be obtained as closed-form expressions by solving a system of simultaneous equations. The composition of the successive groups thus obtained is found to equipartition the total cost and to follow geometric sequences in relation to the number of items, the value of items, and the lengths of the order cycles. Graphs have been proposed to aid the implementation of the grouping scheme. Simple iterative schemes are outlined within the framework of the Pareto function to handle other relevant costs.     

Dynamic pricing and replenishment: Optimality,bounds, and asymptotics

In many applications, managers face the problem of replenishing and selling products during a finite time horizon. We investigate the problem of making dynamic and joint decisions on product replenishment and selling in order to improve profit. We consider a backlog scenario in which penalty cost (resulting from fulfillment delay) and accommodation cost (resulting from shortage at the end of the selling horizon) are incurred. Based on continuous‐time and discrete‐state dynamic programming, we study the optimal joint decisions and characterize their structural properties. We establish an upper bound for the optimal expected profit and develop a fluid policy by resorting to the deterministic version of the problem (ie, the fluid problem). The fluid policy is shown to be asymptotically optimal for the original stochastic problem when the problem size is sufficiently large. The static nature of the fluid policy and its lack of flexibility in matching supply with demand motivate us to develop a “target‐inventory” heuristic, which is shown, numerically, to be a significant improvement over the fluid policy. Scenarios with discrete feasible sets and lost‐sales are also discussed in this article.     

Designing a degradation experiment

Degradation experiments are widely used to assess the reliability of highly reliable products which are not likely to fail under the traditional life tests. In order to conduct a degradation experiment efficiently, several factors, such as the inspection frequency, the sample size, and the termination time, need to be considered carefully. These factors not only affect the experimental cost, but also affect the precision of the estimate of a product's lifetime. In this paper, we deal with the optimal design of a degradation experiment. Under the constraint that the total experimental cost does not exceed a predetermined budget, the optimal decision variables are solved by minimizing the variance of the estimated 100pth percentile of the lifetime distribution of the product. An example is provided to illustrate the proposed method. Finally, a simulation study is conducted to investigate the robustness of this proposed method. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 689–706, 1999     

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

为了进一步提升设备维修决策的科学性,通过建立综合设备剩余寿命预测数据与不确定失效阈值的最优维修决策模型,实现了不可维修设备的最优替换策略。构建基于非线性Wiener过程的设备性能退化模型,并采用极大似然法估计退化模型参数;提出一种基于期望最大(Expectation Maximization, EM)算法的不确定失效阈值分布系数估计方法,通过引入虚拟失效阈值数据实现对失效阈值分布系数的同步迭代更新;基于首达时的概念推导出不确定失效阈值条件下设备剩余寿命的概率密度函数,并基于更新报酬理论建立维修决策模型,从而实现设备的最优维修决策。算例分析表明,设备的失效阈值会对维修决策结果产生重要影响,考虑设备失效阈值的不确定性既有助于提升剩余寿命预测的准确性,又可以有效降低设备的寿命周期费用。     

Computing bounds for the optimal value in linear programming

Consider a standard linear programming problem and suppose that there are bounds available for the decision variables such that those bounds are not violated at an optimal solution of the problem (but they may be violated at some other feasible solutions of the problem). Thus, these bounds may not appear explicitly in the problem, but rather they may have been derived from some prior knowledge about an optimal solution or from the explicit constraints of the problem. In this paper, the bounds on variables are used to compute bounds on the optimal value when the problem is being solved by the simplex method. The latter bounds may then be used as a termination criteria for the simples iterations for the purpose of finding a “sufficiently good” near optimal solution. The bounds proposed are such that the computational effort in evaluating them is insignificant compared to that involved in the simplex iterations. A numerical example is given to demonstrate their performance.     

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.     

Optimal control of a production‐inventory system with both backorders and lost sales

We consider the optimal control of a production inventory‐system with a single product and two customer classes where items are produced one unit at a time. Upon arrival, customer orders can be fulfilled from existing inventory, if there is any, backordered, or rejected. The two classes are differentiated by their backorder and lost sales costs. At each decision epoch, we must determine whether or not to produce an item and if so, whether to use this item to increase inventory or to reduce backlog. At each decision epoch, we must also determine whether or not to satisfy demand from a particular class (should one arise), backorder it, or reject it. In doing so, we must balance inventory holding costs against the costs of backordering and lost sales. We formulate the problem as a Markov decision process and use it to characterize the structure of the optimal policy. We show that the optimal policy can be described by three state‐dependent thresholds: a production base‐stock level and two order‐admission levels, one for each class. The production base‐stock level determines when production takes place and how to allocate items that are produced. This base‐stock level also determines when orders from the class with the lower shortage costs (Class 2) are backordered and not fulfilled from inventory. The order‐admission levels determine when orders should be rejected. We show that the threshold levels are monotonic (either nonincreasing or nondecreasing) in the backorder level of Class 2. We also characterize analytically the sensitivity of these thresholds to the various cost parameters. Using numerical results, we compare the performance of the optimal policy against several heuristics and show that those that do not allow for the possibility of both backordering and rejecting orders can perform poorly.© 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

The initial provisioning decision for insurance type items

Initial provisioning decisions (inventory stocking requirements) for low demand items often have to be made without much knowledge of what future demand rates will be. When the nature of an item is such that little demand for it is expected, the problem of whether to stock initially or risk not stocking the item is most critical. This report discusses this problem and presents decision procedures which can be used to handle this aspect of initial provisioning. The procedures relate an item's provisioning desirability to its provisioning characteristics, such as expected cost, expected resupply time, current information on its likely demand rate, and to an overall operating policy or criterion. The criterion function measures the total system degredation as a function of the events of having items out of stock when demand occurs. Several different policy functions are discussed and the provisioning decision rules which apply to each are presented. Demand rate information is handled through a Bayesian type approach. The decision rules presented in this report can be utilized to either determine stocking requirements within a budgetary constraint, or determine the relative stocking desirability on an item-by-item basis.     

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     

A novel modeling approach for express package carrier planning

Express package carrier networks have large numbers of heavily‐interconnected and tightly‐constrained resources, making the planning process difficult. A decision made in one area of the network can impact virtually any other area as well. Mathematical programming therefore seems like a logical approach to solving such problems, taking into account all of these interactions. The tight time windows and nonlinear cost functions of these systems, however, often make traditional approaches such as multicommodity flow formulations intractable. This is due to both the large number of constraints and the weakness of the linear programming (LP) relaxations arising in these formulations. To overcome these obstacles, we propose a model in which variables represent combinations of loads and their corresponding routings, rather than assigning individual loads to individual arcs in the network. In doing so, we incorporate much of the problem complexity implicitly within the variable definition, rather than explicitly within the constraints. This approach enables us to linearize the cost structure, strengthen the LP relaxation of the formulation, and drastically reduce the number of constraints. In addition, it greatly facilitates the inclusion of other stages of the (typically decomposed) planning process. We show how the use of templates, in place of traditional delayed column generation, allows us to identify promising candidate variables, ensuring high‐quality solutions in reasonable run times while also enabling the inclusion of additional operational considerations that would be difficult if not impossible to capture in a traditional approach. Computational results are presented using data from a major international package carrier. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008