手袋の問題

オペレーションズリサーチでは、グローブ問題^{[ 1 ]}（コンドーム問題^{[ 2 ]}としても知られる）は、最も安い資本コストがしばしば運用時間の劇的な増加につながるが、最も高い資本コストが最短の運用時間をもたらすとは限らないことを示す例として使用される最適化問題である^{[ 3 ] 。}

M人の医師がそれぞれN人の患者を診察する。医師は汚染を防ぐため手袋を着用する。手袋は何度でも使用できるが、同じ面を複数の人が使用してはならない。手袋は何度でも再利用でき、複数個を同時に使用することもできる。

M人の医師とN人の患者が与えられたとき、すべての医師がすべての患者を診察するために必要な手袋の最小数G ( M , N )は次のように表されます。 

• G ( M ,  1) = M
• G (1, N ) = N 
• G ( M  +  1, N + 1) = M + N   

単純なアプローチとしては、手袋の数をG ( M , N ) = MNと見積もる方法がある。しかし、手袋には両面があり、両面を同時に使用する必要がないという事実を利用すれば、この数を大幅に減らすことができる。  

より良い解決策は、各人に専用の手袋を割り当て、それを手術全体を通して使用することです。こうすることで、すべてのペアの接触が二重層で保護されます。医師の手袋の外側表面は患者の手袋の内側表面のみに接触することに注意してください。これにより、M  + N 個の手袋という答えが得られ、これはMNよりも大幅に少なくなります。  

この方式における完了時間はK ·  max  ( M , N ) であり、Kはペアワイズ遭遇の所要時間です。これは、MN 個の手袋を使用した場合とまったく同じ完了時間であることに注意してください。明らかに、この場合、設備投資の増加は作業時間の短縮にはつながっていません。 

手袋の初期分布に非対称性を考慮することで、数G ( M , N ) をさらに改良することができる。最適なスキームは次のとおりである。 

• 医師1はN個の手袋を重ねて着用している。彼はN人の患者を順番に診察し、それぞれの患者に一番外側の手袋を置き忘れていく。
• 医師2～（M - 1）はそれぞれ片方の手袋を着用し、上記のように各接触時に二重構造のプロトコルに従います。  
• 医師Mは自分の手袋は着用していませんが、N人の患者全員を診察し、順番に手袋を集めて、徐々に多層構造の手袋に作り変えていきます。最初の診察では、患者 1の手袋の内側の未使用部分のみを使用しているため、まだ安全です。

この方式では、(1  · N ) + (( M − 1 − 1) · 1) + (1 · 0) = M + N − 2 個の手袋を使用します。この数はこれ以上減らすことはできません。                

メイクスパンは次のように表されます。

• 手袋を植え付けるためのN回の連続的な相互作用。
• 中間段階では、max( M − 2, N ) 回の並列化相互作用を行う。   
• 手袋を回収するために、N回の連続的な操作が必要です。

完了時間: K  ·  (2 N  +  max( M − 2, N ))。   

明らかに、最小のG ( M , N ) はメイクスパンを大幅に増加させ、場合によっては 3 倍にもなります。手袋の数によるメリットはわずか 2 単位であることに注意してください。

手袋のコストと作業時間の長さを比較した場合、どちらかの解決策が好ましい場合がある。理論的には、（M  + N - 1）の中間的な解決策も候補となるはずだが、 M、N 、およびコストパラメータが最適となるためには、非常に狭い範囲の値が必要となるため、しばしば無視される。    

問題文では、伝染の原理が適用されることが明確に示されていません。つまり、ある手袋の内側が、以前に誰かに触れた別の手袋の外側に触れた場合、その内側もその人に触れたとみなされるということです。

また、医療用手袋はリバーシブルなので、より良い解決策として、

${\displaystyle \min \left(\lceil M/2\rceil +N,M+\lceil N/2\rceil \right)}$

手袋は、人数が少ないグループには1つずつ、人数が多いグループには2つずつ支給される。各ペアの最初の手袋は清潔なインターフェースを使用し、2番目の手袋は裏返して使用する。