1
$\begingroup$

I am working through "Thinking Mathematically" by Mason, Burton and Stacey. One of the questions goes as follows:

Three slices of bread are to be toasted under a grill. The grill can hold two slices at once but only one side is toasted at a time. It takes 30 seconds to toast one side of a piece of bread, 5 seconds to put a piece in or take a piece out and 3 seconds to turn a piece over. What is the shortest time in which the three slices can be toasted?

I am wondering if I am overlooking something in my solution method, so I have come here. Some sources online say 130 seconds and others say 139. My solution, if non-fallacious, should be able to get it done in 118 seconds. The process goes as follows. Allow $T_n$ to represent the first side of the $n$th piece of toast and $T_n'$ to represent the opposite side of the $n$th piece of toast. Then, assuming a piece of toast is cooking as soon as it is placed, then the suggested sequence of events enter image description here

Sorry for the convoluted timeline in the picture, but essentially I place the first piece of toast and then the second. $T_1$ and $T_2$'s cooking time will overlap, but there is necessarily a five-second window where they do not. You flip $T_1 \to T_1'$ where $T_1'$ officially begins toasting at 38 seconds. This gives another thirty-second window (until $t = 68$) to get a lot of the time-wasting flipping and removing done. For example, $T_2$ finished at $t=40$ and the most original part of this solution is to remove $T_2$ rather than flip it over and begin cooking the other side immediately. As soon as we are done removing $T_2$ the running total will be $t=45$ at which point we immediately begin placing $T_3$ bringing us to a running total of $t=50$. Note, that $T_3$ will be done at $t = 80$. At this point, we wait until $t=68$ to remove $T_1'$ which brings us to a running total of $t = 73$, at which point we immediately begin placing $T_2'$ which we put aside before. When we are done placing $T_2'$ we will be at $t = 78$ and at $t = 80$ it will be time to flip $T_3$, which brings us to $t = 83$ and which point $T_3'$ will begin toasting. $T_3'$ will thus be done at $t = 113$ and in that time we will have to remove $T_2'$ which began cooking at $t = 78$. Finally, we remove $T_3'$ at $t = 113$ and ending at $t = 118$.

Are there any problems with this solution that I am not detecting? I think it works well, indeed if it works at all, because it uses the long 30-second windows of cooking to do all the time-consuming activities of flipping etc.

$\endgroup$

2 Answers 2

1
$\begingroup$

Assuming that (a) flipping a slice does not require removing and replacing it (so that flipping is a total of 3 seconds and not 13 seconds) and (b) messing with one slice does not interrupt the cooking of the other slice, I see no flaw in your solution.

$\endgroup$
4
  • 1
    $\begingroup$ I just ran a CPOptimizer model which obtained the same solution. Assuming I did not screw up the model, that would seem to confirm that 118 is not just feasible but optimal. $\endgroup$
    – prubin
    Apr 19, 2020 at 22:11
  • $\begingroup$ Thank You professor. Glad to have found the optimal solution! $\endgroup$ Apr 20, 2020 at 16:13
  • $\begingroup$ @prubin: It seems flawed to me. Would you be so kind as to check my answer? $\endgroup$
    – Jim
    Jan 24, 2021 at 22:48
  • $\begingroup$ @Jim: I concur with Rob Pratt's responses to your answer. $\endgroup$
    – prubin
    Jan 25, 2021 at 16:13
0
$\begingroup$

That is smart approach but I see 2 mistakes:

  1. You do not add up the 5 seconds to add the Toast 2. You assume that since the "clock" is running once the toast 1 started to grill Toast 2 magically starts to cook at time 10 implying some parallelism there in the actions which does not seem to be justified from the problem.
  2. You remove T2 at time 40 and place T3 at time 45 but you didn't add either the 5 secs to remove T2 or to add T3. I.e. you should be adding 10 hence T3 starts to cool at 55 and not 45. There is no mention of being able to remove slices/add slices at one movement.
$\endgroup$
7
  • 2
    $\begingroup$ T2 is added 5-10, toasted 10-40, and removed 40-45. T3 is added 45-50. $\endgroup$
    – RobPratt
    Jan 24, 2021 at 23:01
  • $\begingroup$ @RobPratt: By that rational then, what is the point of adding T2 at $5$? T1 and T2 could both be added at $0$ in parallel with overhead of 5 and start to grill both at 5 with that reasoning, isn't that right? $\endgroup$
    – Jim
    Jan 25, 2021 at 0:08
  • 2
    $\begingroup$ No, adding T1 and T2 are separate tasks that cannot be performed at the same time. $\endgroup$
    – RobPratt
    Jan 25, 2021 at 1:00
  • 1
    $\begingroup$ This is resource-constrained scheduling, where the toaster and the person are the two resources. The tasks/operations/actions are usually called jobs. $\endgroup$
    – RobPratt
    Jan 25, 2021 at 18:04
  • 1
    $\begingroup$ Jobs that do not require the same resource can be done in parallel. Adding T1 and adding T2 both require the person. $\endgroup$
    – RobPratt
    Jan 25, 2021 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .