Mam rzeczywisty problem, który próbuję reprezentować i automatyzować. Uprościłem i streściłem to w następujący sposób:
- Jest n miejsc pracy (P1, P2, ..., Pn).
- W każdym miejscu Pn ma klucz Kn.
- Istnieje m Pracownicy, (W1, W2, ..., Wm).
- Aby pracować w Pn, pracownik musi trzymać Kn.
- Każdy klucz może być w posiadaniu pracownika lub pozostawiony na giełdzie E.
Pracownik może w dowolnym momencie udać się na giełdę, aby odebrać klucze, które nie zostały odebrane, lub zostawić klucze, z których mogą korzystać inni.
Teraz istnieje egzogeniczny harmonogram prac, który należy wykonać w ścisłej kolejności. Na przykład:
- 2016-04-21 W1 musi działać na P6
- 2016-04-21 W2 musi działać w P3
- ** wymagana wymiana kluczy **
- 2016-04-22 W3 musi działać w P3
- 2016-04-22 W2 musi działać na P6
Dowolna liczba pracowników może być zmuszona do pracy w Pn w pewnym momencie swojego harmonogramu, chociaż nigdy tego samego dnia
Wiemy:
- Początkowa lokalizacja wszystkich kluczy, zarówno z pracownikami, jak i w E.
- Przyszłe zlecenia pracy, które każdy pracownik będzie musiał wykonać
Tak więc staram się modelować całą tę sytuację. Czy możesz zasugerować struktury danych i algorytmy, na które powinienem patrzeć, aby się nimi zająć i zacząć optymalizować wyjazdy na giełdę dla każdego pracownika?
Chcę zminimalizować całkowitą liczbę podróży do E. Drugim celem byłoby zapewnienie, że żaden pracownik nie wykona nieproporcjonalnej liczby podróży.
Z góry dziękuję!!
źródło
Odpowiedzi:
Pytanie jest trochę dwuznaczne w jednym kluczowym punkcie: dla których elementów próbujemy rozwiązać. Czy chcemy zoptymalizować kolejność przekazywania zasobów? Minimalizujesz liczbę wyjazdów na giełdę? Maksymalizacja przepustowości zlecenia pracy?
Mając to na uwadze, zakładam, że moglibyśmy zrobić dowolną mieszankę tych rzeczy i utrzymać odpowiedź na dość wysokim poziomie.
Pierwszą rzeczą, jaka przychodzi mi do głowy, jest to, że powiązane ze sobą problemy, które próbuje rozwiązać, koncentrują się głównie na zarządzaniu zależnościami. Pracowników, klucze i lokalizacje można traktować jako zależności, które należy rozwiązać, aby wykonać zadania.
Przechodząc do następnego poziomu, przyjrzałbym się adaptacji sortowania topologicznego ( https://en.wikipedia.org/wiki/Topological_sorting ). Modeluj przestrzeń problemu jako duży wykres (nowoczesne bazy danych wykresów mogą być dobrym medium również dla niektórych z tych analiz), a następnie użyj różnych rodzajów topologicznych do rozwiązania różnych aspektów przestrzeni problemu.
Z lekką styczną brzmi to naprawdę zabawny projekt. Dziś zazdroszczę panu.
źródło