ON PROPERTIES OF THE ORDER-BASED COST FUNCTION IN ASSEMBLE-TO-ORDER SYSTEMS by Mohammadreza Bolandnazar B.Sc., Sharif University of Technology, 2011 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES (Business Administration) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) October 2013 ? Mohammadreza Bolandnazar, 2013 ii Abstract One of the main results of ?Order-Based Cost Optimization in Assemble-to-Order Systems? [1] by Y. Lu and J-S. Song, Operations Research, 53, 151-169 (2005) is Proposition 1 (c), which states that the cost function of an assemble-to-order inventory system satisfies a discrete convexity property called L?-convexity. Based on this result, Lu and Song proposed two types of L?-convex minimization algorithms for finding the optimum policy. We construct a simple assemble-to-order system for which the cost function fails to satisfy L?-convexity. Using a similar system, we further show that the cost function may not enjoy a more general notion of discrete convexity property called -convexity. Yet, because of some other properties of the cost function, one can still solve the cost optimization problem using other methods from the literature. iii Preface This thesis is edited based on helpful comments from Tom McCormick, Tim Huh and Maurice Queyranne. Chapter 3 is based on a model used by Y. Lu and J-S. Song in ?Order-Based Cost Optimization in Assemble-to-Order Systems? [1] , Operations Research, 53, 151-169 (2005). I have been the main contributor and responsible for developing the mathematical analysis. This thesis has benefited from insightful comments suggested by Kazuo Murota. A version of chapter 3 will be submitted for publication in academic peer reviewed journals. iv Table of Contents Abstract .......................................................................................................................................... ii Preface ........................................................................................................................................... iii Table of Contents ......................................................................................................................... iv List of Figures ............................................................................................................................... vi List of Abbreviations .................................................................................................................. vii Acknowledgements .................................................................................................................... viii Dedication ..................................................................................................................................... ix Chapter 1: Introduction ................................................................................................................1 1.1 Inventory Management ................................................................................................... 1 1.2 Assemble To Order Systems ........................................................................................... 3 1.3 Literature Review............................................................................................................ 7 1.4 Contributions and Structure .......................................................................................... 15 Chapter 2: Mathematical Background ......................................................................................17 2.1 A Brief Review on Discrete Convexity Analysis ......................................................... 17 2.2 L?/M?/D-convexity ........................................................................................................ 18 2.3 Computational Importance of Discrete Convexity ....................................................... 22 2.4 Coordinatewise-Convex Submodular Functions .......................................................... 25 2.4.1 Reduction Algorithm ................................................................................................ 26 2.4.2 Transformation Method ............................................................................................ 27 2.4.3 Proposed Algorithm .................................................................................................. 28 Chapter 3: Order-Based Inventory System ...............................................................................30 v 3.1 Model Specification ...................................................................................................... 30 3.2 Cost Function and Optimum Policy .............................................................................. 37 3.3 Cost Optimization Algorithm ....................................................................................... 43 3.4 Gaps in The Proof ......................................................................................................... 44 3.5 A Remark on L?-Convexity of The Cost Function ....................................................... 48 Chapter 4: Conclusion .................................................................................................................52 Bibliography .................................................................................................................................53 vi List of Figures Figure -1 sample lattice points in evaluation of expected backorders for different policies ........ 34 vii List of Abbreviations ATO: Assemble-To-Order FCFS: First-Come-First-Serve CCS: Coordinate-wise Convex Submodular SDLMIN: Steepest Descent algorithm for an L?-convex function MSDLMIN: Modified Steepest Descent algorithm for an L?-convex function FTLMIN: Favatti-Tardella algorithm for an L?-convex function over a given interval RDCSUB: Reduction Algorithm for a submodular function over a given interval CCSMIN: Algorithm for minimizing a CCS function over a given interval viii Acknowledgements I would like to thank my supervisors, Dr. T. McCormick and Dr. T. Huh for expanding my vision of the field of research and providing precise answers to my questions. I owe my deepest gratitude to Dr. Queyranne for his insightful questions and comments as my thesis committee member. Special thanks are owed to Dr. K. Murota, for his knowledgeable advice for the thesis. I offer my strong appreciation to Dr. Gillen and Dr. Lindsey who have inspired me to work in this field. I owe particular thanks to my wife, who has supported me throughout my master degree. This research was partially supported by NSERC Grants. ix Dedication To my parents, Fatemeh and Ahmad, and my wife, Roya. 1 Chapter 1: Introduction 1.1 Inventory Management Inventory management is the practice of efficiently administrating the flow of items into and out of an existing inventory. This procedure generally includes scheduling the assignment of units in order to keep the inventory level from becoming unnecessarily high, or becoming too low; two situations which could threaten the operation of the whole supply chain. Proficient inventory management also looks for methods to lower the costs associated with the inventory, both from the perspective of the total holding costs of the goods involved and the liability generated by the goods that are ordered but are not fulfilled in a reasonable time A successful inventory management pays attention to two main facets of any inventory system: lead times and buffer stocks. How long does it take for their suppliers to process their orders and complete deliveries? Inventory management also needs to establish an understanding of how long it will take for those items to transfer out of the inventory and satisfy the customer?s demand. Recognizing these two types of lead times makes it possible to identify how many units must be ordered and when to place these orders to have a smooth manufacturing process. Buffer stock is another important issue in inventory management. Basically, buffer stock is known as extra units kept in the inventory in order to hedge against different kinds of variability in the system such as production levels. For example, the manager may think that it is 2 not a bad idea to keep some additional units of a given machine part on hand, in case an unpredictable flow of demand arises. Generating this buffer aims to lower the chance of stockout in the whole supply chain. Inventory managers usually face a trade-off between holding costs and stock-out costs. If the inventory on-hand becomes too high, the manager may pay an unnecessary amount of money in order to hold the excess inventory on shelves. On the other hand, if the inventory levels become too low, the company will lose revenue because of a lack of customer satisfaction due to stockouts. Efficient inventory management requires an optimum ordering plan which ensures that items are in stock when they are needed and also an allocation policy for existing inventory on hand. In the base-stock policy there is an initial amount of inventory. Once a new demand for a product arrives, a replenishment order is immediately sent to the suppliers of corresponding components. For each particular component it takes an amount of time- called component?s replenishment lead time- that the component arrives at inventory system. This lead time depends on the corresponding supplier?s characteristics and is often assumed to be a random variable independent from other components? lead times. Tracking stock levels is a vital part of inventory operations for any business. There are two commonly used ways of tracking stock levels in inventories: Periodic review and continuous review. In inventory operations, periodic review means to track and manage inventory at particular times. For example, under this policy a retailer gathers data and makes replenishment 3 decisions at the end of each week. On the other hand, in a continuous inventory review policy, the current level of each item is documented and updated each time that item is removed from inventory. In retail stores where purchases are recorded using bar code scanners, the inventory level of each item can be updated immediately after its bar code is scanned and a continuous review scheme can be implemented. Providing a periodic review scheme is easier and involves lower monitoring costs than a continuous review scheme, yet it may lead to inaccurate inventory decisions especially when the managers face high-variability sales. On the other hand, continuous review enables real-time control of inventory levels, which allows mangers to determine accurately reorder times of required items in order to replenish inventory. This scheme also improves the accuracy of accounting, given that the inventory system is able to track real-time costs of retailed products. However, the key drawback of this scheme is the implementation cost such as providing bar-code scanners, computer systems, etc. 1.2 Assemble To Order Systems One of the challenging types of multi-item inventory systems is for assemble-to-order production systems, in which each product is assembled only after all required components are received. In an assemble-to-order (ATO) system generally there are several components and several final products. Customers, order only final products, however, the inventory system holds only components. Each final product is assembled from a specific subset of components, where several units of some components may be required. The assembly time is often assumed to be 4 insignificant, whereas the production-delivery time of components is often assumed to be considerable. Computer manufacturers: The assemble-to-order structure can be useful in industries where a number of components can be placed together immediately to form a final product. For example, in the computer industry, as soon as the main components (mother board, hard drives, CPU, etc.) are available in one point, the final product (a desktop or laptop) can be manufactured quickly by assembling these components. At the beginning, computer industries were controlled under a make-to-stock1 framework. Yet, as soon as Internet started to play a role as a sales medium, the assemble-to-order approach became more popular. One of the best-known assemble-to-order systems is Dell Industries. Dell allows customers to choose among different type of CPUs, mother boards, hard drives, etc. Obviously, the possible number of final products could be very large. E-retailers: Consider an online retailer who holds inventories of several items in her stock. Customers order various collections of these items through an online intermediary. The assembly system corresponding to this example assumes, on one hand, the items in stock as components and on the other hand, the various collections of these items, which could be ordered by customers, as products. 1 Make-to-stock: A manufacturing strategy that uses a buffer stock of final products in order to decouple demand variability from production and matches production levels with customer demand forecasts. In this method the manufacturer tries to satisfy customer orders as soon as possible using products that are already produced and stocked in the inventory. 5 Automobile industries: It is not hard to realize that ATO systems can be implemented in automobile industries. The Economist in 2001 stated that ATO systems could reduce costs of automobile industries by $80 billion annually. Business Week reported that Ford is looking forward to implementing ATO systems in its manufacturing line [2]. The analysis and management of ATO systems are normally complicated, as we can interpret these systems as a hybrid between assembly systems and distribution systems each one with different aspects of complexity [3]. In other words, before implementing such systems two essential questions should be answered: First, is there any underlying coordination among the components, and second how should these components be allocated among the end products? The complexity of ATO systems is partly due to facing these two questions at the same time. There are other important questions to answer before start managing an ATO system: Is it efficient to backlog unsatisfied demands or to lose them? If backlogging is preferred then at any time that only part of the required components of a demand request are on hand, how should we deal with those components- whether it is better to ship them as partial-shipment or put them aside as committed inventory and wait for the remaining part of demand to arrive? If a component arrives, should we assign it to a recent demand or a backlogged one? These are trivial questions in handling single-product and single-component systems, while finding the answers in systems with several products ?made up by overlapping subsets of components, is what makes the analysis and management of these systems complicated. 6 One of the other facets of complexity in ATO systems is due to the replenishment leadtimes, as any decision for a replenishment order at one time may impact the inventory levels for a long time in the future. In the cases that the components are fundamentally different (in terms of their required materials, suppliers, etc.) the leadtimes for each of them is different from that of other components, which makes the model more complicated, especially when the lead times are uncertain. One of the other reasons that make multi-item ATO systems complicated is the correlation among items demands. In an ATO system, it is common to have orders for different products that are placed at the same time, while these products consist of components that are manufactured by separate suppliers. This process causes correlation among the orders at suppliers. The main focus of this research is on a paper of Lu and Song [1]. They modeled a continuous review ATO inventory system with random demands and lead-times in order to find an optimal base-stock policy with an order-based approach. To reiterate the model, suppose that different products require different -but not necessarily disjoint- subsets of items in order to be complete. The customer orders that cannot be fulfilled completely (once they were placed) are backordered. In their model, there is a cost involved with un-fulfilled orders, called backorder cost, and finally there is no cost associated with placing an order. They used two different approaches in finding an optimum base-stock policy: (i) proposing algorithms that find exact solution and (ii) obtaining closed-form approximations. In this thesis we will show that their proposed algorithm for finding exact solution does not necessarily give an optimum policy. We 7 will demonstrate that the inventory model used in their work does not satisfy the necessary conditions required for that algorithm to work properly. 1.3 Literature Review Single-product assembly systems with deterministic leadtimes have triggered many researches since the 1980s. Rosling [4] found that the optimal policy of a single product ATO system is equivalent to that of a serial system, which was established earlier by Clark and Scarf [5]. Schmidt and Nahmias [6] studied an inventory system with two components (with non-identical stochastic lead times) and one end product (with stochastic demand). Gallien and Wein [7] considered a single-product, make-to-stock inventory system where different components have non-identical stochastic lead times. They suggest a formulation for minimizing the inventory cost (holding and backorder) of such system over pre-specified replenishment policies. Cheng et al. [8] move from a make-to-stock system which is concentrated around end products to an assemble-to-order inventory system which does not consider stocking end-products. They give a constrained nonlinear optimization model to find an optimal inventory-service trade-off where each constraint describes the service level of one segment of market. They also give an exact algorithm for a special case in which every demand has a unique component. Despite the single-product case, for ATO systems with multiple products the structure of an optimal policy is not easy to capture. Baker et al. [9], considering a single-period, two-product inventory model, study the effects of component commonality on optimal safety stock levels. They try to minimize system safety stock subject to a service level constraint. In a single-period model, the additional products that remain unsold at the end of each period are not held for being 8 sold in the next period. However, these additional items may be sold at a salvage value for other purposes. We can effectively analyze single-period inventory systems with a static structure. In other words, in such systems each time period may be studied solely in its level and controlled separately from other periods. One of the best known examples of single period inventory operations is the classic newsvendor problem2. In this problem we do not need to consider replenishment lead-times as well as backorders.3 Song and Zipkin [3] have a nice literature reviews on ATO operation systems. It covers technical issues, analytical aspects and managerial insights gained in this field of research. Our main focus is on Lu and Song [1] that analyze a multi-period model of an ATO system with component commonality. As we discussed earlier in section 1.1, one of the factors that makes the analysis of ATO systems complicated, especially when there is uncertainty in the customer orders and item replenishments, is component commonality. Such commonality which causes correlation among the orders at component suppliers, is ignored in many inventory models in the literature; i.e. the demands for different items are assumed to be independent of each other. Lu and Song [1] call this attitude in analysis of ATO systems as item-based approach. 2 The newsvendor problem is an order quantity decision problem used for modeling inventory scenarios of perishable products that have a limited lifetime, an uncertain demand and lost sales. This classical problem is a cornerstone of inventory models under uncertain demand. In its basic characterization, there are two types of cost involved with the model: over-stocking cost which is unit cost of excess demand and under-stocking cost which is the unit cost of lost sales. 3 Instead, in a multi-period model, all the unsold items at the end of each period are being held in inventory for the next period. As we consider the connection between different periods the model becomes more complicated. In a dynamic approach, any final state of a single period should be considered as the initial state of the next period. 9 Instead, when the joint distribution of the product demand is considered, the resulting order-based [1] models become much more complicated. There are several approaches to analyze the correlated demand across different components in a multi-item system. Xu [10]studies the impact of this correlation on a various measures of system performance. In this work, the arrival of demand types is modeled as Poisson process, where the number of order units of each product is picked independently from an arbitrary distribution. Agrawal and Cohen [11] study the performance of an inventory system with commonality in the demands. They analyze the effects of different inventory policies on final delays due to backorders and use the results to find an optimal base stock policy. Song [12] presents a generalization of the notion of correlated demand. Similar to Xu [10], demand arrivals are modeled as a Poisson process with possibly several units of a particular item in each customer order. On the other hand, Song [12] has no independence assumption for batch size of a particular product. The concept of component commonality is considered mostly for periodic-review models, in the literature, while the model discussed by Lu and Song [1] assumes a continuous review scheme. An interesting example of periodic review ATO system with component commonality is analyzed by Akcay and Xu [13]. Their model considers a predefined response time interval (time window) for each product and if the demand for that product is fulfilled within the corresponding time interval (time window) the system receives a reward. They study a 10 two-stage stochastic integer programming model to find the optimal base-stock policy and also the optimal component allocation policy for the ATO system. Furthermore, they prove that the problem of finding optimal component allocation is a multidimensional knapsack problem (MDKP) and is therefore NP-hard. In addition, Hausman et al. [14] study a base-stock periodic-review multi-item inventory system in which orders are modeled by a general multivariate normal distribution (independent demands as a special case) and demands are filled under First-Come-First-Serve4 (FCFS) rule. They find the joint demand fulfillment probability within a pre-defined time window. In many studies, component commonality is considered for systems with zero lead times. Gerchak and Henig [15] present a general multi-period model of an assemble-to-order system with component commonality and investigate the behavior of optimal policies. They consider a storage constraint and assume a zero lead time. With such considerations, they conclude that the optimal levels of components can be lower in an assemble-to-order system than in a corresponding make-to-stock system. Yet, Song and Zhao [16] consider a model for a continuous-review system in which lead times are not necessarily zero. They observe that the effect of component commonality on optimal inventory costs depends on components lead times and the allocation policy. Based on this relationship they give a modified version of FCFS rule and evaluate the performance of the inventory system under this rule. They also talk about the different scenarios for which component commonality may be or may not be beneficial for the performance of the inventory system. In the model discussed by Lu and Song [1] the lead times are not necessarily zero. 4 FCFS is a service policy in which customer demands fulfilled in the order the demands have arrived. 11 Lu and Song [1] develop a comprehensive analysis on a multi-period model of an assemble-to-order inventory system with order-based approach. They assume that there is a cost involved with inventory holding and backorders, and the inventory is controlled under a continuous review scheme. They derive a cost function with respect to holding and backorder costs, and based on it, they try to minimize the expected cost by finding optimum base-stock levels. There are some other related works in the literature on evaluating or optimizing base-stock policy. Song et al [17] study a base-stock policy for a multi-item, multiproduct ATO inventory system, where each component is independently produced by a supplier. This study gives a class of performance measures, such as order fulfillment probability, in order to assess a given base-stock policy. Lu et al. [18] analyze the dependence structure in a multi item ATO system controlled by a base stock policy. This study results in closed-form expressions of mean and variance-covariance, of the problem variables which gives some useful approximations and bounds for the order fill rates- a system performance measure. Based on this, Cheng et al. [8] present an algorithm to find an optimum base-stock policy, subject to a fill rate constraint. A similar work by Zhou and Chao [19] develops a Stein-Chen approximation and its error-bound for order-based fill rate for a multi-item ATO system with random leadtimes of components replenishment. There are some alternatives, in the literature, for assumptions of Lu and Song [1] such as FCFS allocation rule. Although FCFS allocation rule is very common among those papers which assume continuous review scheme in evaluating and optimizing the base stock policies [12] [17] [18], Lu et al [20], adopt a class of common-component allocation rules, called no-holdback 12 (NHB) rules, in continuous-review ATO systems with positive lead times. NHB rule allocates a component to a final product only if it yields immediate fulfillment of the product demand. They compare key performance measures under this rule with those of FCFS. Plambeck and Ward [21] suggest alternatives for FCFS policies in a model based on a multidimensional Brownian approximation. In addition, while most of the researches on ATO systems concentrate on the assembly part, Plambeck [22] considers inventory at component suppliers and in transit line as well as at the assembly facility. Moreover, instead of assuming a homogenous and memory-less process such as Poisson, Lu [23] assumes that the demand process of each product is a renewal process in approximating key performance measures of her multi-item ATO system. Compared to those considered by Lu and Song [1], there may be other important factors in modeling an ATO system, such as returns. DeCroix et al. [24], consider a multi-period ATO system, managed under a base-stock policy, which experiences not only stochastic demands but also stochastic returns. These returns are also subsets of components that can be used to satisfy demands. They study several ways in which returns increase the complexity of different order-based performance metrics of the system such as average backorders. A different approach for finding the average inventory cost of a general class of ATO systems is introduced by Reiman and Wang [25]. They use a multi-stage stochastic program to provide a lower bound on the long run average cost for systems with deterministic lead times. There are two approaches in Lu and Song work [1], (i) finding exact solution and (ii) finding closed-form approximations. In general, finding exact solutions in such systems is computationally demanding. In a similar study, Fu et al., [26] suggest two approximation 13 methods in order to give bounds for several performance measures such as fill rate, average waiting time, and average number of backorders of the proposed system. Horng and Yang [27] have offered an ordinal optimization-based evolutionary algorithm to find a good enough target inventory level of an ATO system in reasonable computation time. Hong and Nelson [28]proposed an algorithm to solve an ATO system containing 8 components and 5 products via a stochastic and discrete-event simulation. To achieve exact solutions for optimal base-stock levels, Lu and Song [1] try to show that the cost function has some properties, such as submodularity and L?-convexity, which lead to use a steepest descent method. Several types of discrete convexity have been considered in the literature. Discretely convex functions were first proposed by Miller [29]. Next, Favati and Tardella [30] suggested the integrally-convex functions. The concept of M-convex functions and L-convex functions were introduced by Murota [31,32]. Based on these concepts two other types of convexity over integer lattice points were proposed later; M?-convexity by Murota and Shioura [33] then L?-convexity by Fujishige and Murota [34]. L?-convexity has recently had some applications in the inventory literature. Lu and Song [1] is one of the earliest papers in this field that introduced the notion of L?-convexity in the literature. They claim that the cost function for their inventory system enjoys L?-convexity and based on that they propose a steepest descent algorithm to find an optimum base-stock policy, using the fact that local optimality guarantees global optimality for L?-convex functions. Zipkin [35] presents an approach to the structural analysis of the standard, single-item lost-sales 14 inventory system with a positive lead time. It is shown that, the optimal cost function possesses L?-convexity with respect to a transformed space. This allows to describe the behavior of the optimal policy and conclude that the optimal order is monotone in the transformed state variables. Huh and Janakiraman [36] use the concept of L?-convexity for single stage systems, to find properties of the optimal policy in serial systems. Pang et al. [37] consider a joint inventory-pricing control problem for a periodic-review, single-stage inventory system with backorder costs. They demonstrate that the profit function, with respect to a transformed variable, is L?-concave which guarantees any local maximum to be a global maximum. They conclude that the optimum order quantity and demand rate for their system can be found using an ascent algorithm applied to the profit function. Lu et al. [38], focusing on the N-System, study the optimal inventory control policy for ATO systems with non-identical lead-times (In N-Systems, there are two products, one of which requires only component 1, and the other requires components 1 and 2). They use L?-convexity in order to show that the cost function in particular cases has unique minimum. Ui introduced a more general notion of convexity [39], called -convexity in discrete space considering an arbitrary neighborhood for points. It is shown in [39] that all of the previous concepts are special cases of this latter one. 15 Ang et al. [40] consider single-item 5 and 6 inventory systems with discrete demand processes. They come up with the fact that, despite the continuous approximations, convexity properties do not hold in discrete space, at least in the sense of L?-convexity. 1.4 Contributions and Structure This thesis, partly shows that L?-convexity does not hold for the cost function presented in Lu and Song [1] which casts doubt on using the greedy algorithms such as the steepest descent method that Lu and Song [1] used for finding the optimum policy. It also shows that the ellipsoid method that Lu and Song [1] proposed for solving the minimization problem may not return an optimum point, since the correctness of this algorithm relies on L?-convexity [41]. However, the cost function still has nice properties which make it possible to adopt a pseudo-polynomial algorithm to find a global minimum. Chapter 2 gives an overview of required mathematical background. We introduce different notions of convexity in discrete space and based on that we will reiterate related algorithms for minimization of classes of functions such as L?-convex and Coordinatewise-convex submodular functions. In Chapter 3 we will explain the inventory model used in Lu and Song [1], in more details. We will show that their model is not -convex at all (it is not L?-convex as a special case). Yet, we will demonstrate that their cost function is a coordinatewise-convex submodular function and its minimum point can be found using an algorithm in Chapter 2. 5 is a type of policy in a single-item continuous review inventory system where is the reorder point and is the order quantity. 6 is a type of policy in a single-item periodic review inventory system with a Poisson demand, where is the reorder interval and is the order-up-to level. 16 17 Chapter 2: Mathematical Background 2.1 A Brief Review on Discrete Convexity Analysis Discrete Convexity Analysis is a new approach for analyzing optimization problems on discrete or combinatorial structures using the ideas of convexity and convex functions from continuous optimization. In this chapter we want to review the concepts that are most relevant to our topic. An Optimization Problem has the following standard form (2-1) Solving such problem is either to find that has the minimum value of the given function among the members of the given set of or to report that such does not exist. The function is called the objective function and the set is called the feasible set. In continuous optimization, a convex program refers to an optimization problem in which is a convex set and is a convex function. is convex when all the points on the line segment joining any two points and in are contained in . Mathematically (2-2) The function defined on the convex set is convex when for any two points and in and for any scalar the following inequality holds 18 (2-3) One of the most important properties of convex programs is that the local optimality guarantees global optimality. This property makes it possible to find the solution of the optimization problem using descent algorithms. Again consider (2-1). When some of the variables in an optimization problem must take their values from a discrete set or when an optimization problem is defined on a combinatorial structure we are confronted with a discrete optimization problem. 2.2 L?/M?/D-convexity In this section we review L?-convexity and M?-convexity in more detail. Then we revisit -convexity and its relationship with the former definitions. First of all we need to introduce some basic definitions. Let { } The characteristic vector of a subset is denoted by { } and is defined as , (2-4) Note that { } for an integer In the following for a function is the subset of for which the value of function is finite. In other words { | } (2-5) For a vector we define? ? as the vector obtained by rounding up the components of to the nearest integer. In other words ? ? is such that 19 ? ? ? ? (2-6) where index represents the component of the vectors. Similarly ? ? is equal to a vector in obtained by rounding down the components of to the nearest integer, i.e., ? ? ? ? (2-7) Last of all, the positive support of a vector , denoted by , is the set of all indices for which the corresponding component is positive. In other words { | } (2-8) Similarly we define the negative support as follows { | } (2-9) Now it is time to introduce M?-convex functions. A function is an M?-convex function if for any and for any the following inequality holds { ( ) ( )} (2-10) Roughly speaking, this property does not allow any point which is not a global minimum to be locally minimal. In other words, for any candidate point in , we can choose a point in its neighborhood which is closer to the global minimum and has a smaller value of than that of the candidate point. To get a better sense, if we form the inequality (2-10) for any candidate point in such as and the global minimum then there is always a point, neighbor to , of the form or for some and that is closer to and enjoys a smaller value of . More precisely, it is shown in [32] that for an M?-convex function if is such that 20 { ( ) (2-11) then for any In other words in an M?-convex function, local optimality with respect to this particular neighborhood, is equivalent to global optimality. Another interesting type of convexity is L?-convexity. A function is an L?-convex function if for any pair of points the discrete midpoint property holds: for all following inequality holds (? ?) (? ?) (2-12) There is an equivalent characterization of L?-convexity ( [32] Theorem 7.7) which is more useful for the purpose of this section: A function is an L?-convex function if for all with the following inequality holds (2-13) where { }. For an L?-convex function local optimality (for a particular neighborhood) guarantees global optimality. More precisely, if is an L?-convex function and for which (2-14) then for all ( [32], Theorem 7.14 ). If we pay attention to the definition and optimality criteria in M?-convexity and L?-convexity we find out that in each of them there is a particular concept of locality. In an M?-convex function for point to be the global minimum it suffices that the value of function be at most equal to those values at points in { | } { | } A 21 similar case happens for an L?-convex function with { | } It gives us the idea of defining neighborhood in such a way that we can reach a more general definition of convexity on lattice space. Ui [39] introduces a nice generalized definition of neighborhood for this purpose and gives a general notion of convexity based on that locality. Let7 { } { } be such that { | } and for all we have Now for any let { | }. The subsets { | } { | } and { | } are two examples of such neighborhoods that lead to and respectively. For define { | } where for each we have { } and { } A function is a -convex function if for all with the following inequality holds (2-15) If is a -convex function then is a -local minimum of if and only if is a global minimum of In other words ( ) (2-16) then for all ( [39], Proposition 1) As we mentioned in section 1.3, Ui [39] characterized L?-convexity as a special case of -convexity under the setting equal to { | }. Furthermore convex 7 The vector in with all components equal to zero is denoted by 22 functions may be the most general known class of discretely convex functions, for which the local minimum points are guaranteed to be global minimum. 2.3 Computational Importance of Discrete Convexity There are two types of algorithms for minimization of L?-convex functions; one is due to Favati-Tardella [30] and runs in pseudo-polynomial time [42], the other is a steepest descent algorithm developed by Murota [43] which also runs in pseudo-polynomial time. The later finds a local minimum of the L?-convex function in a greedy approach. One simple sketch of this minimization algorithm is as follows: Algorithm SDLMIN Steepest Descent algorithm for L?-convex function Step 0: Start from an arbitrary vector . Step1: Find { } and nonempty which minimize Step 2: If then return as the minimizer of and stop. Step 3: Substitute and go to Step1. If we have an upper bound ? on the solution to the minimization problem, in other words we have ? where is the minimum point of function then a simpler version of this algorithm can be used [1], which is: Algorithm MSDLMIN Modified Steepest Descent algorithm for L?-convex function starting from an upper bound ? Step 0: Start from an upper bound vector ? . Step1: Find a nonempty which minimize Step 2: If then return as a minimizer of and stop. Step 3: Substitute and go to Step1. 23 It is not hard to check that these algorithms terminate and return the minimizer of an L?-convex function by using the alternative definition for L?-convex functions in the previous part. The running-time discussion can be found in Murota [32]. A function is a submodular function if for all the following inequality holds (2-17) Let be an arbitrary set and denote the set of all subsets of A function is a submodular set function if for all following inequality holds (2-18) Submodular set functions are special cases of submodular functions. For example, for a submodular function if we define (2-19) then will be a submodular set function. Given that an L?-convex function is also submodular [34] Step 1 in SDLMIN and MSDLMIN is indeed a submodular function minimization problem. McCormick [44] has is a nice review on the algorithms in the literature for this problem. Lu and Song [1] for this minimization problem, have suggested using the polynomial algorithm developed in Iwata [45] which leads to a running time of ( ), where is an upper bound on the time-complexity of evaluating Lu and Song [1] showed that the overall complexity of the 24 modified algorithm with an upper bound ? is of where denotes { ? } Based on submodularity of if we use the algorithm developed in Orlin [46] the time-complexity of Step 1 will be . Therefore the overall complexity is of ( ) Apparently, depends on the method we use to find the value of the function Furthermore, it is obvious that we need to find an upper bound for the optimum point as good as possible because its size directly affects the efficiency of the algorithm that we implement. Because of the dependence of running time on the algorithm is pseudo-polynomial. Similar greedy methods can be designed for minimization of -convex functions. These methods may use the local optimality criteria we discussed earlier in section 2.2. There is also another algorithm proposed by Favati-Tardella [30] for minimization of L?-convex function, which is pseudo-polynomial in the worst case [41] but can be implemented easily. The algorithm takes a L?-convex function [ ?] (where and ? are given lower bound and upper bound for the minimum point of with ?) and is guaranteed to return a global minimum of the function [41]. Algorithm FTLMIN Favatti-Tardella algorithm for L?-convex function over an interval [ ?] Step 0: Start from an upper bound vector ? and lower bound vector set ? Step 1: For each find [ ] which minimizes and update Step 2: For each find [ ] which minimizes and update Step 3: Find a nonempty which minimizes ; if return as a global minimum; otherwise update Step 4: Find a nonempty which minimizes if return as a global minimum; otherwise update and go to Step 1. 25 As we see through these four steps, at any time, the algorithm tries to reduce the size of the current searching domain in which an optimum point exists. This reduction in size of the domain takes place by increasing the lower bound and decreasing the upper bound at each step through a minimization of on either an edge of the searching domain (Step 1 and 2) or on a unit-size hypercube, contained in the searching domain, around the endpoints of that domain (Step 3 and 4). The size reduction of the searching domain is done in such a way that it always contains at least one global optimum of the function from the initial searching domain. In the next section we will discuss a modification of this algorithm, which is useful for minimization problem for a larger class of functions. 2.4 Coordinatewise-Convex Submodular Functions A function is discretely convex in each variable if it satisfies the midpoint property in any coordinate direction; i.e. for each if { } we have (2-20) A coordinatewise-convex submodular (CCS) function is a function which enjoys two properties: (1) discrete convexity in each variable; (2) submodularity. L?-convex functions form a subclass of CCS functions [41]. As we said in the previous section, there is a modification of FTLMIN algorithm for CCS function which does not necessarily find the global minimum of the CCS function but outputs an integer interval which is guaranteed to contain a global minimum [41]. In the following section we describe the modified algorithm to reduce the search interval to which a global minimum of the CCS function belongs. 26 2.4.1 Reduction Algorithm The modified algorithm proposed by Favati-Tardella [30] and revisited by Murota [41] takes an interval [ ?] and returns a reduced interval [ ] which contains a global minimum of a submodular function Murota proves the correctness of the algorithm [41]. Algorithm RDCSUB Reduction algorithm for submodular function over an interval [ ?] Step 0: Start from an upper bound vector ? and lower bound vector set ? Step 1: For each find [ ] which minimizes and update Step 2: For each find [ ] which minimizes and update Step 3: Find a nonempty which minimizes and update Step 4: Find a nonempty which minimizes and update Step 3: If then output [ ] and stop. Otherwise, go to step 1. Obviously if the submodular function is also CCS, step 1 and step 2 are simply univariate convex optimization problems, which can be solved easily using a binary search. Moreover, steps 3 and 4 are submodular set function minimization problem that, as we discussed in section 2.2, can be done in polynomial time using submodular set-function minimization algorithms [44]. Now we need to find a global minimum of the submodular function in a shrunk interval found by RDCSUB algorithm. In the next section, in order to find a global minimum in this interval, we present a transformation method which reduces the problem of minimizing a submodular function over an interval to a minimization problem of a submodular set function 27 over a ring family. The later problem is well-known in the literature and there are efficient algorithms for solving it [44]. 2.4.2 Transformation Method For a finite set a ring family is a collection of subsets of closed under intersection and union. In other words, such that for any then and If where then [ ] { } is a bounded integer interval. For each and for each let define Now take { | } (2-21) Note that the size of is ? ? ? | | Also for any [ ] define { | } (2-22) We claim that { | [ ] } is a ring family over the finite set To see this, suppose that [ ] then we have and . But and are both in [ ] Now for a submodular function over the integer interval [ ] define the function ?over the finite set as follows: ?( ) [ ] (2-23) ? is a submodular set function, since for any [ ] we have ?( ) ?( ) ?( ) ?( ) ?( ) ?( ) (2-24) The only inequality in this expression holds since is submodular. Simply the set of minimizers of within [ ] corresponds to the set of minimizers of ? over through relationship (2-23). 28 2.4.3 Proposed Algorithm So far we have reduced the CCS function minimization problem to a minimization problem for a submodular set function over a ring family, which can be solved using well known algorithms in the literature [44]. Based on what we have seen earlier in this section, the following algorithm can be used to find the minimum point of a CCS function [41]. Algorithm CCSMIN Algorithm for minimizing CCS function over an interval [ ?] Step 1: Apply Reduction Algorithm for submodular function over an interval [ ?] to get a reduced integer interval [ ] Step 2: Transform over [ ] to ? over the ring family Step3: Minimize ?over using any minimization algorithm for submodular set function over a ring family Step 4: Return corresponding [ ] as a minimizer of over [ ] We expect that is significantly smaller than [ ?] although there is still no theoretical basis for it [41]. At the end we need to emphasize that the running time of this algorithm is polynomial in ? ? ? | | To sum up, in this chapter we briefly reviewed notions of discrete convexity with a focus on L?-convexity. Then we studied two different algorithms for L?-convex minimization from the literature. In the next chapter we are going to study the inventory model described in Lu and Song [1] and we will show that their conclusion about L?-convexity of the cost function is not correct. However, they refer to MSDLMIN and FTLMIN algorithms to find the optimum point of their cost function under the assumption of L?-convexity. Thus we cannot expect that these 29 proposed algorithms, for finding the optimum policy, are able to work correctly for their cost function. Fortunately, we will see that their cost function is a CCS function and therefore CCSMIN algorithm can be used to find its optimum point. 30 Chapter 3: Order-Based Inventory System 3.1 Model Specification In the inventory model that Lu and Song [1] consider, the set of items is denoted by { } and the set of order-types is denoted by Each order is a subset of items required for fulfillment of that order type. Naturally is defined as the set of all order-types which require item for their fulfillment, i.e. { } We have assumed that each order type requires at most one unit from each item. A fixed probability is assigned to each order-type, showing the likelihood of each order to be of type Obviously ? We assume that the arrival times of each order follow a Poisson process of rate and thus the arrival times of order-type follow a Poisson process of rate . If denotes the item ?s rate of arrival then ? The inventory is controlled under continuous review. If an order arrives and all of its required items are in stock then the order will be satisfied. Otherwise, if there is not enough inventory on-hand of some of the items then the remaining items will be set aside as committed inventory, until those missing items arrive. In other words, if an order-type arrives and the items in subset are not in stock, the other items, say , would be set aside until all of the items in arrive. Consequently, these items cannot be used in fulfilling other order-types, even if they can completely fulfill an order-type which arrives later. In other words, 31 these items are ?earmarked?8 so that they can complete only the order-type to which they are assigned. As we said in section 1.3, this type of order fulfillment is known as First-Come-First-Served (FCFS) and is assumed in the Lu and Song [1] model, yet one may adopt other policies to get better results [20]. We also assume that the assembly time for every order-type is insignificant, thus each order is fulfilled immediately after all of its items are in stock. The replenishment times for item is denoted as Lu and Song [1] assume that are i.i.d. random variables each with time invariant pdf and cdf At time item has units on order. Based on our assumptions for replenishment time and order arrivals, we can assume that each forms an queue with a demand process identical to order arrivals of item . The random process ( ) is defined as the vector of joint demands on order. Lu et al. [18] show that converges to a vector and derive a nice formula for the probability generating function of as follows *? ? (?* ( )+ ) + (3-1) The inventory on hand of item , is the number of units of item that are in stock and not backlogged for any demand. These items can be assigned to any order type that require item to be fulfilled. Similarly, denotes the number of backorders assigned to item The inventory position of item is derived from the following formula [1] (3-2) 8 Lu and Song [3] refer to these items as backlogged items 32 and is controlled by a base-stock policy: When a demand arrives, order units of item if is less than and order nothing, otherwise. In the following proposition we will see that the inventory position is always equal to if it is set to this number at the beginning. Proposition I. Because of the base stock policy, if is set to at the beginning, then it always equals to Proof. A direct consequence of the policy is that the inventory position never goes below We can also show that this quantity never goes above Clearly, at any instance of time, at most one of the two variables and is nonzero. Moreover, at every replenishment of item (i.e. a unit decrease in ) either the inventory on hand increases by one unit, or the number of backorders decreases by one. Therefore at any replenishment is unchanged. In addition, let?s consider an instance of time when If an order type including item is placed, either there is at least one unit of item in stock which is immediately backlogged, or there is nothing on hand. The former case leads to one unit decrease in and the latter leads to one unit increase in the number of backorders, Clearly, decreases by one unit in both cases, leading to an order placement of item which makes equal to its previous value through adding one unit to Therefore is always equal to Proposition II. The number of backorders and inventory on hand at any time is derived from the following formulas: [1] [ ] (3-3) [ ] (3-4) 33 Proof. To show this, we again use the formula (3-2) and the fact that at any time both of nonnegative variables and cannot be positive simultaneously. If then therefore setting to zero in the formula yields Similarly, if then Finally the trivial case forces and to be zero, because they cannot be positive at the same time. The steady state levels of and are denoted by and respectively. Propostion II implies that Since converges to thus in steady state [1] [ ] (3-5) [ ] (3-6) Each backorder of item is due to an unsatisfied demand of a particular order-type. Similar to [1] we define for each item { (3-7) It is worth mentioning that the sequential order of the index that we use to label unit backorders here, corresponds to the time order of different order-types. In other words, because of the FCFS scheme, the demand of item belongs to the arrived order-type in the pile of orders that are waiting for item Obviously, in the pile of items that are placed but have not arrived yet, the last units are those not assigned to any backlogged order and placed only in order to fill the base-stock level. Now we can define, for item the number of backorders due to order-type denoted by as follows [1] 34 ? [ ] (3-8) The number of unfulfilled demands of type at any time is the maximum among the number of backorders due to each of its required items. In other words, as in [1] { } (3-9) Example I. We consider an inventory system with two products {P, Q}, where the demand for product P follows a Poisson process with rate and the demand for product Q follows another Poisson process with rate . There are two types of components denoted by {1, 2}, where product P requires both components 1 and 2 while product Q requires only component 1. Assume that the replenishment times through all components are identical and equal to the constant Let?s find the backorders due to item for six different base stock policies { } { }. These policies are the lattice points on the rectangle shown in Figure 1-1. Figure -1 sample lattice points in evaluation of expected backorders for different policies First of all based on the notations provided in [1] 35 { } ,? [ ] ? [ ] - (3-10) At any time we have: ? (3-11) Since each of the components in an order-type has to wait the same amount of time to be replenished, they come to the outstanding orders queues at the same time. They also leave at the same time. Each unfulfilled order of type adds exactly 1 to both sides of the equation above, while each order of type adds zero to both sides. In the case of there must be neither order nor waiting to be satisfied, therefore when and again the above equation holds. On the other hand, as we have only two items and item 2 only comes with order ? [ ] [ ] (3-12) Note that thus [ ] and we get { } ,? [ ] ? [ ] - (3-13) In order not to get confused about the summations of the form ? [ ] , let?s state a simple but important proposition. Proposition III. For any integer and for any index and order-type the equality below holds: [ ] (3-14) Where 36 Proof. ? [ ] ? [ ] { [ ] (3-15) Therefore setting we get ? [ ] ( ? [ ] ) [ ] ( ? ) (3-16) Which means . Also thus Now consider . Using the results we obtained above { } { [ ] } (3-17) { } { [ ] } [ ] (3-18) And finally [ ] and , [ ] [ ] - (3-19) As the final point of this example, we see that the Bernoulli random variables are not probabilistically independent from For example, set If then with probability one for any Yet in the case of the probability of is nonzero at least for some of the s. It seems that such implicit assumption of independence, among parameters of different components, has caused one of the gaps in the proof of Proposition (1.c) of Lu and Song [1]. We will discuss this issue in more detail in section 3.4 37 3.2 Cost Function and Optimum Policy One of the key assumptions in Lu and Song?s model [1] is that the inventory holding costs and backorder costs are linear. For each order-type we define as the cost of a backlogged unit of order-type Similarly, for each item we define as unit inventory holding cost. We should consider that the inventory holding costs are due to (1) Committed inventory : items that are earmarked and put aside to take part in a backlogged order-type. (2) Uncommitted Inventory : items that are currently in stock and not committed to any order. We already knew these items as inventory on hand of item Proposition IV. At any time, the committed inventory of item is derived from [1] (? ) (3-20) Proof. Consider an order-type which includes item i.e. Among backorders of this order-type, units are waiting for item and the remaining, say are waiting for some items other than Therefore The total amount of committed inventory of item can be derived from adding up all among the order-types containing item Thus ? ? (? ) (? ) (3-21) But ? ? ? since for each and the term is 1 for one and only one . 38 If denotes the steady state committed inventory of item then the expected inventory level of item will be [1] { } ,[ ] *(? ) +- , (? )- [ ] ? (3-22) To sum up, the expected total cost can be written as in [1] ? [ ] ? [ ] ? ? [ ] ? (? [ ] ) ? [ ] (3-23) We can rewrite [1] the third term by interchanging sums as follows: ? (? [ ] ) ? ? [ ] ?? [ ] (3-24) In order to get a nice expression for expected cost let define ? ? which implies that ? ? [ ] ? [ ] ? ? [ ] . The cost function becomes [1] ? ? ? [ ] (3-25) where ? [ ] We think of [ ] as a constant with respect to vector since as we said earlier in (3-1), is independent from base stock levels. The objective is to find a nonnegative vector of base stock levels which minimizes the expected total cost In general, such integer programming problems 39 are not easy to solve. Yet, finding some nice characteristics may help solving this problem more efficiently. Lu and Song [1] claim that is a L?-convex function. They give a proof of the discrete midpoint property for the cost function and conclude that the global optimum can be found by either the MSDLMIN algorithm or FTLMIN algorithm that we discussed in the previous chapter. But I will show that the proposed proof of the discrete midpoint property is not valid. To show that may not be L?-convex, suppose and . It suffices to show the following inequality: [ ] [ ] [ ] [ ] (3-26) As in Example I, assume that the replenishment times through all components are identical and equal to constant From the results of that example we have [ ] [ ] [ ]. Now, we compare [ ] and [ ]. Clearly, [ ] [ ]. We now proceed to show that this inequality is strict. Fix time t, and suppose that there is no demand in the interval ] and the demand realization during the interval ( ] is one unit of Q followed by one unit of P. Clearly, the event occurs with a strictly positive probability. Furthermore, conditioned on this event, the system managed with the base stock vector has no backorder at time whereas the system managed with has one unit of P backordered at (this happens because a unit of component 1 is used to satisfy demand for Q before another unit can be used for P by the FCFS allocation 40 policy). It follows that [ ] [ ]. Putting these results together, we obtain the required inequality, which implies that is not always L?-convex.9 This leads to a barrier for using a steepest descent algorithm such as MSDLMIN that Lu and Song [1] have used to find the optimum policy for the inventory system under discussion. Indeed, the algorithm may return a local optima which is not the global optimum of the cost function. Now let?s check the M?-convexity of the cost function. Consider again the inventory system described above. Set , and The strict inequality in (3-26) suffices to make sure that is not always M?-convex, since Therefore, is not always M-convex either. The simple inventory system we defined above, with a little change, can also show that the cost function may have no type of -convexity. Assuming that and, without loss of generality, ignoring the constant we get [ ] (3-27) Before going further we need some preliminaries. The following proposition gives an intuition about the relationship between the steady state backorders caused by adopting policies that are due to adjacent lattice points. In other words, we seek a meaningful relation between [ ] for two policies and where ? ? 9 The reader can refer to section 3.5 to see that this non-convexity occurs infinitely many times in the cost function of the simple 2-component system described above. More precisely, for an arbitrary policy we will find sufficiently large where the midpoint property does not hold for the pair where and 41 Proposition V. Let be a random variable and and be integer functions of where { }. { } { } (3-28) Then [ ] { } { } Proof. If , obviously . Otherwise, if we assume , then , (3-29) Therefore is a binary random variable with a mean equal to { } { }. As a straight-forward consequence of this proposition [ ] [ ] { } { } (3-30) Let { } If we assume that then is greater than zero. We can choose and such that In this case [ ] [ ] (3-31) Thus and Furthermore, based on what we had in example 1 it is not hard to check that [ ] [ ] (3-31) We will use these results in finding a pair of points which shows that the cost function is not convex. Consider the lattice points on the rectangle with the and as its 42 upper-right-most point and lower-left-most point, respectively. For any permitted { } containing { } we have { } (3-32) { } (3-33) Now simply { } (3-34) { } (3-35) We want to show that [ ] [ ] [ ] [ ] (3-36) This strict inequality, if holds, shows that for any arbitrary permitted { } the inequality (3-37) holds and thus the cost function is not -convex. Use the results of example I and (3-30) to get [ ] [ ] [ ] [ ] . So the left-hand-side of (3-36) is zero. On the other hand, using the fact that ? and the above lemma we get [ ] [ ] , [ ] ? [ ] [ ] - { } { } (3-38) 43 But the second term is zero since ? thus if then Therefore [ ] [ ] { } (3-39) If we choose sufficiently large then the event { } occurs with a positive probability. Thus the right-hand-side of (3-36) is positive and our proof is complete. Since we disproved the -convexity property of cost function for a general choice of we conclude that the cost function does not obtain any known type of convexity in discrete space such as M?-/L?-/M-/L-convexity. As a result, we should not expect the steepest descent algorithms to find the optimum policy, because these greedy algorithms may find the local optima of the cost function yet there is no guarantee that these optima are globally optimum. 3.3 Cost Optimization Algorithm So far we have realized that the MSDLMIN algorithm is not sufficient for exact minimization of the cost function. This is one of the algorithms proposed in Lu and Song [1] for finding the optimum policy under the misunderstanding that the cost function is L?-convex. They also propose another algorithm similar to FTLMIN algorithm for L?-convex function minimization that we discussed in chapter 2. Since the cost function is not L?-convex this algorithm is not appropriate for cost optimization of the model, as well. Fortunately, the cost function is a CCS function through the following propostion. Proposition VI. (a) The cost function is coordinatewise convex. 44 (b) The cost function is submodular. Proof. ( [1], Proposition 1, (a, b) Given that the cost function is CCS we can find an optimum policy using an algorithm similar to CCSMIN in chapter 2. 3.4 Gaps in The Proof In this part, we want to show the gaps in the proof of L?-convexity of the cost function in Lu and Song [1]. Based on equation (5) in Lu and Song [1] if order-type consists of four components then we have [ { }] (3-40) It is claimed in the proof of Proposition 1(c) of Lu and Song [1] that in order to show the L?-convexity it suffices to show for a four-component order type that (3-41) For verifying this inequality the following reasoning has been used by the authors: (3-42) Let?s assess these inequalities one by one, in our words. For the first inequality, it suffices to say that 45 (3-43) The validity of first step is due to coordinatewise convexity of The second step is equivalent to , [ ] { }- , [ ] { }- (3-44) But this holds since { } { } due to the monotonicity. Although the first inequality in (3-42) is true, the method used in Lu and Song [1] to verify it is not valid. Indeed, it is claimed in Lu and Song [1] that [ { }] [ { }] , [ ] - { { }} (3-45) The true version of this equation is as follows [ { }] [ { }] , [ ] { }- (3-46) If both (3-45) and (3-46) hold, the event , [ ] - must be independent from { { }} which is not true in general. It seems that Lu and Song [1] 46 have derived this statement based on the independence of Bernoulli random variables Even though are independent across (different slots in a single pile) they are not necessarily independent from the parameters of other piles such as . In Example 1 we saw a simple system for which the independence assumption in deriving (3-45) from (3-46) is not true, which shows one of the gaps in the Lu and Song?s proof [1] of the first inequality in (3-42). So far we have seen that the first inequality in (3-42) holds with a different reasoning from what we have in the proof of Proposition 1(c) of Lu and Song [1]. More importantly, we will see in Example II that the second inequality of (3-42) does not always hold. The second inequality is equivalent to (3-47) Simplifying both sides based on the propositions III and V from previous parts we get , [ ] { }- , [ ] { }- (3-48) To show the possible flaw in this inequality the following example is useful. Example II. Let denote the four-component demand type described above. Consider insignificant replenishment times for components 1 and 3, say constant replenishment times close to zero ( Then we can simplify the system to a smaller one consisting of two items 2 and 4. Now assume that items 2 and 4 have identical and constant nonzero (sufficiently large) replenishment time Furthermore, assume that there is only one other 47 demand type in this system which consists only of component {2}. A similar scenario to Example I holds in this example. Set and Similar to Example I we have , [ ] { }- { } , [ ] - { } (3-49) The second equation is because since every outstanding demand for component 4 is due to demand-type In addition similar to the discussion in Example I we have ? ? (3-50) And [ ] The last event has probability zero since with probability one ? (3-51) On the other hand , [ ] { }- , [ ] - { [ ] * [ ] + [ ] } , [ ] [ ] [ ] - (3-52) We want to show that this probability is greater than zero. Consider the events { } (3-53) , [ ] [ ] [ ] - (3-54) 48 Obviously takes place with positive probability (Consider first demand of type and the second demand of type On the other hand and thus As we saw in this example, there might be some cases in which the second inequality in (3-42) does not hold. Unfortunately Lu and Song [1] does not provide any proof for this part. It is only stated that this inequality could be shown with a similar reasoning to that of the first inequality. 3.5 A Remark on L?-Convexity of The Cost Function In example I, we considered an inventory system of two components. Next, we observed in (3-26) that by setting , the cost function of this system does not satisfy the midpoint property at least for the points In this part we want to show that for any choice of there is at least one where and the cost function fails to satisfy the midpoint property for the points and It is a means to make sure that the non-convexity observed in the cost function is not limited to a finite set of base stock policies and might be resolvable for sufficiently large inventory policies. In other words, the midpoint property does not hold for infinitely many pairs of points even for the cost function of this two-component inventory system. First of all, suppose and let Similar to (3-26), we want to show that [ ] [ ] [ ] [ ] (3-55) Which is equivalent to [ ] [ ] [ ] [ ] (3-56) Using Propositions V and III, we simplify the above expression into 49 , [ ] ? [ ] [ ] - , [ ] ? [ ] [ ] - (3-57) Instead of this, we can show for any ( ) (3-58) Where , [ ] ? [ ] [ ] | - (3-59) , [ ] ? [ ] [ ] | - (3-60) Note that we need to consider only since almost surely In order to prove inequality (3-58), we proceed with a combinatorial interpretation of the events and which gives us an easy way to compute the corresponding probabilities. Event { } says that we have exactly orders of type { } in the pile of outstanding orders of either item (as the replenishment lead times are assumed to be identical). The remaining outstanding orders of item { } are due to order type { } It is not surprising that every outstanding order of item { } is due to order type { } There are ( ) different possible arrangement of orders which results in { } and all of them is seen with the equal probability. We claim that 50 ? ( ) ( ) ( ) (3-61) To verify this, assume that there are ( ) ( ) arrangements in which outstanding orders of type will be received (and have been put) before the item in the pile of item { }and also the item in this pile is of type Obviously the remaining order-type among outstanding orders of item { } will be received after the item. Since for outcomes in we want at least order-type among the first items of pile { } and given that there is no prevalence in the order of receiving the corresponding demands, we sum all the terms for possible values of and end up with (3-61). Similarly ? ( ) ( ) ( ) (3-62) We need only to show that ? ( ) ( ) ? ( ) ( ) (3-63) Letting in the left hand side and in the right hand side, we have the following form of the above expression ? ( ) ( ) ? ( ) ( ) (3-64) Now use Pascal?s formulas ( ) ( ) ( ) and ( ) ( ) ( ) to get 51 ? ( ) ( ) ? ( ) ( ) ? ( ) ( ) ? ( ) ( ) (3-65) Note that in the Pascal?s formula we assume conventionally ( ) for and therefore we can cancel the first terms from both sides and end up with ? ( ) ( ) ? ( ) ( ) (3-66) Now use again ? ( ) ( ) ? ( ) ( ) (3-67) Cancelling out repeated terms in both sides will give us ( ) ( ) (3-68) which holds when This completes the proof of our claim (3-56). In this section we showed that the midpoint property for a simple cost function does not hold for infinitely many pairs of points, which makes us sure that even with removing any bounded subset of lattice points, the cost function will not become L?-convex for the remaining part of its domain. 52 Chapter 4: Conclusion The main focus of this study was on the inventory model described in Lu and Song [1] work. Based on this model they derived a cost function for an assemble-to-order system in a continuous-time review scheme. In order to find the optimum policy they proposed two algorithms, the correctness of both of which relies on L?-convexity of the cost function. One of the algorithms is MSDLMIN and the other is FTLMIN. However, they were, mistakenly, assuming that their cost function is L?-convex. In this study we have shown why the cost function may not necessarily be L?-convex. Therefore the MSDLMIN may not work properly. More generally, we have shown that the cost function is not convex for any arbitrary notion of locality; a result which implies that such steepest descent algorithms that try to find a local minimum may not give a global minimum for this cost function at all. Another algorithm, FTLMIN, developed by Favati-Tardella [30], is also not appropriate for minimization of this cost function, since its correctness depends on L?-convexity. Yet, there is a modification of the FTLMIN algorithm, called RDCSUB, which can be used to reduce the size of the minimization problem. We discussed this modified algorithm and then showed that how one can solve the minimization problem using submodular set function minimization in pseudo-polynomial time. 53 Bibliography [1] Yingdong Lu and Jing-Sheng Song, "Order-Based Cost Optimization in Assemble-to-Order Systems," Operations Research, vol. 53, pp. 151-169, January/February 2005. [2] Kathleen Kerwin, "At Ford, E-Commerce Is Job 1," Business Week, pp. 74-78, February 2000. [3] Jing-Sheng Song and Paul Zipkin, "Supply Chain Operations: Assemble-to-Order Systems," Handbooks in Operations Research and Management Science, vol. 11, pp. 561-596, 2003. [4] Kaj Rosling, "Optimal Lot-Sizing for Dynamic Assembly Systems," in Multi-Stage Production Planning and Inventory Control, Sven Axs?ter, Christoph Schneeweiss, and Edward Silver , Eds.: Springer Berlin Heidelberg, 1986, pp. 119-131. [5] Andrew J. Clark and Herbert Scarf, "Optimal Policies for a Multi-Echelon Inventory Problem," Management Science, vol. 6, no. 4, pp. 475?490, July 1960. [6] Steven Nahmias and Charles P. Schmidt, "An efficient heuristic for the multi-item newsboy problem with a single constraint," Naval Research Logistics Quarterly, vol. 31, no. 3, pp. 463?474, September 1984. [7] J?r?mie Gallien and Lawrence M. Wein, "A Simple and Effective Component Procurement Policy for Stochastic Assembly Systems," Queueing Systems, vol. 38, no. 2, pp. 221-248, June 2001. [8] Feng Cheng, Markus Ettl, Grace Lin, and David D. Yao, "Inventory-Service Optimization in Configure-to-Order Systems," Manufacturing & Service Operations Management, vol. 4, pp. 114-132, 2002. 54 [9] Kenneth R. Baker, Michael J. Magazine, and Henry L. W. Nuttle, "The Effect of Commonality on Safety Stock in a Simple Inventory Model," Management Science, vol. 32, pp. 982-988, August 1986. [10] Susan H. Xu, "Structural Analysis of a Queueing System with Multiclasses of Correlated Arrivals and Blocking," Operations Research, vol. 47, pp. 264-276, March/April 1999. [11] Narendra Agrawal and Morris A. Cohen, "Optimal material control in an assembly system with component commonality," Naval Research Logistics, vol. 48, no. 5, pp. 409-429, August 2001. [12] Jing-Sheng Song, "On the Order Fill Rate in a Multi-Item, Base-Stock Inventory System," Operations Research, vol. 46, no. 6, pp. 831-845, November/December 1998. [13] Yal?in Ak?ay and Susan H. Xu, "Joint Inventory Replenishment and Component Allocation Optimization in an Assemble-to-Order System," Management Science, vol. 50, pp. 99-116, January 2004. [14] Warren H. Hausman, Hau L. Lee, and Alex X. Zhang, "Order response time reliability in a multi-item inventory system," European Journal of Operational Research, vol. 109, pp. 646-659, 1998. [15] Yigal Gerchak and Mordechai Henig, "Component commonality in assemble-to-order systems: Models and properties," Naval Research Logistics, vol. 36, no. 1, pp. 61-68, February 1989. [16] Jing-Sheng Song and Yao Zhao, "The value of component commonality in a dynamic inventory system with lead times," Manufacturing & Service Operations Management, vol. 11, no. 3, pp. 493-508, 2009. 55 [17] Jing-Sheng Song, Susan H. Xu, and Bin Liu, "Order-Fulfillment Performance Measures in an Assemble-to-Order System with Stochastic Leadtimes," Operations Research, vol. 47, pp. 131-149, January/February 1999. [18] Yingdong Lu, Jing-Sheng Song, and David D. Yao, "Order Fill Rate, Leadtime Variability, and Advance Demand Information in an Assemble-to-Order System," Operations Research, vol. 51, pp. 292-308, March/April 2003. [19] Wenhui Zhou and Xiuli Chao, "Stein?Chen approximation and error bounds for order fill rates in assemble-to-order systems," Naval Research Logistics, vol. 59, no. 8, pp. 643?655, December 2012. [20] Yingdong Lu, Jing-Sheng Song, and Yao Zhao, "No-Holdback Allocation Rules for Continuous-Time Assemble-to-Order Systems," Operations Research, vol. 58, no. 3, pp. 691?705, May?June 2010. [21] Erica L. Plambeck and Amy R. Ward, "Optimal Control of a High-Volume Assemble-to-Order System," Mathematics of Operations Research, vol. 31, pp. 453-477, August 2006. [22] Erica L. Plambeck, "Asymptotically Optimal Control for an Assemble-to-Order System with Capacitated Component Production and Fixed Transport Costs," Operations Research, vol. 56, pp. 1158-1171, September-October 2008. [23] Yingdong Lu, "Performance analysis for assemble-to-order systems with general renewal arrivals and random batch demands," European Journal of Operational Research, vol. 185, pp. 635?647, 2008. [24] Gregory A. DeCroix, Jing-Sheng Song, and Paul H. Zipkin, "Managing an Assemble-to-Order System with Returns," Manufacturing & Service Operations Management, vol. 11, 56 no. 1, pp. 144?159, Winter 2009. [25] Martin I. Reiman and Qiong Wang, "A stochastic program based lower bound for assemble-to-order inventory systems," Operations Research Letters, vol. 40, no. 2, pp. 89-95, March 2012. [26] Ke Fu, Vernon N. Hsu, and Chung-Yee Lee, "Approximation methods for the analysis of a multicomponent, multiproduct assemble-to-order system," Naval Research Logistics, vol. 58, pp. 685-704, October 2011. [27] Shih-Cheng Horng and Feng-Yi Yang, "Optimal base-stock policy of the assemble-to-order systems," Artificial Life and Robotics, vol. 17, no. 1, pp. 47-52, October 2012. [28] L. Jeff Hong and Barry L. Nelson, "Discrete Optimization via Simulation Using COMPASS," Operations Research, vol. 54, pp. 115-129, 2006. [29] Bruce L. Miller, "On minimizing nonseparable functions defined on the integers with an inventory application," SIAM Journal on Applied Mathematics, vol. 21, no. 1, pp. 166-185, 1971. [30] Paola Favati and Fabio Tardella, "Convexity in nonlinear integer programming," Ricerca Operativa, vol. 53, pp. 3-44, 1990. [31] Kazuo Murota, "Convexity and Steinitz's exchange property," Integer Programming and Combinatorial Optimization, vol. 1084, pp. 260-274, 1996. [32] Kazuo Murota, "Discrete convex analysis," Mathematical Programming, vol. 83, no. 1-3, pp. 313-371, January 1998. [33] Kazuo Murota and Akiyoshi Shioura, "M-convex function on generalized polymatroid," 57 Mathematics of Operations Research, vol. 24, no. 1, pp. 95-105, 1999. [34] Satoru Fujishige and Kazuo Murota, "Notes on L-/M-convex functions and the separation theorems," Mathematical Programming, vol. 88, no. 1, pp. 129-146, June 2000. [35] Paul Zipkin, "On the Structure of Lost-Sales Inventory Models," Operations Research, vol. 56, no. 4, pp. 937-944, July/August 2008. [36] Woonghee Tim Huh and Ganesh Janakiraman, "On the Optimal Policy Structure in Serial Inventory Systems with Lost Sales," Operations Research, vol. 58, no. 2, pp. 486-491, March/April 2010. [37] Zhan Pang, Frank Y. Chen, and Youyi Feng, "Technical Note?A Note on the Structure of Joint Inventory-Pricing Control with Leadtimes," Operations Research, vol. 60, no. 3, pp. 581-587, May/June 2012. [38] Lijian Lu, Jing-Sheng Song, and Hanqin Zhang, "Optimal and Asymptotically Optimal Policies for an Assemble-to-Order N-System," Working paper, 2012. [39] Takashi Ui, "A note on discrete convexity and local optimality," Japan Journal of Industrial and Applied Mathematics, vol. 23, no. 1, pp. 21-29, 2006. [40] Marcus Ang, Jing-Sheng Song, Mingzheng Wang, and Hanqin Zhang, "On properties of discrete (r, q) and (s, T) inventory systems," European Journal of Operational Research, vol. 229, no. 1, pp. 95-105, August 2013. [41] Kazuo Murota, "Minimizing Coordinatewise-convex Submodular Functions," Memorandum, July 2013. [42] Kazuo Murota, "On Steepest Descent Algorithms for Discrete Convex Functions," SIAM 58 Journal on Optimization, vol. 14, pp. 699-707, November 2002. [43] Kazuo Murota, "Algorithms in Discrete Convex Analysis," Math. Programming, vol. 83, pp. 313-371, 2000. [44] S. Thomas McCormick, "Submodular Function Minimization," in Handbooks in Operations Research and Management Science. Berlin: Elsevier Science Publishers, 2006, vol. 12, ch. 7, pp. 321?391. [45] Satoru Iwata, "A Faster Scaling Algorithm For Minimizing Submodular Functions," SIAM Journal on Computing, vol. 32, no. 4, pp. 833?840, 2003. [46] James B. Orlin, "A faster strongly polynomial time algorithm for submodular function minimization," Mathematical Programming, vol. 118, no. 2, pp. 237-251, 2009. [47] Kaj Rosling, "Optimal Inventory Policies for Assembly Systems under Random Demands," Operations Research, vol. 37, no. 4, pp. 565-579, July - August 1989.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On properties of the order-based cost function in assemble-to-order...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On properties of the order-based cost function in assemble-to-order systems Bolandnazar, Mohammadreza 2013
pdf
Page Metadata
Item Metadata
Title | On properties of the order-based cost function in assemble-to-order systems |
Creator |
Bolandnazar, Mohammadreza |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | One of the main results of "Order-Based Cost Optimization in Assemble-to-Order Systems" [1] by Y. Lu and J-S. Song, Operations Research, 53, 151-169 (2005) is Proposition 1 (c), which states that the cost function of an assemble-to-order inventory system satisfies a discrete convexity property called L♮-convexity. Based on this result, Lu and Song proposed two types of L♮-convex minimization algorithms for finding the optimum policy. We construct a simple assemble-to-order system for which the cost function fails to satisfy L♮-convexity. Using a similar system, we further show that the cost function may not enjoy a more general notion of discrete convexity property called D-convexity. Yet, because of some other properties of the cost function, one can still solve the cost optimization problem using other methods from the literature. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-10-25 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
IsShownAt | 10.14288/1.0102462 |
URI | http://hdl.handle.net/2429/45386 |
Degree |
Master of Science - MSc |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_fall_bolandnazar_mohammadreza.pdf [ 791.95kB ]
- Metadata
- JSON: 24-1.0102462.json
- JSON-LD: 24-1.0102462-ld.json
- RDF/XML (Pretty): 24-1.0102462-rdf.xml
- RDF/JSON: 24-1.0102462-rdf.json
- Turtle: 24-1.0102462-turtle.txt
- N-Triples: 24-1.0102462-rdf-ntriples.txt
- Original Record: 24-1.0102462-source.json
- Full Text
- 24-1.0102462-fulltext.txt
- Citation
- 24-1.0102462.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0102462/manifest