Dynamic programming production scheduling

5 [Figure 3, printed on the insert, is provided for use in this question.]
A landscape gardener has three projects, \(A , B\) and \(C\), to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.

2. An engineering firm makes motors. They can make up to five in any one month, but if they make more than four they have to hire additional premises at a cost of \(\pounds 500\) per month. They can store up to two motors for \(\pounds 100\) per motor per month. The overhead costs are \(\pounds 200\) in any month in which work is done.
Motors are delivered to buyers at the end of each month. There are no motors in stock at the beginning of May and there should be none in stock after the September delivery. The order book for motors is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided below. \section*{Production schedule} Total cost: \(\_\_\_\_\)

6. Kris produces custom made racing cycles. She can produce up to four cycles each month, but if she wishes to produce more than three in any one month she has to hire additional help at a cost of \(\pounds 350\) for that month. In any month when cycles are produced, the overhead costs are \(\pounds 200\). A maximum of 3 cycles can be held in stock in any one month, at a cost of \(\pounds 40\) per cycle per month. Cycles must be delivered at the end of the month. The order book for cycles is Disregarding the cost of parts and Kris' time,

1. determine the total cost of storing 2 cycles and producing 4 cycles in a given month, making your calculations clear. There is no stock at the beginning of August and Kris plans to have no stock after the November delivery.
2. Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table below.

   Stage	Demand	State	Action	Destination	Value
   \multirow[t]{3}{*}{1 (Nov)}	\multirow[t]{3}{*}{2}	0 (in stock)	(make) 2	0	200
   		1 (in stock)	(make) 1	0	240
   		2 (in stock)	(make) 0	0	80
   \multirow[t]{2}{*}{2 (Oct)}	\multirow[t]{2}{*}{5}	1	4	0	\(590 + 200 = 790\)
   		2	3	0

   The fixed cost of parts is \(\pounds 600\) per cycle and of Kris' time is \(\pounds 500\) per month. She sells the cycles for \(\pounds 2000\) each.
3. Determine her total profit for the four month period.
   (3)
   (Total 18 marks)

8. A company makes industrial robots. They can make up to four robots in any one month, but if they make more than three they will have to hire additional labour at a cost of \(\pounds 400\) per month.
They can store up to two robots at a cost of \(\pounds 150\) per robot per month.
The overhead costs are \(\pounds 300\) in any month in which work is done.
Robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock after the April delivery. The order book for robots is Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table provided in the answer book.
(Total 12 marks)

7. A company assembles microlight aircraft. They can assemble up to four aircraft in any one month, but if they assemble more than three they will have to hire additional space at a cost of \(\pounds 1000\) per month.
They can store up to two aircraft at a cost of \(\pounds 500\) each per month.
The overhead costs are \(\pounds 2000\) in any month in which work is done. Aircraft are delivered at the end of each month. There are no aircraft in stock at the beginning of March and there should be none in stock at the end of July.
The order book for aircraft is Use dynamic programming to determine the production schedule which minimises the costs. Show your working in the table provided in the answer book and state the minimum production cost.
(Total 14 marks)

7. Remy builds canoes. He can build up to five canoes each month, but if he wishes to build more than three canoes in any one month he has to hire an additional worker at a cost of \(\pounds 400\) for that month. In any month when canoes are built, the overhead costs are \(\pounds 150\) A maximum of three canoes can be held in stock in any one month, at a cost of \(\pounds 25\) per canoe per month. Canoes must be delivered at the end of the month. The order book for canoes is There is no stock at the beginning of January and Remy plans to have no stock after the May delivery.

1. Use dynamic programming to determine the production schedule that minimises the costs given above. Show your working in the table provided in the answer book and state the minimum cost.
   (13) The cost of materials is \(\pounds 200\) per canoe and the cost of Remy's time is \(\pounds 450\) per month. Remy sells the canoes for \(\pounds 700\) each.
2. Determine Remy's total profit for the five-month period.
   (2)
   (Total 15 marks)

7. D2 make industrial robots. They can make up to four in any one month, but if they make more than three they need to hire additional labour at a cost of \(\pounds 300\) per month. They can store up to three robots at a cost of \(\pounds 100\) per robot per month. The overhead costs are \(\pounds 500\) in any month in which work is done. The robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock at the end of May. The order book for January to May is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided in the answer book. State the minimum cost.
(Total 14 marks)

