If all customers must be served (i.e. if the penalties pj are suf¬ciently high for

each j ∈ V2 ), variables zj , j ∈ V2 , can be assumed equal to 0. Hence, the location-

covering problem is a generalization of the well-known set covering problem and is

therefore NP-hard.

Several variants of the location-covering model can be used in practice. For exam-

ple, if ¬xed costs fi are equal for all potential sites i ∈ V1 , it can be convenient

to discriminate among all the solutions with the least number of open facilities the

one corresponding to the least total travelling time, or to the most equitable demand

distribution among the facilities. In the former case, let xij , i ∈ V1 , j ∈ V2 , be a

binary decision variable equal to 1 if customer j is served by facility i, 0 otherwise.

The problem can be modelled as follows:

Minimize

Myi + tij xij (3.60)

i∈V1 j ∈V2

i∈V1

subject to

j ∈ V2 ,

aij xij 1, (3.61)

i∈V1

|V2 |yi , i ∈ V1 ,

xij (3.62)

j ∈V2

yi ∈ {0, 1}, i ∈ V1 , (3.63)

xij ∈ {0, 1}, i ∈ V1 , j ∈ V2 , (3.64)

where M is a large positive constant. Constraints (3.61) guarantee that all the cus-

tomers j ∈ V2 are serviced, while constraints (3.62) ensure that if facility i ∈ V1 is

not set up (yi = 0), then no customer j ∈ V2 can be served by it.

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 115

Table 3.21 Distances (in kilometres) between municipalities of

the consortium in Portugal (Part II).

Macau Moita Montijo Palmela Pinhal Novo

Almada 39.0 29.5 38.8 34.3 39.1

Azenha 15.4 9.5 18.7 24.0 16.9

Carregosa 13.9 5.1 7.2 16.4 10.9

Corroios 32.9 23.4 32.7 28.2 33.0

Lavradio 16.1 7.4 16.6 26.2 14.2

Macau 0.0 9.1 12.0 6.9 1.7

Moita 9.1 0.0 10.6 11.7 7.2

Montijo 12.0 10.6 0.0 19.0 10.3

Palmela 6.9 11.7 19.0 0.0 8.8

Pinhal Novo 1.7 7.2 10.3 8.8 0.0

In Portugal, a consortium of 10 municipalities (Almada, Azenha, Carregosa, Cor-

roios, Lavradio, Macau, Moita, Montijo, Palmela, Pinhal Novo), located in the neigh-

bourhood of Lisbon, has decided to improve its ¬re-¬ghting service. The person

responsible for the project has established that each centre of the community must

be reached within 15 min from the closest ¬re station. Since the main aim is just to

provide a ¬rst help in case of ¬re, the decision maker has decided to assign a single

vehicle to each station. The annual cost of a station inclusive of the expenses of the

personnel is ‚¬198 000. It is assumed that the average travelling speed is 60 km/h

everywhere. In order to determine the optimal station location the location-covering

model (3.60)“(3.64) is used, where V1 = V2 = {Almada, Azenha, Carregosa, Cor-

roios, Lavradio, Macau, Moita, Montijo, Palmela, Pinhal Novo}. Time coef¬cients

tij , i ∈ V1 , j ∈ V2 , can be easily determined from the distances (in kilometres)

reported in Tables 3.20 and 3.21. Coef¬cients aij , i ∈ V1 , j ∈ V2 , were obtained

from Tables 3.20 and 3.21. The minimum number of ¬re stations turns out to be two.

The facilities are located in Almada and Moita. The ¬re station located in Almada

serves Corroios and Almada itself, the remaining ones are served by the ¬re station

located in Moita.

Another interesting variant of the location-covering model arises when one must

locate facilities to ensure double coverage of demand points. A classic case is ambu-

lance location when users are better protected if two ambulances are located within

their vicinity. If one of the two ambulances has to answer a call, there will remain one

ambulance to provide coverage.

3.6 Data Aggregation

Modelling and solving a location problem often requires a considerable amount of

data. For instance, the number of demand points of a large food producer often exceeds

TLFeBOOK

116 DESIGNING THE LOGISTICS NETWORK

several thousands. Similarly, the items marketed by a distribution ¬rm can be around

tens of thousands. Therefore, in order to keep computation times and hardware require-

ments acceptable, data have to be aggregated. This can be done mainly in two ways.

Demand aggregation. Customers can be aggregated according to their position,

service level or frequency of delivery. In the ¬rst case, demand points are clustered in

such a way that customers close to one another (e.g. customers having the same zip

code) are substituted by a customer zone. In the other cases, customers are aggregated

into classes.

Item aggregation. Items are aggregated into a suitable number of product groups.

This can be done according to their distribution pattern or their features (weight,

volume, shape, cost, etc.). In the former case, products manufactured by the same

plants and supplied to the same customers are treated as a single commodity. In

the latter case, similar items (e.g. variants of the same basic product model) are

aggregated.

Whatever the aggregation method, the reduced problem can be modelled with fewer

variables and constraints. In what follows, a demand aggregation method for the CPL

model (see Section 3.3.1) is analysed. The demand points of a subset S ‚ V2 are

aggregated in the following way:

xij = xik , i ∈ V1 , j ∈ S, k ∈ S.

Consequently, each point j ∈ S receives the same fraction of demand from each

facility i ∈ V1 . Let s be the customer zone resulting from the aggregation. Then the

CPL model becomes:

Minimize

cij xij + fi y i

i∈V1 j ∈(V2 \S)∪{s} i∈V1

subject to

xij = 1, j ∈ (V2 \ S) ∪ {s},

i∈V1

i ∈ V1 ,

dj xij qi yi ,

j ∈(V2 \S)∪{s}

1, i ∈ V1 , j ∈ (V2 \ S) ∪ {s},

xij

0

yi ∈ {0, 1}, i ∈ V1 ,

where

cis = i ∈ V1 ,

cij ,

j ∈S

and

ds = dj .

j ∈S

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 117

As a rule, the optimal solution value of the aggregated problem is worse than that

of the original problem. It is useful to evaluate an upper bound on the error made

— (a)

resulting from the aggregation procedure. Let zCPL and zCPL be the costs of the

optimal solutions of the original problem and of the aggregate problem, respectively.

Property. The following relation holds,

— —

(a)

zCPL + µ,

zCPL

zCPL

where

dj r∈S cir

µ= ’ cij .

max (3.65)

r∈S dr

i∈V1

j ∈S

Proof. In Equation (3.65), r∈S cir represents the transportation cost when the whole

demand of customers in S is served by facility i ∈ V1 , while dj / r∈S dr represents

the fraction of the total demand of customers in S. The difference

’ cij

dj cir dr

r∈S r∈S

represents, therefore, the variation (positive, negative or zero) of the cost of assigning

the whole demand of customer j ∈ V2 to facility i ∈ V1 when the vertices of S are

aggregated. Therefore, Equation (3.65) expresses the worst-case error made in the

aggregation process as a sum of the maximum increases of the distribution costs of

the various demand points in S.

It can be shown that bound (3.65) is tight, i.e. there are instances such that the

aggregation error is nearly equal to µ.

If the demands of Brossard and Verdun are aggregated in the Goutte problem

(see Section 3.3, where the maximum distance between plants and sales districts is

assumed to be in¬nite), the worst-case error is, on the basis of Equation (3.65),

µ = µ1 + µ2 = 1578.92 Canadian dollars per year,

where

q1 (ci1 + ci6 )

µ1 = max ’ ci1 = 789.46 Canadian dollars per year,

(q1 + q6 )

i∈V1

q6 (ci1 + ci6 )

µ2 = max ’ ci6 = 789.46 Canadian dollars per year.

(q1 + q6 )

i∈V1

The above aggregation technique can be obviously extended to the case of K

disconnected subsets S1 , . . . , SK .

TLFeBOOK

118 DESIGNING THE LOGISTICS NETWORK

Property. An a priori upper bound on the error is given by

K

— —

(a)

+

zCPL zCPL zCPL µk ,

k=1

where

dj r∈Sk cir

µk = ’ cij .

max

r∈Sk dr

i∈V1

j ∈Sk

3.7 Questions and Problems

3.1 Illustrate why crude oil re¬neries are customarily located near home heating

and automotive fuel markets.

3.2 Describe how ¬xed costs fi , i ∈ V1 , in the CPL model should be computed

in order to take labour costs, property taxes and site-development costs into

account.

3.3 Your company has to close 20 of its 125 warehouses. Suppose the CPL hypothe-

ses hold. How would you de¬ne V1 ? What is the value of p?

3.4 Modify the CPL model to take into account that a subset of already existing

facilities V1 ⊆ V1 cannot be closed (but can be upgraded). Indicate the current

¬xed cost and capacity of facility i ∈ V1 as fi and qi , respectively. Moreover,

let fi and qi be the ¬xed cost and capacity if facility i ∈ V1 is upgraded,

respectively.

3.5 Borachera is a major Spanish wine wholesaler currently operating two CDCs in

Salamanca and Albacete, and a number of RDCs all over the Iberian peninsula.

In order to reduce the overall logistics cost, the company wishes to redesign its

distribution network by replacing its current RDCs with three (possibly new)

RDCs. Based on a preliminary qualitative analysis, an RDC should be located

in the Castilla-Leon region, either in Vallalolid, Burgos or Soria. A second RDC

should be located in the Extremadura region, either in Badajoz, Plasencia or

Caceres. Finally, the third RDC should be located in the Argon region, either

in Barbastro, Saragossa or Teruel. Transportation costs from RDCs to retailers

are charged to retailers. Formulate the Borachera problem as a modi¬ed CPL

model.

3.6 As illustrated in Section 3.3, when designing a distribution network it is cus-

tomary to remove excessively long transportation links from the model in order

to allow for a timely delivery to customers. How should the CPL Lagrangian

heuristic be modi¬ed in this case?

3.7 Modify the CPL Lagrangian heuristic for the case where demand is indivisible

(i.e. a customer demand must be satis¬ed by a single warehouse). Is the modi¬ed

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 119

heuristic still time-polynomial? How can it determine whether an instance of

the modi¬ed problem is feasible?

3.8 Modify the TEMC model in Section 3.4 for the case where a customer can

receive shipments from different DCs if these shipments are for different com-

modities. How should the proposed heuristics be changed in order to take this

modi¬cation into account?

3.9 Modify the location-covering model in order to determine, among the least-

cost solutions, the one associated with the most equitable demand distribution

among the facilities.

3.10 Data aggregation is useful in facility location even if the available algorithms

are able to solve the original problems. Why? (Hint: recall that demand forecasts

at the account and product levels are generally mediocre.)

3.8 Annotated Bibliography

An extensive literature review of strategic production-distribution models is presented

in the following article:

1. Vidal C and Goetschalckx M 1997 Strategic production-distribution models: a

critical review with emphasis on global supply chain models. European Journal

of Operational Research 98, 1“18.

An in-depth examination of location theory in a broader context is reported in the

following book:

2. Love RF, Morris JG and Wesolowsky GO 1988 Facilities Location. North-

Holland, Amsterdam.

A review of the most important location-routing problems is presented in:

3. Laporte G 1988 Location-routing problems. In Vehicle Routing: Methods and

