Unbounded knapsack problem with controllable rates: the case of a random demand for items

This paper focuses on a dynamic, continuous-time control generalization of the unbounded knapsack problem. This generalization implies that putting items in a knapsack takes time and has a due date. Specifically, the problem is characterized by a limited production horizon and a number of item types. Given an unbounded number of copies of each type of item, the items can be put into a knapsack at a controllable production rate subject to the available capacity. The demand for items is not known until the end of the production horizon. The objective is to collect items of each type in order to minimize shortage and surplus costs with respect to the demand. We prove that this continuous-time problem can be reduced to a number of discrete-time problems. As a result, solvable cases are found and a polynomial-time algorithm is suggested to approximate the optimal solution with any desired precision.     

Optimal production run length for products sold with warranty

This article studies the optimal production run length for a deteriorating production system in which the products are sold with free minimal repair warranty. The deterioration process of the system is characterized by a two-state continuous-time Markov chain. For products sold with free minimal repair warranty, we show that there exists a unique optimal production run length such that the expected total cost per item is minimized. Since there is no closed form expression for the optimal production run length, an approximate solution is derived. In addition, three special cases which provide bounds for searching the optimal production run length are investigated and some sensitivity analysis is carried out to study the effects of the model parameters on the optimal production run length. Finally, a numerical example is given to evaluate the performance of the optimal production run length.     

Dynamic economic lot size model with perishable inventory and capacity constraints

In this study, we consider a dynamic economic lot sizing problem for a single perishable item under production capacities. We aim to identify the production, inventory and backlogging decisions over the planning horizon, where (i) the parameters of the problem are deterministic but changing over time, and (ii) producer has a constant production capacity that limits the production amount at each period and is allowed to backorder the unmet demand later on. All cost functions are assumed to be concave. A similar problem without production capacities was studied in the literature and a polynomial time algorithm was suggested (Hsu, 2003 [1]). We assume age-dependent holding cost functions and the deterioration rates, which are more realistic for perishable items. Backordering cost functions are period-pair dependent. We prove the NP-hardness of the problem even with zero inventory holding and backlogging costs under our assumptions. We show the structural properties of the optimal solution and suggest a heuristic that finds a good production and distribution plan when the production periods are given. We discuss the performance of the heuristic. We also give a Dynamic Programing-based heuristic for the solution of the overall problem.     

Optimal Production Policy for an Item with Shortages and Increasing Time-varying Demand

A new production-inventory model is developed for an item with increasing time-varying demand during a finite planning period. We assume that shortages are fully backordered, and the cost of adjusting the production rate depends on the magnitude of the change in the production rate. The objective is to find the optimal policy of adjusting the production rate in order to minimize the total system cost. A solution procedure is presented and a numerical example is provided for the special case of linearly increasing demand.     

An impulse control problem of a production model with interruptions to follow stochastic demand

The paper deals with the stochastic optimal intervention problem which arises in a production & storage system involving identical items. The requests for items arrive at random and the production of an item can be interrupted during production to meet the corresponding demand. The operational costs considered are due to the stock/backlog, running costs and set up costs associated to interruptions and re-initializations. The process presents distinct behaviour on each of two disjoint identical subsets of the state space, and the state process can only be transferred from one subset to the other by interventions associated to interruptions/re-initializations. A characterization is given in terms of piecewise deterministic Markov process, which explores the aforementioned structure, and a method of solution with assured convergence, that does not require any special initialization, is provided.Additionally, we demonstrate that under conditions on the data, the optimal policy is to produce the item completely in a certain region of the state space of low stock level.     

Modelling condition monitoring intervals: A hybrid of simulation and analytical approaches

This paper reports on a study of modelling condition monitoring intervals. The model is formulated based upon two important concepts. One is the failure delay time concept, which is used to divide the failure process of the item into two periods, namely a normal working period followed by a failure delay time period from a defect being first identified to the actual failure. The other is the conditional residual time concept, which assumes that the residual time also depends on the history condition information obtained. Stochastic filtering theory is used to predict the residual time distribution given all monitored information obtained to date over the failure delay time period. The solution procedure is carried out in two stages. We first propose a static model that is used to determine a fixed condition monitoring interval over the item life. Once the monitored information indicates a possible abnormality of the item concerned, that is the start of the failure delay time, a dynamic approach is employed to determine the next monitoring time at the current monitoring point given that the item is not scheduled for a preventive replacement before that time. This implies that the dynamic model overrides the static model over the failure delay time since more frequent monitoring might be needed to keep the item in close attention before an appropriate replacement is made prior to failure. Two key problems are addressed in the paper. The first is which criterion function we should use in determining the monitoring check interval, and the second is the optimization process for both models, which can be solved neither analytically nor numerically since they depend on two unknown quantities, namely, the available condition information and a decision of the time to replace the item over the failure delay time. For the first problem, we propose five appealingly good criterion functions, and test them using simulations to see which one performs best. The second problem was solved using a hybrid of simulation and analytical solution procedures. We finally present a numerical example to demonstrate the modelling methodology.     