6 Simon makes playhouses which he sells through an agent. Each Sunday the agent orders the number of playhouses she will need Simon to deliver at the end of each day. The table below shows the order for the coming week. Simon can make up to 3 houses each day, except for Wednesday when he can make at most 2 houses. Because of limited storage space, Simon can store at most 2 houses overnight from one day to the next, although the number in store does not restrict how many houses Simon can make the next day. The process is modelled by letting the stages be the days and the states be the numbers of houses stored overnight. Simon starts the week, on Monday morning, with no houses in storage. This means that the start of Monday morning has (stage; state) label ( \(0 ; 0\) ). Simon wants to end the week on Friday afternoon with no houses in storage, so the start of Saturday morning will have (stage; state) label ( \(5 ; 0\) ).

1. Explain why the (stage; state) label ( \(4 ; 0\) ) is not needed. Simon wants to draw up a production plan showing how many houses he needs to make each day. He prefers not to have to make several houses on the same day so he assigns a 'cost' that is the square of the number of houses made that day, apart from Monday when the 'cost' is the cube of the number of houses made. So, for example, if he makes 3 houses one day the cost is 9 units, unless it is Monday when the cost is 27 units.
2. Complete the diagram in the answer book to show all the possible production plans and weight the arcs with the costs. Simon wants to find a production plan that minimises the sum of the costs.
3. Set up a dynamic programming tabulation, working backwards from ( \(5 ; 0\) ), to find a production plan that solves Simon's problem.
4. Write down the number of houses that he should make each day with this plan.

7. A company assembles boats. They can assemble up to five boats in any one month, but if they assemble more than three they will have to hire additional space at a cost of \(\pounds 800\) per month. The company can store up to two boats at a cost of \(\pounds 350\) each per month.
The overhead costs are \(\pounds 1500\) in any month in which work is done.
Boats are delivered at the end of each month. There are no boats in stock at the beginning of January and there must be none in stock at the end of May. The order book for boats is Use dynamic programming to determine the production schedule which minimises the costs to the company. Show your working in the table provided in the answer book and state the minimum production cost.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A small firm produces high quality cabinets.
It can produce up to 4 cabinets each month.
Whenever at least one cabinet is made during that month, the overhead costs for that month are \(\pounds 300\). It is possible to hold in stock a maximum of 2 cabinets during any month.
The cost of storage is \(\pounds 50\) per cabinet per month.
The orders for cabinets are shown in the table below. There is no stock at the beginning of January and the firm plans to clear all stock after completing the April orders.

1. Determine the total cost of storing 2 cabinets and producing 3 cabinets in a given month.
2. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from April, to find the production schedule which minimises total costs.
3. Each cabinet is sold for \(\pounds 2000\) but there is an additional cost of \(\pounds 300\) for materials to make each cabinet and \(\pounds 2000\) per month in wages. Determine the total profit for the four-month period.

1. A company wishes to plan its production of a particular item over the coming four months based on its current orders. In each month the company can manufacture up to three of the item with the costs according to how many it makes being as follows:

There are no items in stock at the start of the period and the company wishes to meet all its orders on time and have no stock left at the end of the 4-month period. If any items are not to be supplied in the month they are made there is also a storage cost incurred of \(\pounds 400\) per item per month. The orders for each of the four months being considered are as follows: Use dynamic programming to find how many of the item the company should make in each of these four months in order to minimise the total cost for this period. \section*{Please hand this sheet in for marking} \includegraphics[max width=\textwidth, alt={}, center]{df7b056f-1446-43f1-a2fd-c0d56533550e-6_588_1285_504_276} \includegraphics[max width=\textwidth, alt={}, center]{df7b056f-1446-43f1-a2fd-c0d56533550e-6_588_1280_1361_276}

1. Bernie makes garden sheds. He can build up to four sheds each month.

If he builds more than two sheds in any one month, he must hire an additional worker at a cost of \(\pounds 250\) for that month. In any month in which sheds are made, the overhead costs are \(\pounds 35\) for each shed made that month. A maximum of three sheds can be held in storage at the end of any one month, at a cost of \(\pounds 80\) per shed per month. Sheds must be delivered at the end of the month.
The order schedule for sheds is There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery. Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost.