Lectures in Supply-Chain Optimization

[Pages:261]Lectures in Supply-Chain Optimization

Arthur F. Veinott, Jr.

Management Science and Engineering 361 Department of Management Science and Engineering

Stanford University Stanford, California 94305

Copyright ? 2005 by Arthur F. Veinott, Jr.

Contents

1 Introduction to Supply-Chain Optimization.............................................................................................1 1 Overview..............................................................................................................................................1 2 Motives for Holding Inventories.......................................................................................................... 3

2 Lattice Programming and Supply Chains: Comparison of Optima.......................................................15 1 Introduction....................................................................................................................................... 15 2 Sublattices in d8................................................................................................................................17 3 Ascending Multi-Functions: Monotone Selections.............................................................................21 4 Additive, Subadditive and Superadditive Functions......................................................................... 22 5 Minimizing Subadditive Functions on Sublattices............................................................................ 26 6 Application to Optimal Dynamic Production Planning.................................................................... 27

3 Noncooperative and Cooperative Games: Competition and Cooperation in Supply Chains ............. 31 1 Introduction....................................................................................................................................... 31 2 Nash Equilibria of Noncooperative Superadditive Games................................................................. 32 3 Core of Cooperative Linear Programming Game.............................................................................. 35

4 Convex-Cost Network Flows and Supply Chains: Substitutes/Complements/Ripples ...................... 39 1 Introduction....................................................................................................................................... 39 2 Ripple Theorem................................................................................................................................. 43 3 Conformality and Subadditivity........................................................................................................ 46 4 Monotonicity of the Optimal Arc Flows in Arc Parameters............................................................. 52 5 Smoothing Theorem...........................................................................................................................56 6 Unit Parameter Changes................................................................................................................... 60 7 Some Tips for Applications............................................................................................................... 62 8 Application to Optimal Dynamic Production Planning.................................................................... 64

5 Convex-Cost Network Flows and Supply Chains: Invariance .............................................................. 71 1 Introduction....................................................................................................................................... 71 2 Conjugates and Subgradients............................................................................................................ 72 3 d -Additive Convex Functions........................................................................................................... 74 4 Invariance Theorem for Network Flows............................................................................................ 76 5 Taut-String Solution..........................................................................................................................82 6 Application to Optimal Dynamic Production Planning.................................................................... 83

6 Concave-Cost Network Flows and Supply Chains................................................................................. 87 1 Introduction....................................................................................................................................... 87 2 Minimizing Concave Functions on Polyhedral Convex Sets............................................................. 89 3 Minimum-Additive-Concave-Cost Uncapacitated Network Flows.................................................... 92 4 Send-and-Split Method in General Networks.................................................................................... 98 5 Send-and-Split Method in 1-Planar and Nearly 1-Planar Networks............................................... 105 6 Reduction of Capacitated to Uncapacitated Network Flows...........................................................109 7 Application to Dynamic Lot-Sizing and Network Design................................................................110 8 94%-Effective Lot-Sizing for One-Warehouse Multi-Retailer Systems............................................ 116

7 Stochastic Order, Subadditivity Preservation, Total Positivity and Supply Chains.......................... 127 1 Introduction..................................................................................................................................... 127 2 Stochastic and Pointwise Order.......................................................................................................129 3 Subadditivity-Preserving Transformations and Supply Chains.......................................................133

8 Dynamic Supply Policy with Stochastic Demands.............................................................................. 137 1 Introduction..................................................................................................................................... 137 2 Convex Ordering Costs....................................................................................................................139 3 Setup Ordering Cost and (s? S ) Optimal Supply Policies................................................................140 4 Positive Lead Times.........................................................................................................................152 5 Serial Supply Chains: Additivity of Minimum Expected Cost........................................................ 154 6 Supply Chains with Complex Demand Processes............................................................................157