Studies (ed. Golden BL and Assad AA). North-Holland, Amsterdam.

TLFeBOOK

TLFeBOOK

4

Solving Inventory Management

Problems

4.1 Introduction

Inventories are stockpiles of items (raw materials, components, semi-¬nished and

¬nished goods) waiting to be processed, transported or used at a point of the supply

chain. As pointed out in Chapter 1, there are a number of reasons to have invento-

ries, including improving service level, reducing overall logistics costs, coping with

randomness in customer demand and lead times, making seasonal items available all

year, speculating on price patterns, etc. At the same time, holding an inventory can

be very expensive (the annual cost can be 30% of the value of the materials kept in

stock, or even more). It is therefore crucial to manage inventories carefully.

This chapter deals with the solution of the most important inventory management

problems. Inventory management amounts to deciding for each stocking point in the

supply chain when to reorder and how much to order so that the expected annual cost

is minimized while meeting a given service level. A useful formula that can be used to

know whether a stocking point is well managed is the inventory turnover ratio (ITR),

de¬ned as the ratio between the annual sales priced at the value of the items in stock

and the average inventory investment. Of course, high ITRs generally correspond to

well-managed stocking points.

4.2 Relevant Costs

The costs relevant to the determination of an inventory policy can be classi¬ed into

four broad categories.

Procurement costs. Procurement costs are those associated with the acquisition of

goods. They typically include ¬xed costs (independent of the amount ordered) and

variable costs (dependent of the amount acquired). They may include

Introduction to Logistics Systems Planning and Control G. Ghiani, G. Laporte and R. Musmanno

© 2004 John Wiley & Sons, Ltd ISBN: 0-470-84916-9 (HB) 0-470-84917-7 (PB)

TLFeBOOK

122 SOLVING INVENTORY MANAGEMENT PROBLEMS

• a (¬xed) reorder cost (the cost of issuing and processing an order through the

purchasing and accounting departments if the goods are bought, or the cost for

setting up the production process if the goods are manufactured by the ¬rm);

• a purchasing cost or a (variable) manufacturing cost, depending on whether

the goods are bought from a supplier or manufactured by the ¬rm;

• a transportation cost, if not included in the price of the purchased goods; for the

sake of simplicity, we assume in the remainder of this chapter that ¬xed trans-

portation costs are included in the reorder cost, while variable transportation

costs are included in the purchasing cost;

• the cost of handling the goods at the receiving point.

Inventory holding costs. Inventory holding costs are incurred when materials are

stored for a period of time. They include the following.

• An opportunity (or capital) cost representing the return on investment the ¬rm

would have realized if money had been invested in a more pro¬table economic

activity (e.g. on the stock market) instead of inventory. This cost is generally

estimated on the basis of a standard banking interest rate.

• A warehousing cost. If the company runs its own warehouses, such costs include

space and equipment costs, personnel wages, insurance on inventories, mainte-

nance costs, energy costs and state taxes. Otherwise, warehousing costs amount

to the fee paid for storing the goods in third-party warehouses.

Shortage costs. Shortage costs are paid when customer orders are not met. Shortage

costs depend heavily on customer behaviour and are dif¬cult to evaluate accurately.

They can be classi¬ed as follows.

• Lost sales costs. A lost sale is likely to occur if the unavailable items can be

easily obtained from a competitor. Lost sales costs include the pro¬t that would

have made on the sale, and the negative effect that the shortage could have on

future sales.

• Back order costs. When goods are dif¬cult to replace, a shortage often results

in a delayed sale. Apart from the negative effect on future sales, a back order

could result in a penalty.

Obsolescence costs. Obsolescence costs arise when stocked items lose some of

their value over time. This happens, for example, when food inventories deteriorate,

clothing items in stock go out of fashion, or newspapers are unsold. The value of an

item at the end of its lifetime is usually referred to as its salvage value.

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 123

4.3 Classi¬cation of Inventory Management Models

Inventory management models can be classi¬ed according to a number of criteria.

Deterministic versus stochastic models. In a deterministic model, where demands,

prices and lead times are assumed to be known in advance, the focus is on balancing

different categories of costs (e.g. the ¬xed costs of ordering and the costs of holding

inventory). In a stochastic model, where some data are uncertain, it is impossible

to always satisfy all the demand. As a result, a constraint on customer service level

(stating, for example, that a customer is satis¬ed with a given probability) is usually

imposed.

Fast-moving items versus slow-moving items. Fast-moving items are those man-

ufactured and sold regularly, and include most products on the market. The main issue

when managing a fast-moving item inventory is to determine when stocking points

have to be replenished and how much to order. On the other hand, slow-moving items,

which are often spare parts of complex machineries, have a very low demand (e.g. a

few units every 10 or 20 years). As a rule, manufacturing a spare part several years

after the machinery is constructed is very expensive compared to producing it along

with the machinery. Hence the main issue is to determine the number of items that

have to be produced and stored at the beginning of the planning horizon.

Number of stocking points. Optimal inventory policies can often be derived ana-

lytically for single stocking point models, while multiple stocking point situations are

usually much harder to deal with.

Number of commodities. When holding a multicommodity inventory, joint costs

and constraints usually come into play. It is therefore not surprising that most multi-

commodity inventory management problems are NP-hard.

Instantaneous resupply versus noninstantaneous resupply. A stocking point can

be replenished almost instantaneously (e.g. as a consequence of a truck delivery) or

noninstantaneously (e.g. at a constant rate through a manufacturing process).

4.4 Single Stocking Point: Single-Commodity

Inventory Models under Constant Demand Rate

A single stocking point has to service a single-commodity constant rate demand, and

places orders for the item from another facility. The planning horizon is assumed