客户耐烦期相同的生产——库存系统最优模型

在常数需求率以及有限生产率条件下研究了订货客户耐烦期相同的一类新的生产——库存模型 ,在每一个周期内考虑了延期交货时间超过耐烦期的短缺费用和销售机会损失等因素 ,给出了相应的最优生产时间和周期的确定方法 ,利用数学软件 Matlab及计算机为工具给出了数字例子进行说明 ,其方法和结果为库存系统的管理决策提供了理论依据     

Optimal production stopping and restarting times for an EOQ model with deteriorating items

A perishable single item production-inventory system is studied in this paper. The objective is to describe a general model in which the production rate, the product demand rate, and the item deterioration rate are all considered as functions of time, and to discuss the optimal production stopping and restarting times which minimise the total relevant cost per unit time. In the general model, demand shortage is allowed, where some of the demand is lost and the rest is backlogged. Popular models, such as the pure inventory system and the zero shortage system, are shown to be special cases of our model. The conditions for a feasible stationary point to be optimal are given. The simplest cases with constant rates of production, demand and deterioration are discussed and shown as illustrative examples.     

考虑时值及通货膨胀率的多阶段变质性物品最优库存模型

本文考虑了时值及通货膨胀率下，部分短缺量拖后的变质性物品最优订购问题。在假定变质率为常数和短缺期间损失率与实际缺货量成正比的前提下，给出了寻找最优订购策略的算法，并且证明了在该策略下费用函数取得最小值。最后给出数字实例以说明本模型及求解过程。     

多货栈及变质情形下两种可替代物品的经济订货批量模型

研究了多货栈及变质情形下两种可替代物品的经济订货批量问题.在计划期内,若某一种易变质物品发生缺货,则可以被另一种易变质物品以一定的替代率代替补充,不同物品有不同的变质率,且要决定租用货栈的数量.以库存系统的总费用最小为目标函数,分别对货栈容量无限与有限的情形建立模型,证明了最优策略存在的唯一性,并分别给出了求解最优订购策略的算法,最后通过一个算例验证了算法的最优性.     

An inventory model for slow moving items subject to obsolescence

In this paper, we consider a continuous review inventory system of a slow moving item for which the demand rate drops to a lower level at a known future time instance. The inventory system is controlled according to a one-for-one replenishment policy with a fixed lead time. Adapting to lower demand is achieved by changing the control policy in advance and letting the demand take away the excess stocks. We show that the timing of the control policy change primarily determines the tradeoff between backordering penalties and obsolescence costs. We propose an approximate solution for the optimal time to shift to the new control policy minimizing the expected total cost during the transient period. We find that the advance policy change results in significant cost savings and the approximation yields near optimal expected total costs.     

A stochastic periodic review integrated inventory model involving defective items, backorder price discount, and variable lead time

The purpose of this article is to investigate a stochastic integrated supplier-retailer inventory problem. The model analyzed in this article explores the problem of the protection interval, the backorder price discount, the lead time, and the numbers of shipments from the supplier to the retailer in one production run as control variables to widen applications for an integrated periodic review inventory model. We consider the situation in which the supplier and the retailer establish a long-term strategic partnership and contract to jointly determine the best strategy. We assume that the protection interval demand follows a normal distribution. Our objective is to determine the optimal review period, the optimal backorder price discount, the optimal lead time, and the optimal number of shipments from the supplier to the retailer in one production run, so that the joint expected annual total cost incurred has the minimum value. Furthermore, an algorithm of finding the optimal solution is developed. Also, the sensitivity analysis included and a numerical example is given to illustrate the results of the proposed model.     

The Finite Horizon Trended Inventory Replenishment Problem With Shortages

A new type of replenishment policy is suggested for an inventory item having a finite shortage cost and linear trend in demand over a finite time horizon. The optimal solution of the suggested replenishment policy has a lower total cost as compared with the optimal solution for the traditional replenishment policies.     

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.     

The static stochastic knapsack problem with normally distributed item sizes

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item’s value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.     

Inventory Replenishment Policy for Linearly Increasing Demand Considering Shortages-An Optimal Solution

An optimal solution for inventory replenishment policy for an item having a deterministic demand pattern with linear increasing trend is developed considering shortages. Numerical examples are given to illustrate the results.     

Optimal production inventory policy for defective items with fuzzy time period

