Details
A naive approach would be to estimate the number of gloves as simply G(M, N) = MN. But this number can be significantly reduced by exploiting the fact that each glove has two sides, and it is not necessary to use both sides simultaneously.
A better solution can be found by assigning each person his or her own glove, which is to be used for the entire operation. Every pairwise encounter is then protected by a double layer. Note that the outer surface of the doctors's gloves meets only the inner surface of the patients's gloves. This gives an answer of M + N gloves, which is significantly lower than MN.
The makespan with this scheme is K · max(M, N), where K is the duration of one pairwise encounter. Note that this is exactly the same makespan if MN gloves were used. Clearly in this case, increasing capital cost has not produced a shorter operation time.
The number G(M, N) may be refined further by allowing asymmetry in the initial distribution of gloves. The best scheme is given by:
- Doctor # 1 wears N gloves, layered one on top of another. He visits the N patients in turn, leaving the outermost glove behind with each.
- Doctors # 2 to (M − 1) wear one glove each, and follow the double-layered protocol at each interaction, as described above.
- Doctor # M doesn't wear one of his own, but he visits all the N patients, collecting their gloves in turn 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.
Read more about this topic: Safe Sex Makespan
Famous quotes containing the word details:
“Different persons growing up in the same language are like different bushes trimmed and trained to take the shape of identical elephants. The anatomical details of twigs and branches will fulfill the elephantine form differently from bush to bush, but the overall outward results are alike.”
—Willard Van Orman Quine (b. 1908)
“If my sons are to become the kind of men our daughters would be pleased to live among, attention to domestic details is critical. The hostilities that arise over housework...are crushing the daughters of my generation....Change takes time, but mens continued obliviousness to home responsibilities is causing women everywhere to expire of trivialities.”
—Mary Kay Blakely (20th century)