Problem z rękawiczkami - Glove problem
W badaniach operacyjnych The Problem rękawiczka (znany również jako problemu prezerwatyw ) jest problem optymalizacji używany jako przykład, że najtańszy koszt kapitału często prowadzi do dramatycznego wzrostu czasu pracy, ale to najkrótsza potrzeba czasu działania nie mogą być podane przez najbardziej kosztowny kapitał.
Opis problemu
Każdy z lekarzy M ma za zadanie zbadać każdego z pacjentów N , zakładając rękawiczki, aby uniknąć zakażenia. Każdej rękawicy można użyć dowolną liczbę razy, ale ta sama strona jednej rękawicy nie może być wystawiona na kontakt z więcej niż jedną osobą. Rękawiczki można używać wielokrotnie, a jednocześnie można używać więcej niż jednej.
Biorąc pod uwagę lekarzy M i pacjentów N , minimalna liczba rękawic G ( M , N ) wymaganych od wszystkich lekarzy do zbadania wszystkich pacjentów jest określona przez:
- G ( M , N ) = M + N - 2, jeśli oba M , N ≥ 2
- G ( M , 1) = M
- G (1, N ) = N
- G (1, 1) = 1
Detale
Naiwnym podejściem byłoby oszacowanie liczby rękawic jako po prostu G ( M , N ) = MN . Ale tę liczbę można znacznie zmniejszyć, wykorzystując fakt, że każda rękawica ma dwie strony i nie jest konieczne używanie obu stron jednocześnie.
Lepszym rozwiązaniem jest przypisanie każdej osobie własnej rękawicy, która ma być używana podczas całej operacji. Każde spotkanie w parach jest następnie chronione podwójną warstwą. Należy zwrócić uwagę, że zewnętrzna powierzchnia rękawiczek lekarza styka się tylko z wewnętrzną powierzchnią rękawic pacjenta. Daje to odpowiedź rękawic M + N , która jest znacznie niższa niż MN .
Czas trwania w tym schemacie to K · max ( M , N ), gdzie K jest czasem trwania jednego spotkania parami. Zwróć uwagę, że jest to dokładnie taka sama długość jak w przypadku użycia rękawic MN. Oczywiście w tym przypadku wzrost kosztów kapitałowych nie spowodował skrócenia czasu działania.
Liczbę G ( M , N ) można dodatkowo udoskonalić, dopuszczając asymetrię w początkowym rozłożeniu rękawic. Najlepszy schemat daje:
- Doktor nr 1 nosi rękawiczki N , ułożone jedna na drugiej. Po kolei odwiedza pacjentów N , pozostawiając z każdym zewnętrzną rękawiczkę.
- Lekarze od 2 do ( M - 1) noszą po jednej rękawiczce i postępują zgodnie z dwuwarstwowym protokołem przy każdej interakcji, jak opisano powyżej.
- Doktor nr M nie nosi własnego, ale odwiedza wszystkich pacjentów z grupy N , po kolei zbierając ich rękawiczki i stopniowo zmieniając je w rękawiczki wielowarstwowe. Zwróć uwagę, że podczas swojego pierwszego spotkania używa tylko nietkniętej wewnętrznej strony rękawicy Pacjenta # 1, więc nadal jest bezpieczna.
Ten schemat wykorzystuje rękawice (1 · N ) + (( M - 1 - 1) · 1) + (1 · 0) = M + N - 2. Tej liczby nie można dalej zmniejszać.
Czas trwania jest wtedy określony przez:
- N seryjne interakcje w celu założenia rękawic.
- max ( M - 2, N ) równoległe interakcje dla etapu pośredniego.
- N szeregowe interakcje w celu zebrania rękawic.
Makespan: K · (2 N + max ( M - 2, N )).
Najwyraźniej minimalne G ( M , N ) znacznie zwiększa czas produkcji, czasami o współczynnik 3. Należy zauważyć, że korzyść wynikająca z liczby rękawic wynosi tylko 2 jednostki.
Jedno lub drugie rozwiązanie może być preferowane w zależności od względnego kosztu rękawicy, ocenianego na podstawie dłuższego czasu działania. Teoretycznie rozwiązanie pośrednie z ( M + N - 1) również powinno występować jako rozwiązanie kandydujące, ale wymaga to tak wąskich okien na M , N i optymalnych parametrów kosztowych, że często jest ignorowane.
Inne czynniki
Ze sformułowania problemu nie wynika jasno, że obowiązuje zasada zarażenia, tj. Jeśli wnętrze jednej rękawicy zostało dotknięte przez zewnętrzną stronę, która wcześniej dotykała jakiejś osoby, to wnętrze również liczy się jako dotknięte przez tę osobę.
Ponadto, rękawice medyczne są odwracalne; dlatego istnieje lepsze rozwiązanie, które wykorzystuje
rękawice, gdzie mniej liczna grupa jest wyposażona w rękawiczki, tym liczniejsza jest w parach. Pierwsza z każdej pary używa czystego interfejsu, druga odwraca rękawicę.