Questions and solutions FOM (1CV00) 1 July 2020

Part Rob Basten

Version 31 March 2021

1. Henk & Ingrid: Inventory control - EOQ (5 points).............................................................................. 2

2. HappyCow: Inventory control – Multi-product EPQ (12 points)......................................................... 3
3. Newsvendor Vera: Simple newsvendor problem (5 points) ............................................................... 5
4. Newsvendor with salvage value (10 points) ....................................................................................... 6
5. Xess Xava’s summer job: Production scheduling (12 points) ............................................................. 7
6. Guusje’s e-bikes: Inventory control – Lot sizing (8 points) ................................................................. 9
7. Traveling salesperson Pedro: TSP (8 points) ..................................................................................... 10
1. Henk & Ingrid: Inventory control - EOQ (5 points)
Question

Henk is living in a small studio with a balcony. Especially on warm Summer

evenings, he likes to drink a bottle of beer outside. Still, even if it’s cold or rainy,
he drinks one bottle of beer a day. He drinks quite expensive beer that is
brought to him directly from a monastery in Belgium. The beer costs 5 euros per
bottle, the costs of ordering a delivery of beer is 10 euros, and his holding costs
are 1% per day. For convenience, he simply orders a new delivery every 14
days. His friend Ingrid wonders how much money he is wasting by sticking to
this schedule, instead of optimizing the delivery frequency. What would be the
optimal delivery frequency (in days, round to zero decimals)? And how much
money is Henk wasting on average per day, in other words, what are his
average daily costs minus the optimal daily costs (in cents, round to zero
decimals)?

Henk’s optimal delivery frequency is [eoq1] days (round to zero decimals), and
he is thus wasting [eoq2] cents on average per day (round to zero decimals).

Solution

The EOQ is given on the formula sheet, so [eoq1] can be found by filling out the
formula:
[eoq1] = (2 K D / h)½
= (2 * 10 * 1 / (0.01 * 5))½
= (20 / 0.05)½
= 20 bottles
Since Henk drinks one bottle a day, this means he should order every 20 days.

The costs per day consist of fixed ordering costs, holding costs, and purchasing
costs. The purchasing costs do not depend on the order size (or, equivalently,
the order frequency) and can thus be ignored. Using logical reasoning, you can
see that the costs per day given the order size Q are: K D / Q + h Q / 2. That
means that Henk is wasting:
[eoq2] = K D / 14 + h 14 / 2 – K D / [eoq1] – h [eoq1] / 2
= 10 / 14 + 0.05 * 14 / 2 – 10 / 20 – 0.05 * 20 / 2
= 6.43
= 6 cents on average per day
2. HappyCow: Inventory control – Multi-product EPQ (12 points)
Question

HappyCow is a company producing milk and similar products. The milk is packed
on a single packaging machine. There are three types of milk, each with a fairly
constant demand rate. For every production change thorough cleaning is
required: the change-over costs are 50 euros per change-over and takes 1 hour.
Milk can be sold immediately, so before the production run is completed. The
demand for the three types of milk in liters per week, the holding costs per liter
per week, and the production speed in liters per hour are given by:

Type of milk Butter milk (B) Full cream (F) Skimmed (S)
Demand (D i ) 12000 2000 6000
Holding costs
0.25 0.20 0.15
(h i )
Production
750 500 900
speed (P i )

The packaging machine is available for 40 hours per week. Every type of milk is
produced in every cycle and the cycle has a duration of T weeks. Give the
explicit formula for the total costs per cycle as a function of the cycle duration:
C(T), that expresses the total costs per cycle only in terms of T (for instance: 5
+ 10 T, or 3 + 2TT, where TT = T2).

C(T) = [CTformula]

Determine the maximum number of cycles per week given the capacity
restrictions (round to 2 decimals if needed).

Maximum number of cycles = [max] (round to 2 decimals, if needed)

Ignoring the capacity restrictions and using the formula that you have derived,
you could determine that the best cycle time, i.e., the best cycle length, is 0.32
weeks.

Determine the total costs per week and the production quantity for Skimmed
milk per cycle (in both cases, round to 2 decimals if needed).

Total Costs per week = [tc] (round to 2 decimals, if needed)

Production Quantity Skimmed milk = [pcsm] (round to 2 decimals, if needed)
Solution

This is an example of a multi-product Economic Production Quantity problem.

When products are produced in a cycle with length T, every product has a set-up
every T periods. For the holding costs we now use the alternative h i ’= h i (1-
D i /P i ) (notice that we need to have the same time unit for all variables), which
takes into account the effect of the production speed on the inventory level. This
results in the following formula for costs per cycle:
[CTformula] = C(T)
𝟏𝟏 𝑫𝑫
= ∑𝟑𝟑𝒊𝒊=𝟏𝟏(𝑺𝑺 + 𝒉𝒉𝒊𝒊 (𝟏𝟏 − 𝟒𝟒𝟒𝟒𝑷𝑷𝒊𝒊 )𝑫𝑫𝒊𝒊 𝑻𝑻𝟐𝟐 )
𝟐𝟐 𝒊𝒊
= 3*50
+ ½T2(0.25(1-12000/(40*750))12000
+ 0.20(1-2000/(40*500))2000
+ 0.15(1-6000/(40*900))6000)
= 150 + 1455 T2

The capacity restriction is that the sum of the production hours plus setup times
𝑫𝑫
per week cannot exceed 40. Per week we have ∑𝟑𝟑𝒊𝒊=𝟏𝟏 𝑷𝑷𝒊𝒊 production hours, and
𝒊𝒊
every cycle takes 3 setup hours. The maximum number of cycles is therefore:
𝑫𝑫
[max] = (40 − ∑𝟑𝟑𝒊𝒊=𝟏𝟏 𝑷𝑷𝒊𝒊 )/3
𝒊𝒊
12000 2000 6000
= (40 − ( + + ))/3
750 500 900
= (40 − (16 + 4 + 6.67))/3
= 4.44

Using the CTformula and p.232/233, Section 4.9, of Nahmias & Olsen, we could
find the best cycle time as follows:
[bct] = (150/1455)½
= 0.32 weeks
We don’t ask this in a closed book exam (the 2020 exams were open book)

The total costs per week are:

[tc] = C([bct])/[bct] = 150/0.32 + 1455*0.32 = 934.35

In every cycle, the fraction of the weekly demand per product that we produce is
[bct]. So, the production quantity of full cream milk is:
[pcsm] = [bct]*6000 = 0.32*6000 = 1920
3. Newsvendor Vera: Simple newsvendor problem (5 points)
Question

Newsvendor Vera can buy newspapers at a cost of 2 euros, which she sells
during the day at a price of 3 euros. The demand for her newspapers is
discretely distributed, with the following probability mass function:
Demand 1 2 3 4 5
Probability 0.05 0.25 0.20 0.30 0.20
Whatever she has leftover at the end of the day is worthless.

Determine Vera’s expected profit function E D [W(Q, D)] for Q=1,..,6 and fill in
the values in the table below:
Order (Q) 1 2 3 4 5 6
Expected profit [p1] [p2] [p3] [p4] [p5] [p6]

Solution

Vera’s expected profit = ∑𝟔𝟔𝒅𝒅=𝟏𝟏[𝐏𝐏(𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅 = 𝒅𝒅) min(Q,d) p] - c Q

[p1] = p–c
[p2] = 1.95p – 2c
[p3] = 2.65p – 3c
[p4] = 3.15p – 4c
[p5] = 3.35p – 5c
[p6] = 3.35p – 6c

[p1] = 3–2=1
[p2] = 1.95*3 – 2*2 = 1.85
[p3] = 2.65*3 – 3*2 = 1.95
[p4] = 3.15*3 – 4*2 = 1.45
[p5] = 3.35*3 – 5*2 = 0.05
[p6] = 3.35*3 – 6*2 = -1.95
4. Newsvendor with salvage value (10 points)
Question

For the standard newsvendor problem, the marginal expected profit of adding
one more unit on stock is:
Δ Q E D {W(Q,D)} = E D {W(Q+1,D)} - E D {W(Q,D)} = (p – c) – (p) P{D≤Q}.

Give the marginal expected profit of adding one more unit on stock
Δ Q E D {W’(Q,D)} for the generalized problem in which we include a salvage value
a for every unit of product that is not sold at the end of the period, i.e., the
newsvendor gets this back for any inventory left over.

Δ Q E D {W’(Q,D)} = [nbs1] P{D≤Q}).

For the standard newsvendor problem, the profit function for a given realized
demand d ≥ 0 and a given order quantity Q > 0 is:
w(Q,d) = p min{Q,d} - c Q.

Give the profit function w’’(Q,d) for the generalized problem in which we include
both a salvage value a for every unit of product that is not sold at the end of the
period, i.e., the newsvendor gets this back for any inventory left over, and a
fixed cost b that is incurred by the newsvendor if (s)he orders any
amount Q greater than 0, i.e., (s)he pays b + c Q if (s)he orders Q > 0.

For Q > 0, w’’(Q,d) = [nbs2].

Solution

Δ Q E D {W’(Q,D)} = (p – c) – (p – a) P{D≤Q})

[nbs1] = (p-c)-(p-a)

w’’(Q,d) = [nbs2] = p min{Q,d} + a max {0,Q-d} – c Q – b

5. Xess Xava’s summer job: Production scheduling (12 points)
Question

Xess Xava is old enough to take on a summer job at a restaurant. He starts