9 Myopic Supply Policy with Stochastic Demands.................................................................................161 1 Introduction..................................................................................................................................... 161 2 Stochastic Optimality and Substitute Products.............................................................................. 162 3 Eliminating Linear Ordering Costs and Positive Lead Times......................................................... 167

i

MS&E 361 Supply-Chain Optimization

ii

Copyright ? 2005 Arthur F. Veinott, Jr.

Contents

Appendix.................................................................................................................................................... 169 1 Representation of Sublattices of Finite Products of Chains............................................................ 169 2 Proof of Monotone-Optimal-Flow-Selection Theorem..................................................................... 173 3 Subadditivity/Superadditivity of Minimum Cost in Parameters.................................................... 177 4 Dynamic-Programming Equations for Concave-Cost Flows............................................................179 5 Sign-Variation-Diminishing Properties of Totally Positive Matrices.............................................. 181

References..................................................................................................................................................185

Homework

Homework 1 1 Leontief Substitution Systems 2 Supply Chains with Linear Costs

Homework 2 1 Assembly Supply Chains with Convex Costs 2 Multiple Assignment Problem with Subadditive Costs 3 Characterization of Additive Functions 4 Projections of Additive Convex Functions are Additive Convex

Homework 3 1 Monotone Minimum-Cost Chains 2 Finding Least Optimal Selection 3 Research and Development Game

Homework 4 1 Computing Nash Equilibria of Noncooperative Games with Superadditive Profits 2 Cooperative Linear Programming Game 3 Multi-Plant Procurement/Production/Distribution 4 Projections of Convex Functions are Convex

Homework 5 1 Guaranteed Annual Wage 2 Quadratic Costs and Linear Decision Rules 3 Balancing Overtime and Storage Costs

Homework 6 1 Production Planning: Taut String 2 Plant vs. Field Assembly and Serial Supply Chains: Taut String 3 Just-In-Time Multi-Facility Production: Taut String

Homework 7 1 Stationary Economic-Order-Interval 2 Extreme Flows in Single-Source Networks 3 Cyclic Economic-Order-Interval

Homework 8 1 *%% Effective Lot-Sizing 2 Dynamic Lot-Sizing with Shared Production 3 Total Positivity

Homework 9 1 Production Smoothing 2 Purchasing with Limited Supplies 3 Optimality of ?=? W? Policies

Homework 10 1 Supplying a Paper Mill 2 Optimal Supply Policy with Fluctuating Demands

1

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, operates in 200 countries and has annual sales of 8.6 million vehicles. As a second example, the US 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 products they want in a timely way and as efficiently and profitably as possible. Fueled in part by the information revolution and the rise of e-commerce, the development of models of supply chains and 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 science today. 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 Optimization

2

Copyright ? 2005 Arthur F. Veinott, Jr.

?1 Introduction

These decisions are typically made in an environment that involves uncertainty about product demands, costs, prices, lead times, quality, etc. The decisions are generally made in a multi-party environment that includes competition and often includes collaborative alliances.

Alliances lead to questions of how to share the benefits of collaboration and what information the 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 more responsive and efficient.

Inventories. Typically firms carry inventories at various locations in a supply chain to buffer the operations at different facilities and in different periods. Inventories are the links between facilities and time periods. Inventories of raw materials, work-in-process, and finished goods are ubiquitous in firms engaged in production or distribution (by sale or circulation) of one or more products. Indeed, in the United States alone, 2000 manufacturing and trade inventories totaled 1,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 the Census, Tables 756 and 640). The annual cost of carrying these inventories, e.g., costs associated with capital, storage, taxes, insurance, etc., is significant--perhaps 25% of the total investment in inventories, or 301 billion dollars and 3% of the gross domestic product.

Scope. The conventional types of inventories include raw materials, work in process, and finished goods. But there are many other types of inventories which, although frequently not thought of as inventories in the usual sense, can and have been usefully studied by the methods developed 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 wider than may seem the case at first.

2 MOTIVES FOR HOLDING INVENTORIES Since it is usually expensive to carry inventories, efficient firms would not do so without