to be in¬nite (for the ¬nite horizon case, see Problem 4.4). Since the demand rate

is constant, a minimal cost policy is to replenish on a periodic basis. Let d be the

constant demand rate, T the time lapse between two consecutive orders, q the order

size (i.e. the amount of product ordered at each replenishment). These quantities are

TLFeBOOK

124 SOLVING INVENTORY MANAGEMENT PROBLEMS

I(t)

T = q/d

m

r’d ’d

r

T1 T2 T3 T4

t

’s

Figure 4.1 Inventory level as a function of time.

such that

q = dT . (4.1)

Moreover, let c be the value of an item (assumed to be independent of the order size),

k the ¬xed reorder cost, h the holding cost per item and per time unit, u the shortage

cost per item, independent of the duration of the shortage, and v the shortage cost per

item and per time unit. The holding cost h can be expressed as a fraction p of c:

h = pc. (4.2)

The parameter p is a banking interest rate (measuring capital cost) increased to take

into account warehousing costs. Moreover, let I (t) be the inventory level at time t,

m the maximum inventory level, s the maximum shortage, tl the lead time, i.e. the

time lapse between when an order is placed and when the items are received (see

Chapter 1). The problem is to determine q (or, equivalently, T ) and s in such a way

that the overall average cost per time unit is minimum.

4.4.1 Noninstantaneous resupply

Let Tr 0 be the replenishment time, i.e. the time to make a replenishment, and r

the replenishment rate, i.e. the number of items per unit of time received during Tr .

The following relation holds:

q = rTr . (4.3)

The inventory level I (t) as a function of time t is shown in Figure 4.1. Dashed

lines represent the cumulative number of items arriving at the stocking point during

a replenishment (their slope is r). Since items are picked up at a rate d while a

replenishment takes place, the net number of items stocked per unit of time during

Tr is r ’ d. Finally, after a replenishment, the stock level decreases at a rate equal to

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 125

’d. Let T1 , T2 , T3 and T4 be the time the inventory level takes to go from ’s to 0,

from 0 to m, from m to 0 and from 0 to ’s, respectively.

The maximum inventory level m is given by

s + m = (r ’ d)Tr .

Therefore, from Equation (4.3),

m = (r ’ d)Tr ’ s = q(1 ’ d/r) ’ s.

The total average cost per time unit µ(q, s) is

1 ¯ ¯

µ(q, s) = (k + cq + hI T + us + v ST ). (4.4)

T

The quantity in parentheses in the right-hand side is the average cost per period,

given by the ¬xed and variable costs of a resupply (k and cq, respectively), and the

¯ ¯

holding cost hI T , plus the shortage costs (us and v ST ). The holding and shortage

¯ ¯

costs depend on the average inventory level I , and on the average shortage level S,

respectively:

m(T2 + T3 )

T

1 1

¯

I= I+ (t) dt = ,

T T 2

0

s(T1 + T4 )

T

1 1

¯

S= I’ (t) dt = ,

T T 2

0

where

’I (t)

I (t) if I (t) 0, if I (t) 0,

I+ (t) = and I’ (t) =

0 otherwise, 0 otherwise.

Moreover, since

s = (r ’ d)T1 ,

m = (r ’ d)T2 ,

m = dT3 ,

s = dT4 ,

the time lapses T1 , T2 , T3 and T4 are given by

s

T1 = ,

r ’d

m

T2 = ,

r ’d

m

T3 = ,

d

s

T4 = .

d

TLFeBOOK

126 SOLVING INVENTORY MANAGEMENT PROBLEMS

I(t)

T = q/d

m

t

Figure 4.2 Inventory level as a function of time when shortage is not allowed.

Consequently,

[q(1 ’ d/r) ’ s]2

m2

¯

I= = , (4.5)

2q(1 ’ d/r) 2q(1 ’ d/r)

s2

¯=

S . (4.6)

2q(1 ’ d/r)

Finally, using Equations (4.1), (4.5) and (4.6), Equation (4.4) can be rewritten as

h[q(1 ’ d/r) ’ s]2 vs 2

kd usd

µ(q, s) = + cd + + + . (4.7)

2q(1 ’ d/r) 2q(1 ’ d/r)

q q

If shortages are allowed, the minimum point (q — , s — ) of the convex function µ(q, s)

can be obtained by solving the equations:

‚

= 0,

µ(q, s)

‚q q=q — ,s=s —

‚

= 0.

µ(q, s)

‚s q=q — ,s=s —

As a result,

h+v (ud)2

2kd

—

q= ’ (4.8)

h(1 ’ d/r) h(h + v)

v

and

(hq — ’ ud)(1 ’ d/r)

—

s= . (4.9)

(h + v)

If shortages are not allowed (see Figure 4.2), Equation (4.7) can be simpli¬ed since

s = 0:

µ(q) = kd/q + cd + 2 hq(1 ’ d/r).

1

(4.10)

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 127

µ(q)

kd/q + hq(1 ’ d/r)/2

hq(1 ’ d/r)/2

kd/q

q

q*

Figure 4.3 Average costs as a function of q.

Hence, a single equation has to be solved:

d

= 0,

µ(q)

dq q=q —

Finally, the optimal order size q — is (see Figure 4.3)

2kd

q— = . (4.11)

h(1 ’ d/r)

Golden Food distributes tinned foodstuff in Great Britain. In a warehouse located in

Birmingham, the demand rate d for tomato pur´ e is 400 pallets a month. The value of

e

a pallet is c = £2500 and the annual interest rate p is 14.5% (including warehousing

costs). Issuing an order costs £30. The replenishment rate r is 40 pallets per day.

Shortages are not allowed. The holding cost is given by

h = 0.145 — 2500 = £362.5 per year per pallet

