Modelowanie złożonego harmonogramu pracy

9

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ę!!

Gareth Lloyd
źródło
2
Średnia liczba podróży do E na pracownika = „łączna liczba podróży” / m. Więc jeśli m jest stały, twoje dwa cele są takie same. Bardziej interesujące: Myślę, że każdy pracownik może nosić jednocześnie więcej niż jeden klucz?
Doc Brown
Tak, pracownicy mogą nosić dowolną liczbę kluczy. Jeśli chodzi o „średnią”, myślę, że źle się wyraziłem. Myślałem bardziej o uczciwości, aby żaden pracownik nie musiał odbywać nieproporcjonalnej liczby podróży, a więc niskiej wariancji. (zredagowane pytanie, aby dopasować)
Gareth Lloyd
Ponieważ pracownicy są oczywiście zaufani do kluczy i mogą przechowywać klucze przez noc i tak długo, jak to konieczne - dopóki wymiana nie jest wymagana - dlaczego nie stworzyć zestawu kluczy dla każdego pracownika, który przechowują na stałe? Alternatywnie, utwórz zestaw kluczy dla każdego pracownika dla wszystkich miejsc, do których się udają, na dany okres, powiedzmy, tydzień. Klucze są duplikowane w razie potrzeby, aby ustawić tydzień dla każdego pracownika. Wszyscy pracownicy wymieniają klucze raz w tygodniu.
radarbob
Czy przejście na giełdę kosztuje (pieniądze lub czas)?
Dan Pichelman 21.04.16
Tak, więcej podróży na giełdę to gorszy wynik.
Gareth Lloyd

Odpowiedzi:

1

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.

Michał
źródło
Spójrz na wykresy w moim github github.com/MatheusArleson/Graphs
linuxunil
Czy algorytm kolorowania pomaga w tej sytuacji? en.m.wikipedia.org/wiki/Graph_coloring
linuxunil