Dynamic Programming - Worked Example

A clockmaker makes clocks to order. His order books for clocks over the next five months is shown below.

Months

January

February

March

April

May

Number of Clocks Scheduled for Delivery

1

5

3

3

2

The clocks are delivered at the end of each month. The clockmaker can make up to four clocks a month, but if more than two clocks are made in any month, he has to hire an assistant at £400 per month. Workshop costs are £250 in any month in which clocks are made and the workshop has storage space for two clocks, with each clock costing £50 a month to store. He starts in January with no clocks in stock and aims to finish in May with no clocks in stock.

To solve the problem, draw up the table below.

Stage

Demand (Number of clocks to be delivered that month)

Number of clocks in storage at start of month

Production

Number of clocks in storage at end of month

Cost







We work backwards from the end of the last month, stage 1. There can be 0, 1 or 2 clocks in storage at the start of the month but there must be no clocks in storage at the end. The number of clocks in storage plus the number of clocks produced must equal two, the number of clocks to be delivered at the end of the month.

Stage

Demand (Number of clocks to be delivered that month)

Number of clocks in storage at start of month

Production

Number of clocks in storage at end of month

Cost in £

1

2

0

2

0

250*



1

1

0

50+250=300*



2

0

0

2*50=100*

For the second stage, we include all possible options, as we did for the first stage. We must however, make the stock levels correspond, so that the stock levels at the end of the month for the second stage correspond to the stock levels at the start of the month for the first stage. A * on a cost indicates the lowest cost route backwards to that state of having a certain amount of stock at the start of that month. The total costs for first and second stage are calculated for each possible option.

Stage

Demand (Number of clocks to be delivered that month)

Number of clocks in storage at start of month

Production

Number of clocks in storage at end of month

Cost in £

1

2

0

2

0

250*



1

1

0

50+250=300*



2

0

0

2*50=100*

2

3

0

3

0

250+400++250=900*



0

4

1

250+400+300=950



1

2

0

50+250+250=550*



1

3

1

50+250+400+300=1000



1

4

2

50+250+400+100=800



2

1

0

2*50+250+250=600*



2

2

1

2*50+250+300=650



2

3

2

2*50+400+100=600

3

3

0

3

0

250+400+900=1550



0

4

1

250+400+550=1200*



1

2

0

50+250+900=1200*



1

3

1

50+250+400+550=1250



1

4

2

50+250+400+600=1300



2

1

0

2*50+250+900=1250



2

2

1

2*50+250+550=900*



2

3

2

2*50+250+400+600=1350

4

5

1

4

0

50+250+400+1200=1900*



2

3

0

2*50+250+400+1200=1950



2

4

1

2*50+250+400+900=1650*

5

1

0

1

0

Not feasible since there must be at least one clock in stock at the end of the month to satisfy demand in February



0

2

1

250+1900=2150



0

3

2

250+400+1650=2300

The least cost option is to produce two clocks in January, four clocks in February, four clocks in March, two clocks in April and two clocks in May.