Part II: non-periodic orders

Inventory Management

Claudio Arbib

Università dell’Aquila __________

Part II: non-periodic orders

Contents

Non-periodic problems

– equilibrium conditions

Cost functions A convex model

– LP formulation – example

A concave model

– properties of the polyhedron

– properties of optimal solutions

– Wagner-Whitin’s Algorithm

– examples

Non-periodic management

magazine

magazine plant plant

market market A plant must fulfill market

demand in different periods, minimizing production,

delivery and inventory costs

Non-periodic management

• For simplicity, consider

a single product type, to be manufactured in a finite planning horizon, divided in

control periods{1, 2, …, T}, corresponding to

a known demand d

, …, d

, variable with time, and to

decision variables

x

= amount produced/delivered in period t s

= stock level in period t

x

s

d

x

s

d

x

s

d

x

d

s

1 2 3 T

Non-periodic management

x

s

d

x

s

d

x

s

d

x

d

s

1 2 3 T

tempo Production chart

Delivery chart Stock level chart x₁

x₂

x₃

d₁

d₂ d₃

s₁

s₂

s₃

Equilibrium conditions

x

s

d

x

s

d

x

s

d

x

d

s

1 2 3 T

x

= d

+ s

x

+ s

= d

+ s

t = 2, …, T – 1 x

+ s

= d

x

, s

> 0 t = 1, 2, …, T

• The values introduced are in the following relation

possible initial and/or final stock

+ s

+ s

Cost function

The solution technique depends on the form of the cost function.

Let f: IR

→ IR, and λ

, …, λ

> 0 such that Σ ^λ

= 1.

Let x

, …, x

∈ IR

. We say that f is

m i=1

f (x

)

x

x

f (x

)

x = λ x

+ (1 – λ )x

f (x)

λ f(x

) + (1 – λ )f (x

)

• convex if

f ( Σ

^λ

^x

^{) <} Σ

^λ

