ISYE 3104 Summer 2006 Homework 4 Solution
ISyE 3104: Introduction to Supply Chain Modeling:
Manufacturing and Warehousing
Instructor : Spyros Reveliotis
Summer 2006
Solutions for Homework #4
Chapter 7
14.
Demand = (6, 12, 4, 8,15, 25, 20, 5, 10, 20, 5, 12)
Starting inventory = 4
Ending inventory = 8
h = 1
K = 40
Net out starting and ending inventories to obtain
r = (2, 12, 4, 8,15, 25, 20, 5, 10, 20, 5, 20)
a) Silver Meal
Start in period 1:
C(1) = 40
C(2) = (40 + 12)/2 = 26
C(3) = [40 + 12 + (2)(4)]/3 = 20
C(4) = [40 + 12 + (2)(4) + (3)(8)]/4 = 21 Stop.
Start in period 4:
C(1) = 40
C(2) = (40 + 15)/2 = 27.5
C(3) = [40 + 15 + (2)(25)]/3 = 35 Stop.
Start in period 6:
C(1) = 40
C(2) = (40 + 20)/2 = 30
C(3) = [40 + 20 + (2)(5)]/3 = 23.3333
C(4) = [40 + 20 + (2)(5) + (3)(10)]/4 = 25 Stop.
Start in period 9:
C(1) = 40
C(2) = (40 + 20)/2 = 30
C(3) = [40 + 20 + (2)(5)]/3 = 23.3333
C(4) = [40 + 20 + (2)(5) + (3)(20)]/4 = 32.5 Stop.
Silver Meal solution: r = (2, 12, 4, | 8,15, | 25, 20, 5, | 10, 20, 5, | 20)
b) LUC
Start in period 1:
C(1) = 40/2 = 20
C(2) = (40 + 12)/(2 + 12) = 3.71
C(3) = (40 + 12 + 8) /(2 + 12 + 4) = 3.33
C(4) = (40 + 12 + 8 + 24) /(2 + 12 + 4 + 8) = 3.23
C(5) = (40 + 12 + 8 + 24 + 60) /(2 + 12 + 4 + 8 + 15) = 3.51 Stop.
Start in period 5:
C(1) = 40/15 = 2.67
C(2) = (40 + 25)/(15 + 25) = 1.625
C(3) = (40 + 25 + 40)/(15 + 25 + 20) = 1.75 Stop.
Start in period 7:
C(1) = 40/20 = 2
C(2) = (40 + 5)/(20 + 5) = 1.8
C(3) = (40 + 5 + 20)/(20 + 5 + 10) = 1.86 Stop.
Start in period 9:
C(1) = 40/10 = 4
C(2) = (40 + 20)/(10 + 20) = 2
C(3) = (40 + 20 + 10)/(10 + 20 + 5) = 2
C(4) = (40 + 20 + 10 + 60)/(10 + 20 + 5 + 20) = 2.3636
LUC solution: r = (2, 12, 4, 8, | 15, 25, | 20, 5, | 10, 20, 5, | 20)
c) Part Period Balancing
This method sets the order horizon equal to the number of periods that most closely matches the total holding cost with the setup cost, which is $40 in this problem. Therefore, we compute the absolute value of the difference between the holding and setup costs in each period and find the one with the lowest value.
Start in period 1:
# of Periods Holding Cost Abs Value of (Holding - Setup)
2 12 28
3 20 20
4 44 4 ß closest
Start in period 5:
# of Periods Holding Cost Abs Value of (Holding - Setup)
2 25 15 ß closest
3 65 25
Start in period 7:
# of Periods Holding Cost Abs Value of (Holding - Setup)
2 5 35
3 25 15 ß closest
4 85 45
Start in period 10:
# of Periods Holding Cost Abs Value of (Holding - Setup)
2 5 35
3 45 5 ß closest
Part Period Balancing solution: r = (2, 12, 4, 8, | 15, 25, | 20, 5, 10, | 20, 5, 20)
d) Cost comparison of three methods.
1. SM incurs a setup cost of $200 from the 5 setups and a holding cost of 20+15+30+30 = $95. The total cost is $295.
2. LUC incurs a setup cost of $200 from the 5 setups and a holding cost of 44+25+5+30 = $104. The total cost is $304.
3. PPB incurs a setup cost of $160 from the 4 setups and a holding cost of 44+25+25+45 = $139. The total cost is $299.
In this case, Silver Meal is the least expensive method.
17.
a) Average demand = (335 + 200 + 140 + 440 + 300 + 200) / 6 = 269.17
EOQ = = 599
Week / 1 / 2 / 3 / 4 / 5 / 6Demand / 335 / 200 / 140 / 440 / 300 / 200
Production / 599 / 0 / 599 / 0 / 599 / 0
Inventory / 264 / 64 / 523 / 83 / 382 / 182
b) Silver Meal
Start in period 1:
C(1) = 200
C(2) = [200 + (200)(0.3)]/2 = 130
C(3) = [(2)(130) + (2)(140)(0.3)]/3 = 114.67
C(4) = [(3)(114.67) + (3)(440)(0.3)]/4 = 185 Stop.
Start in period 4:
C(1) = 200
C(2) = [200 + (300)(0.3)]/2 = 145
C(3) = [(2)(145) + (2)(200)(0.3)]/3 = 136.67 Stop.
Hence y1= 335 + 200 + 140 = 675, y4= 440 + 300 + 200 = 940
c) LUC
Start in period 1:
C(1) = 200/335 = 0.597
C(2) = [200 + (200)(0.3)]/(335 + 200) = 0.486
C(3) = [200 + (200)(0.3) + (140)(2)(0.3)]/(335 + 200 + 140) = 0.510 Stop.
Start in period 3:
C(1) = 200/140 = 1.428
C(2) = [200 + (400)(0.3)]/(140 + 440) = 0.572
C(3) = [200 + (400)(0.3) + (300)(2)(0.3)]/(140 + 440 + 300) = 0.582 Stop.
Start in period 5:
C(1) = 200/300 = 0.67
C(2) = [200 + (200)(0.3)]/(300 + 200) = 0.52 Stop.
Hence y1= 335 + 200 = 535, y3= 140 + 440 = 580, y5 = 300 + 200 = 500
d) Part Period Balancing
Start in period 1:
# of Periods Holding Cost Abs Value of (Holding - Setup)
2 60 140
3 144 56 ß closest
4 540 340
Start in period 4:
# of Periods Holding Cost Abs Value of (Holding - Setup)
2 90 110
3 210 10 ß closest
r = (335, 200, 140, | 440, 300, 200)
e) Cost comparison
1. Lot-for-lot costs = 6(200) = $1200
2. EOQ costs: 3(200) + (0.3)(264 + 64 + 523 + 83 + 382 + 102) = $1049.4
3. SM costs: 2(200) + (0.3)(200 + 280 + 300 + 400) = $754
4. LUC costs: 3(200) + (0.3)(200 + 440 + 200) = $852
5. PP costs: same as SM.
The Silver Meal and Part Period Balancing heuristics resulted in the same least expensive costs.
19. Using the hint the modified requirements vector is (10, 3, 0, 26, 23), K = 30, h = 1. Define
cij : the setup and holding cost of ordering in period i to meet requirements through period j-1 (notice that these quantities correspond to the costs of the various arcs appearing in the “shortest path” formulation of the problem).
Then, for 1≤ i ≤ 5, i +1≤ j ≤ 6, we have:
c12 = 30
c13 = 30 + 3 = 33
c14 = 30 + 3 + 0 = 33
c15 = 30 + 3 + (26)(3) = 111
c16 = 30 + 3 + (26)(3) +(23)(4) = 203
c23 = 30
c24 = 30 + 0 = 30
c25 = 30 + (26)(2) = 82
c26 = 30 + (26)(2) + (23)(3) = 151
c34 = 30
c35 = 30 + 26 = 56
c36 = 30 + 26 + (23)(2) = 102
c45 = 30
c46 = 30 + 23 = 53
c56 = 30
The optimal solution can be computed using the Wanger-Whitin algorithm in the forward sense, as presented in class, or in the backward sense, as presented in your textbook (in general, the forward version of this type of algorithms is preferred over the backward one, since it is deemed to be more intuitive). Below, we demonstrate both.
The forward verion of the Wagner-Whitin algorithm will be illustrated first; notice the employment of the cij variables in the implementation of this algorithm that demonstrates the connection of the concepts underlying this algorithm to those underlying the shortest path formulation.
f1 = c12 =30 at i = 1
f2 = min = min = 33 at i = 1
f3 = min = min = 33 at i = 1
f4 = min = min = 63 at i = 4
f5 = min = min = 86 at i = 4
Production takes place next in periods 1 and 4, with y1 = r1 + r2 + r3 = 13 and y4 = r4 + r5 = 49. The optimal cost is 2(20)+3+23 = $86.
The backward version of the Wanger-Whitin algorithm for this problem is as follows:
f6 = 0
f5 = 30 at j = 6
f4 = min = min = 53 at j = 6
f3 = min = min = 83 at j = 4
f2 = min = min = 83 at j = 4
f1 = min = min = 86 at j = 4
The solution is the same as the one obtained by the forward dynamic programming method.
22. The given information is
r = (335, 200, 140, 440, 300, 200)
K = $200
h = 0.30
The resulting cij matrix for this problem is:
2 / 3 / 4 / 5 / 6 / 71 / 200 / 260 / 344 / 740 / 1100 / 1400
2 / 200 / 242 / 506 / 776 / 1016
3 / 200 / 332 / 512 / 692
4 / 200 / 290 / 410
5 / 200 / 260
6 / 200
As in problem 17, both forward and backward versions of the WW algorithm can be used. We illustrate the backward version here:
f6 = c67 = 200
f5 = = min (400, 260) = 260 at j = 7.
f4 = = min = 410 at j = 7.
f3 = = min = 592 at j = 5.
f2 = = min = 652 at j = 4.
f1 = = min = 754 at j = 4.
The minimum cost is thus 754. In order to determine the optimal policy, we start with f1 and retrace the optimal solutions at the correct stages. Since in period 1 the optimal i = 4, it follows that y1 = r1 + r2 + r3 = 675, y2 = 0, y3 = 0. The next period of ordering is period 4. Since the optimal value of j corresponding to f4 is j = 7, it follows that y4 = r4 + r5 + r6 = 940 and y5 = y6 = 0. Note that this is the same solution obtained by the Silver-Meal heuristic.
27. Because of the maximum order size constraint, we first check the feasibility condition: for j = 1, …, n. Equivalently, we may check if is less than c=20 for all j.
Feasibility check:
r1 / =2(r1+r2)/2 / =(2+12)/2 / =7
(r1+r2+r3)/3 / =(2+12+4)/3 / =6
(r1+r2+r3+r4)/4 / =(2+12+4+8)/4 / =6.5
(r1+r2+r3+r4+r5)/5 / =(2+12+4+8+25)/5 / =10.2
(r1+r2+r3+r4+r5+r6)/6 / =(2+12+4+8+25+15)/6 / =11
(r1+r2+r3+r4+r5+r6+r7)/7 / =(2+12+4+8+25+15+20)/7 / =12.2
(r1+r2+r3+r4+r5+r6+r7+r8)/8 / =(2+12+4+8+25+15+20+5)/8 / =11.3
(r1+r2+r3+r4+r5+r6+r7+r8+r9)/9 / =(2+12+4+8+25+15+20+5+10)/9 / =11.2
(r1+r2+r3+r4+r5+r6+r7+r8+r9+r10)/10 / =(2+12+4+8+25+15+20+5+10+20)/10 / =12.1
(r1+r2+r3+r4+r5+r6+r7+r8+r9+r10+r11)/11 / =(2+12+4+8+25+15+20+5+10+20+5)/11 / =11.4
(r1+r2+r3+r4+r5+r6+r7+r8+r9+r10+r11+r12)/12 / =(2+12+4+8+25+15+20+5+10+20+5+20)/12 / =12.1
All the ratios are less than 20, so there exists a feasible solution.
Initial Solution:
Next, we obtain a feasible solution by back-shifting demands in the periods that is higher than 20. Period 5 has a demand of 25 units, which is 5 units higher than the maximum order size. The 5 units of excess is back-shifted to period 4, yielding a modified requirement schedule: r’ = (2, 12, 4, 8, 20, 20, 20, 5, 10, 20, 5, 20). This is a feasible schedule and the relevant data is shown in the following table:
Month / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12r' / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
c / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20
y / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
Excess cap. / 18 / 8 / 16 / 12 / 0 / 0 / 0 / 15 / 10 / 0 / 15 / 0
Improvement Steps:
Starting from the last period, consider shifting the demand to earlier periods:
From Period / To Period / Shift demand / Additional Holding cost12 / 11 / 15 / = (12-11)(15)(1) = 15
12 / 9 / 5 / = (12-9)(5)(1) = 15
The saving in setup cost of $40 is greater than the additional holding costs.
Month / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12r' / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
C / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20
15 / 20 / 0
Y / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
5 / 0
Excess cap. / 18 / 8 / 16 / 12 / 0 / 0 / 0 / 15 / 10 / 0 / 15 / 0
Shifting demands in period 11 to earlier periods does not result in a saving, but period 10 does.
From Period / To Period / Shift demand / Additional Holding cost10 / 9 / 5 / = (10-9)(5)(1) = 5
10 / 8 / 15 / = (10-8)(15)(1) = 30
Again, the saving in setup cost of $40 is greater than the additional holding costs.
Month / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12r' / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
c / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20
20
20 / 15 / 0 / 20 / 0
y / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
0
0 / 5 / 0
Excess cap. / 18 / 8 / 16 / 12 / 0 / 0 / 0 / 15 / 10 / 0 / 15 / 0
Backshifting demands from periods 9, 8, 7, 6, or 5 does not result in a saving.
The next improvement step comes in period 4.
From Period / To Period / Shift demand / Additional Holding cost4 / 3 / 8 / = (4-3)(8)(1) = 8
Month / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12
r' / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
c / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20
20
12 / 0 / 20 / 15 / 0 / 20 / 0
y / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
0
8 / 20 / 0 / 5 / 20 / 0 / 20
Excess cap. / 18 / 8 / 16 / 12 / 0 / 0 / 0 / 15 / 10 / 0 / 15 / 0
Finally, backshift demands from period 3 as follows:
From Period / To Period / Shift demand / Additional Holding cost3 / 2 / 8 / = (3-2)(8)(1) = 8
3 / 1 / 4 / = (3-1)(4)(1) = 8
Month / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12
r' / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
c / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20 / 20
0 / 20
6 / 20 / 12 / 0 / 20 / 15 / 0 / 20 / 0
y / 2 / 12 / 4 / 8 / 20 / 20 / 20 / 5 / 10 / 20 / 5 / 20
20 / 0
14 / 0 / 8 / 20 / 0 / 5 / 20 / 0 / 20
Excess cap. / 18 / 8 / 16 / 12 / 0 / 0 / 0 / 15 / 10 / 0 / 15 / 0
The capacitated solution is y =(6, 20, 0, 0, 20, 20, 20, 20, 20, 0, 20, 0)
50.
b) Using POQ, one will never order in periods in which there is positive inventory, which we know from the results of section 3 is optimal. Hence, this method is likely to be better than simple EOQ.
c) This method orders a fixed number of periods of supply and ignores the magnitudes of the requirements. The three heuristic methods we discussed (S/M, PPB, and LUC) do take the sizes of demands into account and for that reason are more likely to yield lower cost solutions. However, the computations are simpler with this method.
d) From problem 17, we have
EOQ = 599
∑ ri = 1615 which gives l = 1615/6 = 269.17
P = EOQ/l = 599/269.17 = 2.23
which we round to 2. Hence, the POQ solution is
y = (535, 0, 580, 0, 500, 0).
The cost of this solution is (3)(200)+(0.30)(200+440+200) = 852.
9