In this paper, an optimal production inventory model with fuzzy time period and fuzzy inventory costs for defective items is formulated and solved under fuzzy space constraint. Here, the rate of production is assumed to be a function of time and considered as a control variable. Also the demand is linearly stock dependent. The defective rate is taken as random, the inventory holding cost and production cost are imprecise. The fuzzy parameters are converted to crisp ones using credibility measure theory. The different items have the different imprecise time periods and the minimization of cost for each item leads to a multi-objective optimization problem. The model is under the single management house and desired inventory level and product cost for each item are prescribed. The multi-objective problem is reduced to a single objective problem using Global Criteria Method (GCM) and solved with the help of Fuzzy Riemann Integral (FRI) method, Kuhn–Tucker condition and Generalised Reduced Gradient (GRG) technique. In optimum results including production functions and corresponding optimum costs for the different models are obtained and then are presented in tabular forms.     

Production-inventory control policy under warm/cold state-dependent fixed costs and stochastic demand: partial characterization and heuristics

The motivation for our study comes from some production and inventory systems in which ordering/producing quantities that exceed certain thresholds in a given period might eliminate some setup activities in the next period. Many examples of such systems have been discussed in prior research but the analysis has been limited to production settings under deterministic demand. In this paper, we consider a periodic-review production-inventory model under stochastic demand and incorporate the following fixed-cost structure into our analysis. When the order quantity in a given period exceeds a specified threshold value, the system is assumed to be in a “warm” state and no fixed cost is incurred in the next period regardless of the order quantity; otherwise the system state is considered “cold” and a positive fixed cost is required to place an order. Assuming that the unsatisfied demand is lost, we develop a dynamic programming formulation of the problem and utilize the concepts of quasi-K-convexity and non-K-decreasing to show some structural results on the optimal cost-to-go functions. This analysis enables us to derive a partial characterization of the optimal policy under the assumption that the demands follow a Pólya or uniform distribution. The optimal policy is defined over multiple decision regions for each system state. We develop heuristic policies that are aimed to address the partially characterized decisions, simplify the ordering policy, and save computational efforts in implementation. The numerical experiments conducted on a large set of test instances including uniform, normal and Poisson demand distributions show that a heuristic policy that is inspired by the optimal policy is able to find the optimal solution in almost all instances, and that a so-called generalized base-stock policy provides quite satisfactory results under reasonable computational efforts. We use our numerical examples to generate insights on the impact of problem parameters. Finally, we extend our analysis into the infinite horizon setting and show that the structure of the optimal policy remains similar.     

Profitability ratio maximization in an inventory model with stock-dependent demand rate and non-linear holding cost

This paper studies a deterministic inventory model with a stock-dependent demand pattern where the cumulative holding cost is a non-linear function of both time and stock level. When the monetary resources are limited and the inventory manager can invest his/her money in buying different products, it seems reasonable to select the ones that provide a higher profitability. Thus, a new approach with the aim of maximizing the profitability ratio (defined as the profit/cost quotient) is considered in this paper. We prove that the profitability ratio maximization is equivalent to minimizing the inventory cost per unit of an item. The optimal policy is obtained in a closed form, whose general expression is a generalization of the classical EOQ formula for inventory models with a stock-dependent demand rate and a non-linear holding cost. This optimal solution is different from the other policies proposed for the problems of minimum cost or maximum profit per unit time. A complete sensitivity analysis of the optimal solution with respect to all the parameters of the model is developed. Finally, numerical examples are solved to illustrate the theoretical results and the solution methodology.     

On upper bounds of sequential stochastic production planning problems

In this paper we consider a class of problems that determine production, inventory and work force levels for a firm in order to meet fluctuating demand requirements. A production planning problem arises because of the need to match, at the firm level, supply and demand efficiently. In practice, the two common approaches to counter demand uncertainties are (i) carrying a constant safety stock from period to period, and (ii) planning with a rolling horizon. Under the rolling horizon (or sequential) strategy the planning model is repeatedly solved, usually at the end of every time period, as new information becomes available and is used to update the model parameters. The costs associated with a rolling horizon strategy are hard to compute a priori because the solution of the model in any intermediate time period depends on the actual demands of the previous periods.In this paper we derive two a priori upper bounds on the costs for a class of production planning problems under the rolling horizon strategy. These upper bounds are derived by establishing correspondences between the rolling horizon problems and related deterministic programs. One of the upper bounds is obtained through Lagrangian relaxation of the service level constraint. We propose refinements to the non-Lagrangian bounds and present limited computational results. Extensions of the main results to the multiple item problems are also discussed. The results of this paper are intended to support production managers in estimating the production costs and value of demand information under a rolling horizon strategy.