^{f (x}

⁾

Cost function

The solution technique depends on the form of the cost function.

Let f: IR

→ IR, and λ

, …, λ

> 0 such that Σ ^λ

= 1.

Let x

, …, x

∈ IR

. We say that f is

m i=1

f (x

)

x

x

f (x

)

• concave if instead

f ( Σ

^λ

^x

^{) >} Σ

^λ

^{f (x}

⁾

x = λ x

+ (1 – λ )x

f (x)

λ f(x

) + (1 – λ )f (x

)

x f (x)

Cost function

For instance, the following

• are convex functions

• are neither concave nor convex

x f (x)

• are concave functions

x

f (x)

A piecewise-linear convex model

• inventory costs G

(s

), proportional to the stock level

g

cost per each unit held in during period t

x

, b

• production costs P

(x

) with the following form

p

cost per unit produced up to quantity q

P

> p

extra cost per unit produced beyond q

(overtime labor)

p

x

q

P

(x

)

p

q

+ P

(x

– q

) G

(s

)

g

s

Suppose that the activities of

day t entail

Objective

The objective is to minimize the total (non linear) cost

min P

(x

) + P

(x

) + … + P

(x

) + P

(x

) + + G

(s

) + G

(s

) + … + G

(s

)

In order to obtain a linear cost function, let us distinguish

between the part of x

(say u

) produced without overtime labor and that (say w

) produced with overtime labor:

x

= u

+ w

0 < u

< q

, 0 < w

min p

u

+ p

u

+ … … … … + p

u

+

+ P

w

+ P

w

+ … … … … + P

w

+

+ g

s

+ g

s

+ … + g

s

Minimize the total cost

Σ

[P

(x

) + G

(b

)]

assuming zero backlog ( s

> 0 per t = 1, …, T )

and with the constraint of fulfilling the demand (equilibrium equations)

min p

u

+ p

u

+ … … … … + p

u

+ + P

w

+ P

w

+ … … … … + P

w

+ + g

s

+ g

s

+ … + g

s

subject to

u

+ w

+ s

– s

= d

u

< q

u

, w

, s

> 0 for t = 1, …, T

Problem

Example ( ^data )

Period jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

Production cost 25 25 30 40 20 20

Extra cost 40 45 45 50 40 45

Inventory cost 25 20 30 30 30 30

Plant capacity 100 100 100 100 120 120

Demand 80 210 315 270 240 120

Example ( constraints )

Period jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

Demand 80 210 315 270 240 120

Plant capacity 100 100 100 100 120 120

u Ordinary production w Overtime production

Present stock Previous stock

1 1 1 1 1 1

1 1 1 1 1 1

-1 -1 -1 -1 -1 -1

1 1 1 1 1 1

Reference

Equilibrium equations s

0

= SUMPRODUCT(C13:C16,C8:C11) =

80

80

Example ( ^cost )

Period jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

Production cost 25 25 30 40 20 20

Extra cost 40 45 45 50 40 45

Inventory cost 25 20 30 30 30 30

u Ordinary production w Overtime production

Present stock Previous stock

Total cost s

= SUMPRODUCT(C4:H6,C8:H10)

0

A concave model

• In general the production cost in a period t does not only

depend on the amount manufactured: producing any amount, even a small one, entails a fixed cost; the same is for inventory cost (in which one can include material handling, magazine rental etc.)

• Due to economy of scale, however, passing from a production (inventory) level of 10 units to 20 costs less than passing from zero production to producing 10 units

• Last, we can imagine that, sometimes, the day production and stock are not sufficient to cover demand. In this case (backlog

= negative stock level), orders can be fulfilled by calling, at an additional cost, freight from other plants

• To take into account all these issues, the cost function must be

modified

A concave model

• inventory costs G

(s

)

γ

fixed holding cost + cost for maintaining a specific amount σ

fixed backlog cost + cost of the amount ordered outside

x

, s

G

(s

)

σ

γ

P

(x

)

π

• production costs P

(x

)

π

fixed cost to activate production in period t

+ operational cost to produce a specific amount

Here we assume that the costs associated with the activities

of day t have the following form:

x

= d

+ s

x

+ s

= d

+ s

x

+ s

= d

+ s

…

x

+ s

= d

Properties of the polyhedron

Σ

^x

⁼ Σ

^d

^{, x}

^{> 0}

Property 1 The polyhedron of this problem is limited

(NB: even if s

is not constrained non-negative)

s

= Σ ^x

^– Σ ^d

^{⇒ |s}

^{| < ∞}

k<t k<t

x

+ x

+ x

= Σ ^d

x

, x

, x

> 0

3

i=1

x

⇒ |x

| < ∞

Properties of the polyhedron

Property 2 A concave function defined on a limited polyhedron has a minimum point in a vertex

P

f (x)

*

minimum

Proof

• Given a limited polyhedron P, let v

, …, v

be its vertices:

P = conv(v

, …, v

)

that is, each y ∈ P, and therefore a point y* of minimum of f in P, can be expressed as convex combination of the vertices of P:

• Then, if v* is a minimum of f in {v

, …, v

}, one has

• But if f is concave one has

f( y* ) = f ( Σ

^λ

^v

^{) >} Σ

^λ

^{f (v}

⁾

y* = Σ ^λ

v

with Σ ^λ

= 1, λ

> 0

p i=1

p i=1

f (v*) < Σ ^λ

f (v

) < f (y*)

p i=1

hence also v* is a minimum of f in P

A property of optimal solutions

• z* = (x*, s*) vertex ⇔ z* basic solution of Az = d z > 0

where A is a T × (2T – 1) matrix In other words, no more than T components of z* are > 0

• If the initial stock level is s

= 0, it follows

x

> d

> 0 s

+ x

> d

> 0

i.e., at least one between s

and x

must be > 0 for t = 2, …, T In other words, at least T components of z* are > 0

⇓

• Exactly one between s

and x

must be > 0 for t = 2, …, T

… and pauses production periods…

s

d

d

s

k t

x

d

s

d

x

i k–1

A property of optimal solutions

From the argument above one derives that every optimal solution

has the following structure:

Algorithm ( Wagner-Whitin, 1958 )

1) Compute the amount x

necessary to fulfill the demand from day i to day t

i+1 t

s

d

d

s

s

i

d

x

= d

+ d

+ … + d

Algorithm

2) Compute the amounts s

, s

, …, s

that one has to stock in order to fulfill d

, d

, …, d

i+1 t

d

d

i

d

x

s

= d

+ … + d

s

= d

s

= d

+ … + d

Algorithm

3) Compute the cost of producing (holding) on day i enough products to fulfill the demand from i to t:

