Finn and Lea own a cake business. Finn does all the baking while Lea does all the decorating. One day they need to complete five cake orders. The order in which they complete the cakes doesn’t matter, however all cakes need to be baked before they can be decorated. A cake can be decorated at any time after it has been baked. Also Finn and Lea can each work on only one cake at a time.
The times to bake and decorate each of the cakes are shown in the table below.
| Order Number | Cake Type | Baking Time (min) | Decorating Time (min) |
|---|---|---|---|
| \(1\) | Carrot Cake | \(50\) | \(20\) |
| \(2\) | Vanilla Birthday Cake | \(30\) | \(60\) |
| \(3\) | Strawberry Cheesecake | \(70\) | \(40\) |
| \(4\) | Rainbow Layer Cake | \(100\) | \(90\) |
| \(5\) | Angel Food Cake | \(80\) | \(10\) |
If Finn and Lea start working on these orders at 9:30 a.m., what is the earliest time that they can be completely finished all five cakes? Justify your answer.
The sum of all the baking times is \(330\) minutes. Similarly, the sum of all the decorating times is \(220\) minutes. Since \(330>220\), we can conclude that it will take at least \(330\) minutes to complete all the orders. Furthermore, since the last cake to be baked still needs to be decorated after that, it is not possible to complete all the orders in \(330\) minutes. The shortest decorating time is \(10\) minutes, so the shortest possible time to complete all the orders is \(330+10=340\) minutes. Now we need to see if we can arrange the orders in such a way that they can all be completed in \(340\) minutes.
If we put the orders with the shortest decorating times at the end, then Finn won’t be waiting a long time after he has finished baking. Similarly, if we put the orders with the shortest baking times at the beginning, then Lea won’t be waiting a long time before she can start decorating. We will look at the baking and decorating times from smallest to largest and place orders with shorter baking times at the beginning, and orders with shorter decorating times at the end.
The smallest time is a decorating time of \(10\) minutes for Order \(5\). So we place that order last.
| Position | \(1^\textrm{st}\) | \(2^\textrm{nd}\) | \(3^\textrm{rd}\) | \(4^\textrm{th}\) | \(5^\textrm{th}\) |
|---|---|---|---|---|---|
| Order # | 5 |
The next smallest time is a decorating time of \(20\) minutes for Order \(1\). We place that order second last.
| Position | \(1^\textrm{st}\) | \(2^\textrm{nd}\) | \(3^\textrm{rd}\) | \(4^\textrm{th}\) | \(5^\textrm{th}\) |
|---|---|---|---|---|---|
| Order # | 1 | 5 |
The next smallest time is a baking time of \(30\) minutes for Order \(2\). We place that order first.
| Position | \(1^\textrm{st}\) | \(2^\textrm{nd}\) | \(3^\textrm{rd}\) | \(4^\textrm{th}\) | \(5^\textrm{th}\) |
|---|---|---|---|---|---|
| Order # | 2 | 1 | 5 |
The next smallest time is a decorating time of \(40\) minutes for Order \(3\). We place that order third last.
| Position | \(1^\textrm{st}\) | \(2^\textrm{nd}\) | \(3^\textrm{rd}\) | \(4^\textrm{th}\) | \(5^\textrm{th}\) |
|---|---|---|---|---|---|
| Order # | 2 | 3 | 1 | 5 |
The remaining order to be placed is Order \(4\). We place that order in the empty spot in second position. The positions of all of the orders are now determined.
| Position | \(1^\textrm{st}\) | \(2^\textrm{nd}\) | \(3^\textrm{rd}\) | \(4^\textrm{th}\) | \(5^\textrm{th}\) |
|---|---|---|---|---|---|
| Order # | 2 | 4 | 3 | 1 | 5 |
Now we create a timeline to help calculate how long it takes to complete the orders in this way. The timeline shows the time slots during which each order is baked and decorated. Since baking and decorating different cakes can happen at the same time, there are two simultaneous schedules shown on the timeline, one for baking and one for decorating. Finn bakes the cakes back-to-back, and Lea starts decorating each cake after it has finished baking and once Lea is available.
Using the timeline, we can see it takes \(340\) minutes to complete the orders, so we have found an arrangement that allows all orders to be completed in \(340\) minutes.
Since \(340\) minutes is equal to \(5~\text{h}~40~\text{min}\), and Finn and Lea start working on the orders at \(9\text{:}30\) a.m., it follows that they will be completely finished at \(3\text{:}10\) p.m., at the earliest.
Note: It turns out that this is not the only arrangement that produces a time of \(340\) minutes. The complete list of arrangements of order numbers that produce a time of \(340\) minutes is below, where the order numbers are written in the order that they are completed.
\(1,~2,~4,~3,~5\)
\(2,~1,~4,~3,~5\)
\(2,~3,~4,~1,~5\)
\(2,~4,~1,~3,~5\)
\(2,~4,~3,~1,~5\)
\(3,~2,~4,~1,~5\)
\(4,~1,~2,~3,~5\)
\(4,~1,~3,~2,~5\)
\(4,~2,~1,~3,~5\)
\(4,~2,~3,~1,~5\)
\(4,~3,~1,~2,~5\)
\(4,~3,~2,~1,~5\)
Connections to Computer Science
To solve this problem we used a greedy strategy, which is a strategy for solving optimization problems. Using this strategy, we made the optimal choice at each step, in hopes of finding the optimal solution. Greedy strategies do not always produce optimal solutions, but are still useful because they are easy to describe and implement, and often give a good approximation to the optimal solution.