= £30.2 per month per pallet.

Therefore, from Equation (4.11),

2 — 30 — 400

q— = = 39.9 ≈ 40 pallets,

30.2[1 ’ 400/(40 — 20)]

where it is assumed that the number of workdays in a month equals 20 (hence the

TLFeBOOK

128 SOLVING INVENTORY MANAGEMENT PROBLEMS

I(t)

T = q/d

m

t

’s

Figure 4.4 Inventory level as a function of time in the instantaneous resupply case.

demand rate d is 20 pallets per workday). Finally, from Equations (4.1) and (4.3),

T — = 40/400 = 1/10 month = 2 workdays,

Tr— = 40/40 = 1 workday.

4.4.2 Instantaneous resupply

If resupply is instantaneous, the optimal inventory policy can be obtained by Equations

(4.8), (4.9) and (4.11), taking into account that r ’ ∞. If shortages are allowed (see

Figure 4.4), then

h + v 2kd (ud)2

—

q= ’ ,

h(h + v)

v h

hq — ’ ud

—

s= .

(h + v)

If shortages are not allowed (see Figure 4.5), Equation (4.10) becomes

µ(q) = kd/q + cd + 2 hq

1

(4.12)

and the optimal order size is given by

2kd

q— = . (4.13)

h

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 129

I(t)

T = q/d

m=q

t

Figure 4.5 Inventory level as a function of time in the EOQ model.

This is the classical economic order quantity (EOQ) model introduced by F. W. Harris

in 1913. The total cost per time unit of an EOQ policy is

√

µ(q — ) = 2kdh + cd.

Optimal policies with no backlogging (in particular, the EOQ policy) satisfy the

zero inventory ordering (ZIO) property, which states that an order is received exactly

when the inventory level falls to zero.

Al-Bufeira Motors manufactures spare parts for aircraft engines in Saudi Arabia. Its

component Y02PN, produced in a plant located in Jiddah, has a demand of 220 units

per year and a unit production cost of $1200. Manufacturing this product requires

a time-consuming set-up that costs $800. The current annual interest rate p is 18%,

including warehousing costs. Shortages are not allowed. The holding cost is

h = 0.18 — 1200 = 216 dollars/year per unit.

Therefore, from Equation (4.13),

q — = 40.37 units,

and, from Equation (4.1),

T — = 40.37/220 = 0.18 years = 66.8 days.

The total cost is given by Equation (4.12),

hq — 800 — 220 216 — 40.37

kd

+ = + = 8719.63 dollars per year,

q— 2 40.37 2

plus

cd = 220 — 1200 = 264 000 dollars per year.

TLFeBOOK

130 SOLVING INVENTORY MANAGEMENT PROBLEMS

I(t)

m

l

t

’s

tl

Figure 4.6 Reorder point.

In practice, the values of q — and of T — must be rounded as explained in Section 4.12.

4.4.3 Reorder point

An order has to be issued tl time instants before the inventory level equals ’s. In case

resupplies are instantaneous, a replenishment is needed every time the inventory level

equals the following reorder point l,

l = (tl ’ tl /T T )d ’ s,

where tl /T is the number of periods included in the lead time (see Figure 4.6).

In the Al-Bufeira Motors problem, a set-up has to be planned seven days in advance.

Assuming T = 67 days, the reorder point l is

220

l = (7 ’ 7/67 — 67) ’ 0 ≈ 4 units.

365

4.5 Single Stocking Point: Single-Commodity

Inventory Models under Deterministic

Time-Varying Demand Rate

When orders are placed in advance, demands can be assumed to be deterministic,

yet time-varying. Let 1, . . . , TH be a ¬nite and discrete time horizon. In addition, let

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 131

dt , t = 1, . . . , TH , be the demand at time period t, k the ¬xed reorder cost, and h the

holding cost. The problem is to decide how much to order in each time period in such

a way that the sum of reorder costs plus holding costs is minimized. No backlogging

is allowed. In 1958, H. M. Wagner and T. M. Whithin formulated this problem as

follows. The decision variables are the amount qt , t = 1, . . . , TH , ordered at the

beginning of time period t, the inventory level It , t = 1, . . . , TH , at the end of time

period t; in addition let yt , t = 1, . . . , TH , be a decision variable equal to 1 if an

order is placed in time period t, 0 otherwise.

Minimize

(kyt + hIt ) (4.14)

t=1,...,TH

subject to

It = It’1 + qt ’ dt , t = 1, . . . , TH , (4.15)

t = 1, . . . , TH ,

qt yt dr , (4.16)

r=t,...,n

I0 = 0, (4.17)

t = 1, . . . , TH ,

It 0,

t = 1, . . . , TH ,

qt 0,

yt ∈ {0, 1}, t = 1, . . . , TH ,

where the objective function (4.14) is the total cost. Equations (4.15) are the inventory-

balance constraints, inequalities (4.16) state that for each time period t = 1, . . . , TH ,

qt is zero if yt is zero, and equation (4.17) speci¬es the initial inventory.

2

An optimal solution of the Wagner“Within model can be obtained in O(TH ) time

through a dynamic programming procedure. This algorithm is based on the following

theoretical results.

Proposition. Any optimal policy satis¬es the ZIO property, i.e.

qt It’1 = 0, t = 1, . . . , TH .

Proof. If It’1 = δ > 0 and qt > 0, the total cost can be reduced by setting It’1 := 0,

qt := qt + δ, and modifying the remaining variables accordingly.

Corollary. In an optimal policy, the amount ordered at each time period is the total

demand of a set of consecutive subsequent periods.

The algorithm is as follows. Let G = (V , A) be a directed acyclic graph, where