C(i, t) = P

(x

) + G

(s

) + G

(s

) + … + G

(s

) 4) Suppose to know the minimum costs c

, c

, …, c

to be borne if one wants to fulfill the demand in a planning horizon of 0, 1, …, k–1 days

(initially, c

= 0) 5) Then the cost borne to fulfill the demand up to day k is

given by

c

= min

{c

+ C(i, k)}

Computing c _k

Minimum among:

1 c

1 2 c

1 k–2 c

+ C(k–1, k) ^{k–1 k}

+ C(2, k) ^{2 k–2 k–1 k}

+ C(3, k) ^{3 k–2 k–1 k}

+ C(1, k) ^{1 2 k–2 k–1 k}

c

= 0

1 k–1 c

+ C(k, k) ^k

Example 1

cost

level

1

x

s

5

1/2

1/3

x

2

s

3

1/3 2/3

3

x

s

4

2/3

1/6

s

4

x

6

1/6 2/3

5

x

2

1

= 10

Example 1

cost

level

1/2

1/3 1/3

2/3 2/3

1/6

1/6 2/3

1

= 10 Construct matrix C of the C(i, t)’s

P

(d

) P

(d

+ d

) + G

(d

) P

(d

+ d

+ d

) + G

(d

+ d

) + G

(d

) … P

(d

) P

(d

+ d

) + G

(d

) …

C = P

(d

) …

Production of day 1, covering the amount required in days 1, 2 e 3

Inventory on day 1 to cover the amount required in days 2 e 3

Inventory on day 2 to cover the amount required in day 3

Example 1

cost

level

1/2

1/3 1/3

2/3 2/3

1/6

1/6 2/3

1

= 10

d

= 5 d

= 3 d

= 4 d

= 6 d

= 2

P

(d

) P

(d

+ a

) + G

(d

) P

(d

+ d

+ d

) + G

(d

+ d

) + G

(d

) … P

(d

) P

(d

+ d

) + G

(d

) …

C = P

(d

) …

P

(5) P

(8) + G

(3) P

(12) + G

(7) + G

(4) P

(3) P

(7) + G

(4)

P

(4)

Example 1

cost

level

1/2

1/3 1/3

2/3 2/3

1/6

1/6 2/3

1

= 10

d

= 5 d

= 3 d

= 4 d

= 6 d

= 2 C =

(15 + 5) (15 + 8) + (10 + 3) (15 + 12) + (10 + 7) + (5 + 4) (10 + 3) (10 + 7) + (5 + 4)

(15 + 4)

1 3

2 3 1

2

1 3 2 3 1 2

1 3 1

3 1 2

2 3

C(1,1) = 17 ,5 C(1,2) = 30 ,0 C(1,3) = 41 ,0 … C(2,2) = 11 ,0 C(2,3) = 20 ,0 … C(3,3) = 17 ,7 …

…

Example 1

cost

level

1/2

1/3 1/3

2/3 2/3

1/6

1/6 2/3

1

= 10 Based on the C(i, t)’s we can now compute:

c

= C(1, 1) = 17 ,5

c

