Structured policies for complex production and inventory models
Creators: name: Sun, Daning
Publisher: name: University of British Columbia
Year: 2011

description: For inventory models minimizing the long-run average cost over an infinite horizon, the existence of optimal policies was an open question for a long time. Consider a deterministic, continuous time inventory system satisfies the following conditions: the production network is acyclic, the joint setup cost function is monotone, the holding cost and the backlogging cost rates are nonnegative, the demand rates are constant over time, the production rates are infinite or finite non-increasing, and backlogging may be allowed or not. For this very general extension of the Wilson-Harris EOQ model, we prove the existence of optimal policies. Very few properties of optimal policies have been discovered since the 1950's. Restricting the above inventory model to infinite production rates, we present some new properties of optimal policies, such as the Latest Ordering Property, and explicit expressions for echelon inventories and order quantities in terms of ordering instants. An assembly production system with n facilities has a constant external demand occurring at the end facility. Production rates at each facility are finite and non-increasing along any path in the assembly network. Associated with each facility are a set-up cost and positive echelon holding cost rate. The formulation of the lot-sizing problem is developed in terms of integer-ratio lot size policies. This formulation provides a unification of the integer-split policies formulation of Schwarz and Schrage [34] (1975) and the integer-multiple policies formulation of Moily [20] (1986), allowing either assumption to be operative at any point in the system. A relaxed solution to this unified formulation provides a lower bound to the cost of any feasible policy. The derivation of this Lower Bound Theorem is novel and relies on the notion of path holding costs, a generalization of echelon holding costs. An optimal power-of-two lot size policy is found by an 0(n³ log n) algorithm and its cost is within 2% of the optimum in the worst case. Mitchell [18] (1987) extended Roundy's 98%-effectiveness results for one-warehouse multi-retailer inventory systems with backlogging. We extend this 98%-effectiveness result for series inventory systems with backlogging. The nearly-integer-ratio policies still work. The continuous relaxation provides a lower bound on the long-run average cost of any feasible policy. The backlogging model is also reduced in 0{n) time to an equivalent model without backlogging. Roundy's results [27] (1983) are then applied for finding a 98%-effective backlogging policy in O(nlogn) time. In an EOQ model with n products, joint setup costs provide incentives for joint replenishment. These joint setup costs may be modelled as a positive, nondecreasing, submodular set function. A grouping heuristic partitions the n products into groups, and all products in the same group are always jointly replenished. Each group is then considered as a single "aggregate product" being replenished independently of the other groups, and therefore according to the EOQ formula. As a result, possible savings when several groups are simultaneously replenished are simply ignored. Our main result is that the cost of the best such grouping solution cannot be worse than 44.8% above the optimum cost. Known examples show that it can be as bad as 22.4% above the optimum cost. These results contrast with earlier results for power-of-two policies, the best of which never being worse than about 2% above the optimum cost.