V = {1, . . . , TH , TH + 1} is a vertex set and A = {(t, t ) : t = 1, . . . , TH , t =

t + 1, . . . , TH + 1} is an arc set. With each arc (t, t ) is associated the cost of ordering

in time period t to satisfy the demands in time periods t, t + 1, . . . , t ’ 1:

gtt = k + h (r ’ t)dr .

r=t,...,t ’1

TLFeBOOK

132 SOLVING INVENTORY MANAGEMENT PROBLEMS

Then the shortest path between vertices 1 and TH + 1 corresponds to a least-cost

inventory policy.

Sao Vincente Chemical is a Portuguese company producing lubricants. In the fol-

lowing year, its product Serrado Oil is expected to have a demand of 720, 1410, 830

and 960 pallets in winter, spring, summer and autumn, respectively. Manufacturing

this product requires a time-consuming set-up that costs ‚¬8900. The current annual

interest rate p is 7.5%, including warehousing costs. The variable production cost

amounts to $350 per pallet while the initial inventory is zero. The holding cost is

h = 0.075 — 350/4 = 6.56 euros/season per unit.

Let t = 1, 2, 3, 4 represent the winter, spring, summer and autumn periods, respec-

tively. By solving the Wagner“Within model, it follows that the optimal policy is

to produce at the beginning of winter and summer of the next year. In particular,

y1 = y3 = 1, y2 = y4 = 0, q1 = 2130, q2 = 0, q3 = 1790, q4 = 0, I1 = 1410,

I2 = 0, I3 = 960, I4 = 0. Total holding and set-up costs amount to ‚¬33 353.

4.6 Models with Discounts

In the previous sections it has been assumed that the value of an item is always constant

(equal to c). In practice, quantity discounts offered by suppliers, or economies of scale

in the manufacturing processes, make the value of an item dependent on the order

size q. In the following, quantity-discounts-on-all-units and incremental quantity

discounts are examined under the EOQ hypothesis. Let f (q) be the value of q items.

If the value of an item is independent of q, then f (q) = cq. Otherwise, f (q) is a

concave nondecreasing function.

4.6.1 Quantity-discounts-on-all-units

The function f (q) is assumed to be piecewise linear (see Figure 4.7),

f (q) = ci q, i = 1, 2, . . . ,

qi’1 q < qi ,

where q0 = 0, q1 , . . . are known discount breaks (qi < qi+1 , i = 1, 2, . . . ), f (q0 ) =

0, and ci > ci+1 , i = 1, 2 . . . . Hence, if the order size q is included between discount

breaks qi’1 and qi , the value of every item is ci , i = 1, 2, . . . . It is worth noting

that, depending on ci coef¬cients, f (q) can be greater than f (q ) for q < q (see

Figure 4.7). In practice, the effective cost function is

f (q) = min{ci q, ci+1 qi }, i = 1, 2, . . . .

qi’1 q < qi ,

The total average cost function µ(q) can be written as

µ(q) = µi (q), i = 1, 2, . . . ,

qi’1 q < qi ,

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 133

f (q)

q

q0 q1 q2 q3

Figure 4.7 The value of q items: quantity-discounts-on-all-units.

where, as hi = pci , i = 1, 2, . . . ,

µi (q) = kd/q + ci d + 2 hi q, i = 1, 2, . . . .

1

(4.18)

Then, the optimal order size q — can be obtained through the following procedure.

Step 1. By imposing

dµi (qi )

= 0, i = 1, 2, . . . ,

dqi qi =qi

determine the order size qi , i = 1, 2, . . . , that minimizes µi (q),

2kd

qi = i = 1, 2, . . . .

, (4.19)

hi

Let ±

qi’1 , if qi < qi’1 ,

—

qi = qi , i = 1, 2, . . . . (4.20)

if qi’1 qi qi ,

qi , if qi > qi ,

Step 2. Compute the optimal solution q — = qi—— , where

i — = arg min {µ(qi— )}.

i=1,2,...

TLFeBOOK

134 SOLVING INVENTORY MANAGEMENT PROBLEMS

Maliban runs more than 200 stationery outlets in Spain. The ¬rm buys its products

from a restricted number of suppliers and stores them in a warehouse located near

Sevilla. Maliban expects to sell 3000 boxes of the Prince Arthur pen during the next

year. The current annual interest rate p is 30%. Placing an order costs ‚¬50. The

supplier offers a box at ‚¬3, if the amount bought is less than 500 boxes. The price

is reduced by 1% if 500“2000 boxes are ordered. Finally, if more than 2000 boxes

are ordered, an additional 0.5% discount is applied. Then, by using Equations (4.19)

and (4.20),

2 — 50 — 3000 —

q1 = = 577.35 boxes, q1 = 500 boxes,

0.30 — 3

2 — 50 — 3000 —

q2 = = 580.26 boxes, q2 = 580.26 boxes,

0.30 — 2.97

2 — 50 — 3000 —

q3 = = 581.73 boxes, q3 = 2000 boxes.

0.30 — 2.955

By comparing the corresponding annual average costs given by Equations (4.18),

—

the optimal order size is q — = 580 boxes (≈ q2 ), corresponding to an annual cost of

‚¬9427.

4.6.2 Incremental quantity discounts

The function f (q) is assumed to depend on q as follows (see Figure 4.8),

f (q) = f (qi’1 ) + ci (q ’ qi’1 ), i = 1, 2, . . . ,

qi’1 q < qi , (4.21)

where q0 = 0, q1 , . . . are known discount breaks (qi < qi+1 , i = 1, 2, . . . ), f (q0 ) =

0, and ci > ci+1 , i = 1, 2 . . . . Consequently, if the order size q is included between