= min{C(1, 2); c

+ C(2, 2)} = min{30 ,0 ; 17 ,5 + 11 ,0 } = 28 ,5

c

= min{C(1, 3); c

+ C(2, 3); c

+ C(3, 3)} =

= min{41 ,0 ; 17 ,5 + 20 ,0 ; 28 ,5 + 17 ,7 } = 37 ,5

… and so on

Example 1

Based on the C(i, t)’s we can now compute:

c

= C(1, 1) = 17 ,5

c

= min{C(1, 2); c

+ C(2, 2)} = min{30 ,0 ; 17 ,5 + 11 ,0 } = 28 ,5

c

= min{C(1, 3); c

+ C(2, 3); c

+ C(3, 3)} =

= min{41 ,0 ; 17 ,5 + 20 ,0 ; 28 ,5 + 17 ,7 } = 37 ,5

… and so on

… and so on

Up to T = 1 the optimal solution is clearly……..

5

1

5

Up to T = 3 the optimal solution is ..……

7

2

3

3

4 5 4

1

5

Up to T = 2 the optimal solution is………

5

1

5

2

3

3

Example 2 ( ^data )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

300 250 250 200 200 200

80 210 315 270 240 120

Production cost

Q Demand

0 20.000 40.000 60.000 80.000 100.000 120.000 140.000 160.000 180.000 200.000

50 150 250 350 450 550 650 750

production cost in the first two months inventory cost in the first two months

Example 2 ( computing P _t )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

from 1 to t 80 290 605 875 1115 1235

from 2 to t 210 525 795 1035 1155

from 3 to t 315 585 825 945

from 4 to t 270 510 630

from 5 to t 240 360

from 6 to t 120

300 250 250 200 200 200

from 1 to t from 2 to t from 3 to t from 4 to t from 5 to t from 6 to t Production cost

Cumulative demand Production cost

Demand

Q

= SEGNO(G9)*$E$2 + SE(G9 <= $E$15; $E$3*G9; $E$3*$E$15+ $E$4*(G9–$E$15))

G

2 3 4

9

15

E

Example 2 ( computing P _t )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

from 1 to t 80 290 605 875 1115 1235

from 2 to t 210 525 795 1035 1155

from 3 to t 315 585 825 945

from 4 to t 270 510 630

from 5 to t 240 360

from 6 to t 120

300 250 250 200 200 200

from 1 to t from 2 to t from 3 to t from 4 to t from 5 to t from 6 to t Production cost

Cumulative demand Production cost

Demand

Q

= SEGNO(G9)*$E$2 + SE(G9 <= $E$15; $E$3*G9; $E$3*$E$15+ $E$4*(G9–$E$15))

G

2 3 4

9

15

E

Production_cost(2,4)

Example 2 ( computing G _t )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

from 1 to t 80 290 605 875 1115 1235

from 2 to t 210 525 795 1035 1155

from 3 to t 315 585 825 945

from 4 to t 270 510 630

from 5 to t 240 360

from 6 to t 120

300 250 250 200 200 200

from 1 to t from 2 to t from 3 to t from 4 to t from 5 to t from 6 to t Inventory cost

Cumulative demand Production cost

Demand

Q

= MATR.PRODOTTO(D$5:D$5;E9:E9)

D E

5

9

Example 2 ( computing G _t )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

from 1 to t 80 290 605 875 1115 1235

from 2 to t 210 525 795 1035 1155

from 3 to t 315 585 825 945

from 4 to t 270 510 630

from 5 to t 240 360

from 6 to t 120

300 250 250 200 200 200

from 1 to t from 2 to t from 3 to t from 4 to t from 5 to t from 6 to t Inventory cost

Cumulative demand Production cost

Demand

Q

= MATR.PRODOTTO(D$5:E$5;F9:F10)

D E F

5

9 10

Example 2 ( computing G _t )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

from 1 to t 80 290 605 875 1115 1235

from 2 to t 210 525 795 1035 1155

