## Task 4 - 280914

Three workpieces $W_{1}, W_{2}, W_{3}$ go through an assembly line with four processing machines $M_{1}, M_{2}, M_{3}, M_{4}$. Each workpiece must pass through the machines in the order $M_{1}, M_{2}, M_{3}, M_{4}$, and the order of the three workpieces must be the same at each machine.

The processing times of the workpieces on the individual machines are (in hours) given in the following table:

|  | $M_{1}$ | $M_{2}$ | $M_{3}$ | $M_{4}$ |
| :--- | :---: | :---: | :---: | :---: |
| $W_{1}$ | 4 | 1 | 2 | 1.5 |
| $W_{2}$ | 2 | 2.5 | 1 | 0.5 |
| $W_{3}$ | 2 | 3.5 | 1 | 1 |

Two workpieces can never be processed simultaneously on the same machine. The times for changing the workpieces at the machines are so small that they can be neglected.

Give an order of the three workpieces for passing through the assembly line such that the total time (the time from the entry of the first workpiece into machine $M_{1}$ to the exit of the last workpiece from machine $M_{4}$) is as small as possible! Show that the order you give with its total time is better than any other order!
(Machine designation shortened to 1,2,3,4 instead of $M_{1}, M_{2}, M_{3}, M_{4}$)

In the representations of the temporal sequence, the total time is determined for each of the six possible sequences of three workpieces, assuming that each machine receives the next workpiece (in the intended sequence) as soon as possible.

When comparing these representations, it turns out:

The sequence $W_{3}, W_{1}, W_{2}$ outperforms all other sequences with its total time.

Hints:

It is also possible to proceed in a very argumentative manner. For example, one can first determine for which sequence

- the sum of the times of the first and second workpieces in $M_{1}$ plus the sum of the times of the third workpiece in $M_{1}, M_{2}, M_{3}$, and $M_{4}$

yields the smallest possible value. Instead of the sum (1), one can more easily use

- the sum of the times of the third workpiece in $M_{2}, M_{3}$, and $M_{4}$.

According to the table in the problem text, this sum is smallest for $W_{2}$ as the third workpiece (namely 4; in contrast, it is 4.5 for $W_{1}$ and 5.5 for $W_{3}$). Then one can investigate whether for one of the sequences with $W_{2}$ as the third workpiece it holds that

- $W_{2}$ can pass through the machines $M_{1}, M_{2}, M_{3}, M_{4}$ without waiting times.

If this is the case, it follows: This sequence outperforms the total times of all sequences that do not minimize (1) or (2).

(Note: Without statement (3), such a conclusion would not be secure!) Finally, a sequence that satisfies (3) must be compared with the other one in which $W_{2}$ is also the third workpiece. The investigation of (3) and the aforementioned comparison can, for example, be carried out using the two representations above for $W_{1}, W_{3}, W_{2}$ and $W_{3}, W_{1}, W_{2}$. The consideration of (1) and (2) thus saves four such representations.

Solutions of the 1st Round 1988 adopted from [5]

### 6.30.2 2nd Round 1988, Class 9