good reasons. Thus, it seems useful to examine the motives for holding inventories. As we do so,

MS&E 361 Supply-Chain Optimization

3

Copyright ? 2005 Arthur F. Veinott, Jr.

?1 Introduction

we give examples briefly illustrating many of the more common motives as well as the methods

used to analyze them. We shall discuss only the case of a single facility and single party in the

remainder of this section, reserving the complications arising from multiple facilities and parties

for subsequent sections.

It is helpful to begin by formulating and studying an 8-period supply-chain problem under

certainty. Let B3, C3 and =3 be respectively the nonnegative production, end-of-period inventory and given demand for a single product in period 3 oe 1? ? ? 8. Let -3?D? and 23?D? be respectively the costs of producing and storing D 0 units of the product in period 3. We can and do assume

without loss of generality that -3?0? oe 23?0? oe 0 for all 3. The problem is to choose production and inventory schedules B oe ?B3? and C oe ?C3? respectively that minimize the 8-period cost

8

?1?

G ?B? C? ? " ? -3?B3? 23?C3??

"

subject to the stock-conservation constraints

?2 ?

B3 C3" C3 oe =3? 3 oe 1? ? ? 8

and nonnegativity of production and inventories (the last to assure that demands are met as they arise without backorders)

?3?

B? C 0

where for simplicity we set C! ? C8 ? !. Network-Flow Formulation. The problem ?1?-?$? can be viewed as one of finding a mini-

mum-nonlinear-cost network flow as Figure 1 illustrates. The variables are the flows in the arcs that they label, the exogenous demands (negative demands are "supplies") at nodes 1? ? ? 8 are

%

0

=3 "

B"

B#

B$

B%

1 ="

C"

2 =#

C#

3 =$

C$

4 =%

Figure 1. Production Planning Network

the

given

demands

in

those

periods,

and

the

supply

at

node

zero

is

the

total

demand

!

3

=3

in

all

periods. The stock-conservation constraints ?#? are the flow-conservation constraints in the net-

MS&E 361 Supply-Chain Optimization

4

Copyright ? 2005 Arthur F. Veinott, Jr.

?1 Introduction

work. The flow-conservation constraint at node zero expresses the fact that total production in all periods equals total demand in all periods. The flow-conservation constraint at each other node 3 0 expresses the fact that the sum of the initial inventory and production in period 3 equals the sum of the demand and final inventory in that period.

One important motive for carrying inventories arises when there is a temporal increase in the 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 this can 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 to hold 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 then a minimum-linear-cost uncapacitated network-flow problem in which node zero is the source from which the demands at the other nodes are satisfied. Clearly a minimum-cost flow can be constructed by finding for each node 3 0 a minimum-cost chain (i.e., directed path) from node zero to 3, and satisfying the demand at 3 by shipping along that chain. Let G3 be the resulting minimum cost. The G3 can be found recursively from the dynamic-programming forward equations ?2! ? G! ? _?

?4 ?

G3 oe min ?-3? 23" G3"?? 3 oe 1? ? ? 8.

This recursion expresses the fact that a minimum-cost chain from node zero to node 3 either

consists solely of the production arc from node zero to 3 and incurs the cost -3, or contains node 3 1 and the storage arc joining nodes 3 " and 3, and incurs the cost 23" G3". In short, the minimum-cost way to satisfy each unit of demand in period 3 is to choose the cheaper of two al-

ternatives, viz., satisfy the demand by production in period 3 or by production at an optimally

chosen prior period and storage to period 3. The G3 are calculated by forward induction in the

order G"? G#? ? ? G8. In this process one records the periods 3" oe " 3# ? 3: Y 8, say, in which it is optimal

to produce, i.e., periods 3 for which G3 oe -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.,

35""

?5 ?

B35 oe " =4, 5 oe "? ? ? :.

4oe35

This means that it is optimal to produce only in periods in which there is no entering inventory,

i.e.,

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download