from 3 to t 315 585 825 945

from 4 to t 270 510 630

from 5 to t 240 360

from 6 to t 120

300 250 250 200 200 200

from 1 to t from 2 to t from 3 to t from 4 to t from 5 to t from 6 to t Inventory cost

Cumulative demand Production cost

Demand

Q

= MATR.PRODOTTO(D$5:H$5;I9:I13)

D E F G H I

5

9 10 11 12 13

Example 2 ( computing G _t )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

from 1 to t 80 290 605 875 1115 1235

from 2 to t 210 525 795 1035 1155

from 3 to t 315 585 825 945

from 4 to t 270 510 630

from 5 to t 240 360

from 6 to t 120

300 250 250 200 200 200

from 1 to t from 2 to t from 3 to t from 4 to t from 5 to t from 6 to t Inventory cost

Cumulative demand Production cost

Demand

Q

= MATR.PRODOTTO(E$5:F$5;G10:G11)

E F G

5

10 11

Inventory_cost(2,4)

Example 2 ( computing C(i, t) )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

300 250 250 200 200 200

C(i, t) jan-feb mar-apr may-jun jul-aug sep-oct nov-dec jan-feb

mar-apr may-jun jul-aug sep-oct nov-dec Production cost

Demand Q

C(2, 4)

= Production_cost(2, 4) + Inventory_cost(2, 4)

Example 2 ( ^solution )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

300 250 250 200 200 200

C(i, t) jan-feb mar-apr may-jun jul-aug sep-oct nov-dec jan-feb C(1, 1) C(1, 2) C(1, 3) C(1, 4) C(1, 5) C(1, 6) mar-apr C(2, 2) C(2, 3) C(2, 4) C(2, 5) C(2, 6)

may-jun C(3, 3) C(3, 4) C(3, 5) C(3, 6)

jul-aug C(4, 4) C(4, 5) C(4, 6)

sep-oct C(5, 5) C(5, 6)

nov-dec C(6, 6)

c1 c2 c3 c4 c5 c6

minimum cost Production cost

Demand Q

12

D

= D$12

Example 2 ( ^solution )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

300 250 250 200 200 200

C(i, t) jan-feb mar-apr may-jun jul-aug sep-oct nov-dec jan-feb C(1, 1) C(1, 2) C(1, 3) C(1, 4) C(1, 5) C(1, 6) mar-apr C(2, 2) C(2, 3) C(2, 4) C(2, 5) C(2, 6)

may-jun C(3, 3) C(3, 4) C(3, 5) C(3, 6)

jul-aug C(4, 4) C(4, 5) C(4, 6)

sep-oct C(5, 5) C(5, 6)

nov-dec C(6, 6)

c1 c2 c3 c4 c5 c6

minimum cost Production cost

Demand Q

= MIN(E$12; D19 + E$13)

D E

12 13

19

Example 2 ( ^solution )

jan-feb mar-apr may-jun jul-aug sep-oct nov-dec

fixed 25 25 30 40 20 20

per unit up to Q 400 450 540 500 400 420

per unit over Q 120 140 180 170 140 150

Inventory cost per unit 250 200 300 300 300

80 210 315 270 240 120

300 250 250 200 200 200

C(i, t) jan-feb mar-apr may-jun jul-aug sep-oct nov-dec jan-feb C(1, 1) C(1, 2) C(1, 3) C(1, 4) C(1, 5) C(1, 6) mar-apr C(2, 2) C(2, 3) C(2, 4) C(2, 5) C(2, 6)

may-jun C(3, 3) C(3, 4) C(3, 5) C(3, 6)

jul-aug C(4, 4) C(4, 5) C(4, 6)

sep-oct C(5, 5) C(5, 6)

nov-dec C(6, 6)

c1 c2 c3 c4 c5 c6

minimum cost Production cost

Demand Q

= MIN(F$12; D$19 + F$13; E$19 + F$14)

D E F

12 13 14

19