Transcription
Lectures in Supply-Chain OptimizationArthur F. Veinott, Jr.Management Science and Engineering 361Department of Management Science and EngineeringStanford UniversityStanford, California 94305
Copyright 2005 by Arthur F. Veinott, Jr.
Contents1 Introduction to Supply-Chain Optimization.11 Overview.12 Motives for Holding Inventories. 32 Lattice Programming and Supply Chains: Comparison of Optima.151 Introduction. 152 Sublattices in d 8 .173 Ascending Multi-Functions: Monotone Selections.214 Additive, Subadditive and Superadditive Functions. 225 Minimizing Subadditive Functions on Sublattices. 266 Application to Optimal Dynamic Production Planning. 273 Noncooperative and Cooperative Games: Competition and Cooperation in Supply Chains . 311 Introduction. 312 Nash Equilibria of Noncooperative Superadditive Games. 323 Core of Cooperative Linear Programming Game. 354 Convex-Cost Network Flows and Supply Chains: Substitutes/Complements/Ripples . 391 Introduction. 392 Ripple Theorem. 433 Conformality and Subadditivity. 464 Monotonicity of the Optimal Arc Flows in Arc Parameters. 525 Smoothing Theorem.566 Unit Parameter Changes. 607 Some Tips for Applications. 628 Application to Optimal Dynamic Production Planning. 645 Convex-Cost Network Flows and Supply Chains: Invariance . 711 Introduction. 712 Conjugates and Subgradients. 723 d -Additive Convex Functions. 744 Invariance Theorem for Network Flows. 765 Taut-String Solution.826 Application to Optimal Dynamic Production Planning. 836 Concave-Cost Network Flows and Supply Chains. 871 Introduction. 872 Minimizing Concave Functions on Polyhedral Convex Sets. 893 Minimum-Additive-Concave-Cost Uncapacitated Network Flows. 924 Send-and-Split Method in General Networks. 985 Send-and-Split Method in 1-Planar and Nearly 1-Planar Networks. 1056 Reduction of Capacitated to Uncapacitated Network Flows.1097 Application to Dynamic Lot-Sizing and Network Design.1108 94%-Effective Lot-Sizing for One-Warehouse Multi-Retailer Systems. 1167 Stochastic Order, Subadditivity Preservation, Total Positivity and Supply Chains. 1271 Introduction. 1272 Stochastic and Pointwise Order.1293 Subadditivity-Preserving Transformations and Supply Chains.1338 Dynamic Supply Policy with Stochastic Demands. 1371 Introduction. 1372 Convex Ordering Costs.1393 Setup Ordering Cost and (sß S ) Optimal Supply Policies.1404 Positive Lead Times.1525 Serial Supply Chains: Additivity of Minimum Expected Cost. 1546 Supply Chains with Complex Demand Processes.1579 Myopic Supply Policy with Stochastic Demands.1611 Introduction. 1612 Stochastic Optimality and Substitute Products. 1623 Eliminating Linear Ordering Costs and Positive Lead Times. 167i
MS&E 361 Supply-Chain OptimizationCopyright 2005 Arthur F. Veinott, Jr.iiContentsAppendix. 1691 Representation of Sublattices of Finite Products of Chains. 1692 Proof of Monotone-Optimal-Flow-Selection Theorem. 1733 Subadditivity/Superadditivity of Minimum Cost in Parameters. 1774 Dynamic-Programming Equations for Concave-Cost Flows.1795 Sign-Variation-Diminishing Properties of Totally Positive Matrices. 181References.185HomeworkHomework 11 Leontief Substitution Systems2 Supply Chains with Linear CostsHomework 21 Assembly Supply Chains with Convex Costs2 Multiple Assignment Problem with Subadditive Costs3 Characterization of Additive Functions4 Projections of Additive Convex Functions are Additive ConvexHomework 31 Monotone Minimum-Cost Chains2 Finding Least Optimal Selection3 Research and Development GameHomework 41 Computing Nash Equilibria of Noncooperative Games with Superadditive Profits2 Cooperative Linear Programming Game3 Multi-Plant Procurement/Production/Distribution4 Projections of Convex Functions are ConvexHomework 51 Guaranteed Annual Wage2 Quadratic Costs and Linear Decision Rules3 Balancing Overtime and Storage CostsHomework 61 Production Planning: Taut String2 Plant vs. Field Assembly and Serial Supply Chains: Taut String3 Just-In-Time Multi-Facility Production: Taut StringHomework 71 Stationary Economic-Order-Interval2 Extreme Flows in Single-Source Networks3 Cyclic Economic-Order-IntervalHomework 81 *%% Effective Lot-Sizing2 Dynamic Lot-Sizing with Shared Production3 Total PositivityHomework 91 Production Smoothing2 Purchasing with Limited Supplies3 Optimality of Ð ß WÑ PoliciesHomework 101 Supplying a Paper Mill2 Optimal Supply Policy with Fluctuating Demands
1Introduction to Supply-Chain Optimization1 OVERVIEWSupply Chains. The supply chains of large corporations involve hundreds of facilities (retailers, distributors, plants and suppliers) that are globally distributed and involve thousands ofparts and products. As one example, one auto manufacturer has 12 thousand suppliers, 70 plants,operates in 200 countries and has annual sales of 8.6 million vehicles. As a second example, theUS Defense Logistics Agency, the world’s largest warehousing operation, stocks over 100 thousand products. The goals of corporate supply chains are to provide customers with the productsthey want in a timely way and as efficiently and profitably as possible. Fueled in part by theinformation revolution and the rise of e-commerce, the development of models of supply chainsand their optimization has emerged as an important way of coping with this complexity. Indeed,this is one of the most active application areas of operations research and management sciencetoday. This reflects the realization that the success of a company generally depends on the efficiency with which it can design, manufacture and distribute its products in an increasingly competitive global economy.Decisions. There are many decisions to be made in supply chains. These includeì what products to make and what their designs should be;ì how much, when, where and from whom to buy product;ì how much, when and where to produce product;ì how much and when to ship from one facility to another;ì how much, when and where to store product;ì how much, when and where to charge for products; andì how much, when and where to provide facility capacity.1
MS&E 361 Supply-Chain OptimizationCopyright 2005 Arthur F. Veinott, Jr.2§1 IntroductionThese decisions are typically made in an environment that involves uncertainty about productdemands, costs, prices, lead times, quality, etc. The decisions are generally made in a multi-partyenvironment that includes competition and often includes collaborative alliances.Alliances lead to questions of how to share the benefits of collaboration and what informationthe various parties ought to share. In many supply chains, the tradition has been not to share information. On the other hand, firms in more than a few supply chains realize that there are important benefits from sharing information too, e.g., the potential for making supply chains moreresponsive and efficient.Inventories. Typically firms carry inventories at various locations in a supply chain to bufferthe operations at different facilities and in different periods. Inventories are the links betweenfacilities and time periods. Inventories of raw materials, work-in-process, and finished goods areubiquitous in firms engaged in production or distribution (by sale or circulation) of one or moreproducts. Indeed, in the United States alone, 2000 manufacturing and trade inventories totaled1,205 billion dollars, or 12% of the gross domestic product of 9,963 billion dollars that year(2001 Statistical Abstract of the United States, U.S. Department of Commerce, Bureau of theCensus, Tables 756 and 640). The annual cost of carrying these inventories, e.g., costs associatedwith capital, storage, taxes, insurance, etc., is significant—perhaps 25% of the total investmentin inventories, or 301 billion dollars and 3% of the gross domestic product.Scope. The conventional types of inventories include raw materials, work in process, andfinished goods. But there are many other types of inventories which, although frequently notthought of as inventories in the usual sense, can and have been usefully studied by the methodsdeveloped for the study of ordinary inventories. Among others, these include:ì plant capacity,ì equipment,ì space (airline seat, container, hotel room)ì circulating goods (cars, computers, books),ì cash and securities,ì queues,ì populations (labor, livestock, pests, wildlife),ì goodwill,ì water and evenì pollutants.Thus the scope of applications of the methods of supply-chain optimization is considerably widerthan may seem the case at first.2 MOTIVES FOR HOLDING INVENTORIESSince it is usually expensive to carry inventories, efficient firms would not do so withoutgood reasons. Thus, it seems useful to examine the motives for holding inventories. As we do so,
MS&E 361 Supply-Chain OptimizationCopyright 2005 Arthur F. Veinott, Jr.3§1 Introductionwe give examples briefly illustrating many of the more common motives as well as the methodsused to analyze them. We shall discuss only the case of a single facility and single party in theremainder of this section, reserving the complications arising from multiple facilities and partiesfor subsequent sections.It is helpful to begin by formulating and studying an 8-period supply-chain problem undercertainty. Let B3 , C3 and 3 be respectively the nonnegative production, end-of-period inventoryand given demand for a single product in period 3 œ 1ß á ß 8. Let -3 ÐDÑ and 23 ÐDÑ be respectivelythe costs of producing and storing D0 units of the product in period 3. We can and do assumewithout loss of generality that -3 Ð0Ñ œ 23 Ð0Ñ œ 0 for all 3. The problem is to choose productionand inventory schedules B œ ÐB3 Ñ and C œ ÐC3 Ñ respectively that minimize the 8-period costGÐBß CÑ " Ò -3 ÐB3 Ñ 23 ÐC3 ÑÓ8Ð1Ñ"subject to the stock-conservation constraintsÐ2ÑB3 C3 " C3 œ 3 ß 3 œ 1ß á ß 8and nonnegativity of production and inventories (the last to assure that demands are met as theyarise without backorders)Ð3 ÑBß C0where for simplicity we set C! C8 !.Network-Flow Formulation. The problem Ð1Ñ-Ð Ñ can be viewed as one of finding a minimum-nonlinear-cost network flow as Figure 1 illustrates. The variables are the flows in the arcsthat they label, the exogenous demands (negative demands are “supplies”) at nodes 1ß á ß 8 are%0B"1 "C"B#2 # Σ 3"B%B C#3 C 4 %Figure 1. Production Planning Networkthe given demands in those periods, and the supply at node zero is the total demand !3 3 in allperiods. The stock-conservation constraints Ð#Ñ are the flow-conservation constraints in the net-
MS&E 361 Supply-Chain OptimizationCopyright 2005 Arthur F. Veinott, Jr.4§1 Introductionwork. The flow-conservation constraint at node zero expresses the fact that total production in allperiods equals total demand in all periods. The flow-conservation constraint at each other node3 0 expresses the fact that the sum of the initial inventory and production in period 3 equals thesum of the demand and final inventory in that period.One important motive for carrying inventories arises when there is a temporal increase inthe marginal cost of supplying demand, i.e., -† 3 Ð 3 Ñ increases in 3 over some interval. (The derivative here is with respect to the quantity, not time.) There are at least two ways in which thiscan happen.Linear Costs and Temporal Increase in Unit Supply Cost. One is where the costs are linear, so there are unit costs -3 and 23 of production and storage in period 3. Then it is optimal tohold inventory in a period if the unit production cost in that period is less than that in the following period and the unit storage cost is small enough. In any case, the problem Ð1Ñ-Ð Ñ is thena minimum-linear-cost uncapacitated network-flow problem in which node zero is the sourcefrom which the demands at the other nodes are satisfied. Clearly a minimum-cost flow can beconstructed by finding for each node 3 0 a minimum-cost chain (i.e., directed path) from nodezero to 3, and satisfying the demand at 3 by shipping along that chain. Let G3 be the resultingminimum cost. The G3 can be found recursively from the dynamic-programming forward equations Ð2! G! ÑÐ4ÑG3 œ min Ð-3 ß 23 " G3 " Ñß 3 œ 1ß á ß 8.This recursion expresses the fact that a minimum-cost chain from node zero to node 3 eitherconsists solely of the production arc from node zero to 3 and incurs the cost -3 , or contains node3 1 and the storage arc joining nodes 3 " and 3, and incurs the cost 23 " G3 " . In short, theminimum-cost way to satisfy each unit of demand in period 3 is to choose the cheaper of two alternatives, viz., satisfy the demand by production in period 3 or by production at an optimallychosen prior period and storage to period 3. The G3 are calculated by forward induction in theorder G" ß G# ß á ß G8 .In this process one records the periods 3" œ " 3# â 3: Ÿ 8, say, in which it is optimalto produce, i.e., periods 3 for which G3 œ -3 . Then if it is optimal to produce in a period 35 , say,it is optimal to produce an amount exactly satisfying all demands prior to the next period 35 "(3: " 8 ") in which it is optimal to produce, i.e.,B35 œ " 4 , 5 œ "ß á ß :.35 " "Ð5Ñ4œ35This means that it is optimal to produce only in periods in which there is no entering inventory,i.e.,
MS&E 361 Supply-Chain OptimizationCopyright 2005 Arthur F. Veinott, Jr.Ð6Ñ5§1 IntroductionC3 " B3 œ 0ß 3 œ 1ß á ß 8.The G3 can be computed in linear time with at most 8 operations where an operation is herean addition and a comparison. To see this observe from Ð4Ñ that the computing G3 requires oneaddition Ðcomputing 23 " G3 " Ñ and one comparison (choosing the smaller of the two costs -3and 23 " G3 " ). Because there are 8 such G3 to compute, the claim is verified.Since the periods in which it is optimal to produce are independent of the demands, it isclear from (5) that optimal production in a period is increasing and linear in present and futuredemands with the rate of increase not exceeding that of the demands. Also, the magnitude ofthe change in optimal present production resulting from a change in forecasted demand in a future period diminishes the more distant the period of the change in forecasted demand.This example illustrates several themes that will occur repeatedly throughout this course.Network-Flow Models of Supply Chains. One is the fundamental idea in §4-§6 of formulating and solving supply-chain problems as minimum-cost network-flow problems with scale diseconomies or economies in the arc flow costs. This approach has several advantages. First, it unifies thetreatment of many supply-chain models. Second, it extends the applicability of the methods tobroad classes of problems outside of supply-chain management. Third, it facilitates use
Introduction to Supply-Chain Optimization 1 OVERVIEW Supply Chains. The supply chains of large corporations involve hundreds of facilities (retail-ers, distributors, plants and suppliers) that are globally distributed and involve thousands of parts and products. As one example, one auto manufacturer has 12 thousand suppliers, 70 plants,File Size: 1MBPage Count: 261Explore furtherGLOBAL SUPPLY CHAIN MANAGEMENT [Author] n to Operations and Supply Chain Managementwww.nitc.ac.inStability in Supply Chain Networks - Stanford Universityweb.stanford.edu(PDF) Supply Chain Management: theory and practiceswww.researchgate.netSupply Chain Analytics - Capgeminiwww.capgemini.comRecommended to