working at 9:00 in the morning. The tasks, the time they take (duration 1), and
their agreed end time, i.e., due date, can be found in the following table (you
may ignore duration 2 for now).
Agreed end time
Job Duration 1 Duration 2
(due date)
D = Dish washing 30 12:00 60
I = Intake of guests 20 10:00 10
S = Shopping 80 11:50 40
R = Resting 70 13:00 90
V = Vacuum cleaning 55 10:40 80
C = Car washing 40 10:20 30

In which order should he perform his tasks, given that he wants to minimize the
average flow time of the jobs?

The best sequence is: [flowseq] (six letters without spaces or dashes, e.g.,
DISRVC)

The resulting average flow time is: [avgflow] (round to zero decimals, if needed)

What is the best sequence if Xess Xava wants to finish as many jobs as possible
in time?

The best sequence is: [tardyseq] (six letters without spaces or dashes, e.g.,
DISRVC)

The number of jobs he doesn’t finish in time is: [tardynum]

Since Xess Xava likes some intellectual challenge, he now tries to find the
sequence of jobs that makes him finish as early as possible on day 2. This
means he ignores the agreed end time and looks at duration 1 for the duration
of the jobs on day 1 and at duration 2 for the duration of the jobs on day 2. The
restriction that he takes into account is that he can only start working on a job
on day 2 at the time that he has finished that job on day 1. So, if he starts with
car washing on day 1 at 9:00, he finishes at 9:40, meaning that he can start
with car washing on day 2 at 9:40 (or later).

In what order will Xess Xava perform his jobs?

The best sequence is: [newseq] (six letters without spaces or dashes, e.g.,
DISRVC)

He finishes on day 2 at: [newtime] (HH:MM, e.g., 23:59)

Solution

Using the shortest processing time gives the minimal average flow time (and
lateness):
[flowseq] = IDCVRS
[avgflow] = 815 / 6 = 136

Using Moore’s algorithm gives the minimal number of tardy jobs:

[tardyseq] = ICSDRV
[tardynum] = 1 (vacuum cleaning)

The best sequence to perform the jobs on both days is found using Johnson’s
algorithm:
[newseq] = DVRSCI
[newtime] = 14:40
6. Guusje’s e-bikes: Inventory control – Lot sizing (8 points)
Question

Guusje is responsible for the planning and lotsizing of various types of E-bikes.
One very popular type is the Corona model. The set-up costs for starting a batch
for this model are 140 euro and the daily holding costs are 2 euro per bike per
day. The demand for the next seven days is given as follows:
day 1 2 3 4 5 6 7
demand 20 25 14 20 9 7 12

As a lotsizing method, Guusje uses the method that guarantees the minimum
costs for this problem. Solve this problem with that method and fill in the
numbers in the following statements.

The minimum costs for the first four periods are [c4]. (In other words: What are
the optimal costs if you would need to solve this problem for the first four
periods only?)

The set-ups will take place in periods 1, [p2], … (you only need to give the
second period with a set-up, even if there are more than two in total).

The minimum costs for the complete seven period problem are [c7].

Solution

Guusje obtains the solution with minimum costs using Wagner-Whitin.

The results are:

period 1 2 3 4 5 6 7
demand 20 25 14 20 9 7 12
1 140 190 246 366 438 - -
2 280 308 388 442 - -
3 330 370 406 - -
4 386 404 432 504
5 510 >510 >510
6 >510 >510
7 >510
[c4] = 366
[p2] = 4
[c7] = 504
7. Traveling salesperson Pedro: TSP (8 points)
Question

For traveling salesman Pedro, the distance between his customer locations and
the depot is given in the following table.
Locations A B C D E
A 8 13 21 9
B 8 9 17 14
C 13 9 16 11
D 21 17 16 19
E 9 14 11 19
Depot 12 10 16 23 16
What is the solution for the traveling salesman problem that Pedro faces when
he uses the “savings” algorithm, leaving from the depot? Follow the scheme
below.

First calculate the savings on a separate sheet of paper (you cannot fill them in
here).
Locations A B C D E
A
B
C
D
E

Then we make a selection (possibly some are blank).

Combination Saving

[s]

Resulting route = Depot-[r]-Depot (only give five letters, e.g., ABCDE)

Resulting total distance = [d]
Solution

Savings:
Locations A B C D E
A 14 15 14 19
B 17 16 12
C 23 21
D 20
E

Then we make a selection (possibly some are blank)

combination saving
C-D 23
21 (this makes D-E
C-E impossible and C
unreachable)
[s] = 19 (this makes E
A-E
unreachable)
16 (this makes D
B-D
unreachable)
blank blank

Resulting route = Depot-[r]-Depot = Depot-BDCEA-Depot (or the reverse route)

Resulting total distance = [d] = 10+17+16+11+9+12 = 75

Notice: Better solutions exist, but you won’t find them using the savings
method, meaning that these solutions are wrong.