Safe Sex Makespan - Details

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.