and turning it into a multilayered glove progressively. Note that in his first encounter, he uses only the untouched inside of Patient # 1's glove, so it's still safe. This scheme uses (1 · N) + ((M − 1 − 1) · 1) + (1 · 0) = M + N − 2 gloves. This number cannot be reduced further. The makespan is then given by: N serial interactions to plant the gloves. max(M − 2, N) parallelized interactions for intermediate stage. N serial interactions to collect the gloves. Makespan: K · (2N + max(M − 2, N)). Clearly, the minimum G(M, N) increases the makespan significantly, sometimes by a factor of 3. Note that the benefit in the number of gloves is only 2 units. One or the other solution may be preferred depending on the relative cost of a glove judged against the longer operation time. In theory, the intermediate solution with (M + N − 1) should also occur as a candidate solution, but this requires such narrow windows on M, N and the cost parameters to be optimal that it is often ignored. Other factors The statement of the problem does not make it clear that the principle of contagion applies, i.e. if the inside of one glove has been touched by the outside of another that previously touched some person, then that inside also counts as touched by that person. Also, medical gloves are reversible; therefore a better solution exists, which uses gloves where the less numerous group are equipped with a glove each, the more numerous in pairs. The first of each pair use a clean interface, the second reverse the glove. References Mathematical optimization in business