discount breaks qi’1 and qi , the value of (q ’ qi’1 ) items is ci , the value of (qi’1 ’

qi’2 ) items is ci’1 , etc. The average total cost function µ(q) is

µ(q) = µi (q), i = 1, 2, . . . ,

qi’1 q < qi ,

where, on the basis of Equation (4.12),

kd f (q)d f (q) q

µi (q) = + +p i = 1, 2, . . . .

,

q q q2

Using Equation (4.21), µi (q), i = 1, 2, . . . , can be rewritten as

µi (q) = kd/q + [f (qi’1 ) + ci (q ’ qi’1 )]d/q

+ 2 p[f (qi’1 ) + ci (q ’ qi’1 )], i = 1, 2, . . .

1

(4.22)

The optimal order size q — can be computed through a procedure very similar to

that used in the previous case.

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 135

f (q)

q

q0 q1 q2 q3

Figure 4.8 The value of q items: incremental quantity discounts.

Step 1. Determine the value qi , i = 1, 2, . . . , that minimizes µi (q) by imposing

that

dµi (qi )

= 0, i = 1, 2, . . . .

dqi qi =q

i

Hence

2d[k + f (qi’1 ) ’ ci qi’1 ]

qi = i = 1, 2, . . . .

, (4.23)

pci

If qi ∈ [qi’1 , qi ], then let µi (qi ) = ∞, i = 1, 2, . . . .

/

Step 2. Compute the optimal solution q — = qi — , where

i — = arg min {µ(qi )}.

i=1,2,...

If Maliban (see the previous problem) applies an incremental quantity discount

policy, then, by using Equation (4.23),

2 — 3000 — 50

q1 = = 577.4 boxes,

0.30 — 3

2 — 3000[50 + (3 — 500) ’ (2.97 — 500)]

q2 = = 661.6 boxes,

0.30 — 2.97

2 — 3000{50 + [(3 — 500) + (2.97 — 1500)] ’ (2.955 — 2000)}

q3 =

0.30 — 2.955

= 801.9 boxes.

TLFeBOOK

136 SOLVING INVENTORY MANAGEMENT PROBLEMS

Consequently, as q1 > 500 and q3 < 2000, the optimal order size is q — =

662 boxes (≈ q2 ), corresponding to an annual average cost, given by Equation (4.22),

equal to ‚¬9501.67.

4.7 Single Stocking Point: Multicommodity

Inventory Models

When several commodities are kept in stock, their inventory policies are intertwined

because of common constraints and joint costs, as we now discuss in two separate

cases. In the ¬rst case, a limit is placed on the total investment in inventories, or on the

warehouse space. In the second case, commodities share joint ordering costs. For the

sake of simplicity, both analysis will be performed under the EOQ model hypotheses.

4.7.1 Models with capacity constraints

Let n be the number of commodities in stock and qj , j = 1, . . . , n, the amount of

commodity j ordered at each replenishment. The inventory management problem can

be formulated as follows.

Minimize

µ(q1 , . . . , qn ) (4.24)

subject to

g(q1 , . . . , qn ) b, (4.25)

q1 , . . . , qn 0, (4.26)

where the objective function (4.24) is the total average cost per time unit. Under the

EOQ hypothesis, the objective function µ(q1 , . . . , qn ) can be written as

n

µ(q1 , . . . , qn ) = µj (qj ),

j =1

where, on the basis of Equation (4.12),

µj (qj ) = kj dj /qj + cj dj + 2 hj qj , j = 1, . . . , n,

1

and quantities kj , dj , cj , hj , j = 1, . . . , n, are the ¬xed reorder cost, the demand

rate, the value, and the holding cost of item j , respectively. As is customary, hj =

pj cj , j = 1, . . . , n, where pj is the interest rate of commodity j .

Equation (4.25) is a side constraint (referred to as a capacity constraint) represent-

ing both a budget constraint or a warehouse constraint. It can usually be considered

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 137

as linear,

n

aj qj b, (4.27)

j =1

where aj , j = 1, . . . , n, and b are constants. As a result, problem (4.24)“(4.26)

has to be solved through iterative methods for NLP problems, such as the conjugate

gradient method. Alternatively, the following simple heuristic can be used if the

capacity constraint is linear and the interest rates are identical for all the commodities

(pj = p, j = 1, . . . , n).

Step 1. Using Equation (4.13), compute the EOQ order sizes qj , j = 1, . . . , n:

2kj dj

qj = j = 1, . . . , n.

, (4.28)

pcj

If the capacity constraint (4.27) is satis¬ed, STOP, the optimal order size for each

product j, j = 1, . . . , n, has been determined.

Step 2. Increase the interest rate p of a δ quantity to be determined. Then, the order

sizes become

2kj dj

qj (δ) = , j = 1, . . . , n. (4.29)

(p + δ)cj

Determine the value δ — satisfying the relation,

n

aj qj (δ — ) = b.

j =1

Hence,

n 2

2kj dj

1

—

δ= ’ p.

aj (4.30)

b cj

j =1

Insert δ — in Equations (4.29) in order to determine the order sizes qj , j = 1, . . . , n.

¯

New Frontier distributes knapsacks and suitcases in most US states. Its most suc-

cessful models are the Preppie knapsack and the Yuppie suitcase. The Preppie knap-

sack has a yearly demand of 150 000 units, a value of $30 and a yearly holding cost

equal to 20% of its value. The Yuppie suitcase has a yearly demand of 100 000 units,

a value of $45 and a yearly holding cost equal to 20% of its value. In both cases,

placing an order costs $250. The company™s management requires the average capital

invested in inventories does not exceed $75 000. This condition can be expressed by

the following constraint,

30q1 /2 + 45q2 /2 75 000,

TLFeBOOK

138 SOLVING INVENTORY MANAGEMENT PROBLEMS

where it is assumed, as a precaution, that the average inventory level is the sum

of the average inventory levels of the two items. The EOQ order sizes, given by

Equation (4.28),

2 — 250 — 150 000

q1 = = 3535.53 units,

0.2 — 30

2 — 250 — 100 000

q2 = = 2357.02 units,

0.2 — 45

do not satisfy the budget constraint. Applying the conjugated gradient method starting

from the initial values (q1 , q2 ) = (1, 1), the following solution is obtained after 300

iterations,

q1 = 2500 units,

¯

q2 = 1666.66 units,

¯

whose total cost is $9 045 000. Applying the heuristic procedure, by using Equa-

tion (4.30), the same solution is obtained. In effect,

2

2 — 250 — 150 000 45 2 — 250 — 100 000

1 30

—

δ= + ’ 0.2

75 000 2 30 2 45

= 0.2,

hence,

2 — 250 — 150 000

q1 =

¯ = 2500 units,

(0.2 + 0.2) 30

2 — 250 — 100 000

q2 =

¯ = 1666.66 units.

(0.2 + 0.2) 45

4.7.2 Models with joint costs

For the sake of simplicity, we assume in this section that only two commodities

are kept in the inventory. Let k1 and k2 be the ¬xed costs for reordering the two

commodities at different moments in time, and let k1’2 be the ¬xed cost for ordering

both commodities at the same time (k1’2 < k1 + k2 ). In addition, let T1 and T2 be the

time lapses between consecutive replenishments of commodities 1 and 2, respectively

(see Figure 4.9). Then,

q1 = d1 T1 , (4.31)

q2 = d2 T2 . (4.32)

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 139

I(t)

T2

q2

T1

q1

t

Figure 4.9 Inventory level as a function of time in case of synchronized orders.

The periodicity of a joint replenishment policy is

T = max{T1 , T2 }.

In each period T , the orders issued for the two items are

N1 = T /T1 ,

N2 = T /T2 .

N1 and N2 are positive integer numbers, one of them being equal to 1 (in the situation

depicted in Figure 4.9, N1 = 3 and N2 = 1). During each period T , two items are

ordered simultaneously exactly once. Moreover, Nj ’ 1 single orders are placed for

each item j, j = 1, 2. Hence, the total average cost per time unit is

µ(T , N1 , N2 )

k1’2 + (N1 ’ 1)k1 + (N2 ’ 1)k2 h 1 d1 T h2 d2 T

= + c1 d1 + c2 d2 + + . (4.33)

T 2N1 2N2

By solving the equation,

‚

= 0,

µ(T , N1 , N2 )

‚T T =T —

the value T — (N1 , N2 ) that minimizes µ(T , N1 , N2 ) is obtained,

2N1 N2 [k1’2 + (N1 ’ 1)k1 + (N2 ’ 1)k2 ]

T — (N1 , N2 ) = , (4.34)

h1 d1 N2 + h2 d2 N1

as a function of N1 and N2 .

TLFeBOOK

140 SOLVING INVENTORY MANAGEMENT PROBLEMS

Shamrock Microelectronics Ltd is an Irish company which assembles printed cir-

cuit boards (PCBs) for a number of major companies in the appliance sector. The Y 23

PCB has an annual demand of 3000 units, a value of ‚¬30 and a holding cost equal to

20% of its value. The Y 24 PCB has an annual request of 5000 units, a value of ‚¬40

and a holding cost equal to 25% of its value. The cost of issuing a joint order is ‚¬300

while ordering a single item costs ‚¬250. If no joint orders are placed, the order sizes

are, according to Equation (4.13),

2 — 250 — 3000

—

q1 = = 500 units,

0.2 — 30

2 — 250 — 5000

—

q2 = = 500 units.

0.25 — 40

From Equations (4.31) and (4.32):

T1— = 500/3000 = 1/6,

T2— = 500/5000 = 1/10.

This means that Shamrock would issue 1/T1— = 6 orders per year of Y 23 PCB and

1/T2— = 10 orders per year of the Y 24 PCB. Since

250 — 3000 0.2 — 30 — 500

—

µ1 (q1 ) = + 30 — 3000 +

500 2

= 93 000 euros per year,

250 — 5000 0.25 — 40 — 500

—

µ2 (q2 ) = + 40 — 5000 +

500 2

= 205 000 euros per year,

the average annual cost is ‚¬298 000 per year. If a joint order is placed and N1 = 1,

N2 = 2, the periodicity of joint orders is, according to Equation (4.34),

2 — 1 — 2 — (300 + 250)

T— = = 0.16.

0.2 — 30 — 3000 — 2 + 0.25 — 40 — 5000 — 1

Shamrock would issue 1/T — = 6.25 joint orders per year. The annual average cost,

computed through Equation (4.33), is equal to

300 + 250 0.2 — 30 — 3000 — 0.16

µ(T — , 1, 2) = + 30 — 3000 + 40 — 5000 +

0.16 2

0.25 — 40 — 5000 — 0.16

+

2—2

= 296 877.5 euros per year.

TLFeBOOK

SOLVING INVENTORY MANAGEMENT PROBLEMS 141

4.8 Stochastic Models

Inventory problems with uncertain demand or lead times have quite a complex math-

ematical structure. In this section, a restricted number of stochastic models are illus-

trated. First, the classical Newsboy Problem, where a one-shot reorder decision has

to be made, is examined. Then, (s, S) policies are introduced for a variant of the

Newsboy Problem. Finally, the most common inventory policies used by practition-

ers (namely, the reorder level method, the reorder cycle method, the (s, S) method

and the two-bin technique) are reviewed and compared. The ¬rst three policies make