Mam do czynienia z problemem, nie jestem pewien, jak podejść. Muszę wygenerować kalendarz dla pracowników, z których każdy ma określone ograniczenia pracy (niektóre osobiste, niektóre wspólne)
Z czym pracuję:
- Mam lekarzy
- Każdy lekarz musi pracować 5 dni w tygodniu.
- Każdy lekarz musi pracować 1 noc / tydzień
- Każdy lekarz musi przepracować taką samą liczbę nocy w porównaniu z innymi lekarzami (lub jak najbliżej)
- Każdy lekarz musi przepracować tyle samo nocy czwartkowych i niedzielnych w porównaniu z innymi lekarzami (lub jak najbliżej)
- Niektórzy lekarze nie mogą pracować w określone dni / noce (dane wprowadzone przez użytkownika)
- Niektórzy lekarze chcieliby pracować w określone dni / noce (wkład użytkownika)
- Niektórzy lekarze chcieliby nie pracować w określone dni / noce (dane wprowadzone przez użytkownika)
Użytkownik, o którym mowa, to osoba zajmująca się kalendarzem. Próbuję zbudować rozwiązanie, które automatycznie wygeneruje kalendarz spełniający wszystkie ograniczenia. Rozwiązaniem jest wprowadzenie dużych ustawień „dodaj lekarzy” i „dodaj ograniczenia” dla każdego lekarza, a następnie przycisk „generuj kalendarz”. To jest naprawdę podstawowe dla użytkownika.
Mój problem :
Nie jestem pewien, jak wygenerować faktyczne planowanie, czytałem o sieciach neuronowych, algorytmach genetycznych i tak dalej, i wszystkie one wydają się być właściwym rozwiązaniem, ale też nie do końca.
Kiedy patrzę na GA, są w stanie znaleźć rozwiązanie dla danej populacji (mój problem), ale populacja początkowa musi już przestrzegać określonego zestawu ograniczeń, które następnie zostałyby zoptymalizowane. W takim przypadku moja początkowa populacja jest już rozwiązaniem. Nie potrzebuję go „optymalizować”. Nie ma znaczenia, że jedna osoba pracuje 3 poniedziałkowe noce z rzędu, o ile faktycznie jest to poprawne, a inni pracują tak samo, co oznacza, że inni też będą pracować 3 poniedziałkowe noce z rzędu i jest w porządku. Co sprawia, że uważam, że GA są dla mnie zbyt „zaawansowane”, ponieważ mój problem został już rozwiązany w punkcie początkowym GA.
Ale z drugiej strony GA naprawdę wygląda na to, że zostały stworzone do tego, więc może nie rozumiem tego poprawnie?
W każdym razie, ponieważ nigdy nie korzystałem z GA (ani sieci neuronowych, ani niczego w tym rodzaju), chciałbym mieć pewność, że wybieram właściwe podejście przed zaangażowaniem się w taką krzywą uczenia się.
Moje pytanie :
Jak myślisz, co jest dobrym podejściem / algorytmem / techniką dla problemu takiego jak mój? Gaz? Sieci neuronowe? Coś zupełnie innego?
Mam wszystkie uszy i w razie potrzeby jestem otwarty na więcej szczegółów, ale myślę, że wyraziłem się jasno :)
Odpowiedzi:
Algorytmy genetyczne i sieci neuronowe nie są tu odpowiednie. Są one meta-heurystykami dla znalezienia wystarczająco dobrego, przybliżonego rozwiązania problemu. W szczególności oba wymagają znalezienia funkcji kosztu, aby ocenić rozwiązania kandydujące. Gdy masz już taką funkcję kosztu, może być łatwiej ręcznie opracować algorytm optymalizujący ten koszt.
To ważna myśl: biorąc pod uwagę dwa harmonogramy, potrzebujemy sposobu, aby zdecydować, czy harmonogram A lub harmonogram B jest „lepszy”. Wymieniłeś różne kryteria, ale nie jest jasne, jak się odnoszą. Czy niespełnienie jednego kryterium zawodzi całe rozwiązanie? Czy też częściowe niedotrzymanie ograniczenia sprawia, że jest to gorsze rozwiązanie niż inne?
Na najbardziej podstawowym poziomie możesz po prostu podzielić tydzień na odrębne przedziały czasowe i brutalnie wymusić wszystkie kombinacje slot-lekarz. Można jednak użyć trudnych ograniczeń, aby zmniejszyć tę przestrzeń wyszukiwania do łatwiejszego do zarządzania rozmiaru. Wydaje się, że ograniczenia czasu pracy i nocnych zmian są odpowiednie dla takiego ograniczenia przestrzeni poszukiwań. Pozostają ci setki kandydujących rozwiązań.
Aby wybrać najlepsze rozwiązanie dla kandydata, musisz je uszeregować. Jest to dość łatwe, jeśli jedno ograniczenie miękkie ma wyraźny pierwszeństwo przed wszystkimi innymi ograniczeniami miękkimi, np. Jeśli lekarz nie może przepracować określonej zmiany, jest to ważniejsze niż lekarz, który nie chce pracować na tej zmianie. Ale nie mogę zdecydować o tych regułach dla ciebie - to decyzja kierownicza. Trudniej jest, jeśli dwa miękkie ograniczenia nie mają wyraźnego pierwszeństwa, w takim przypadku będziesz musiał wymyślić jakąś funkcję kosztu, która ujednolica znaczenie dwóch ograniczeń w jednym pomiarze.
Prawdopodobnie skonstruowałbym chciwy algorytm, który wypełnia pusty harmonogram zgodnie z niektórymi priorytetowymi kryteriami. To może nie być najbardziej optymalne rozwiązanie, ale jest o wiele łatwiejsze niż filozofowanie na temat tego, co tak naprawdę oznacza „optymalne”.
Pierwszym krokiem było wypełnienie nocnych zmian w weekendy i próba wybrania lekarzy, którzy nie robili nocnej zmiany przez dłuższy czas, biorąc również pod uwagę życzenia użytkowników „nie mogę tam pracować” . Zakładając, że te życzenia są tygodniowe, a nie ciągłe, oznacza to, że lekarz, który nie może pracować w weekendowe noce przez tydzień, zostanie wybrany w przyszłym tygodniu.
Podobną procedurę można zastosować w pozostałe noce: po próbie uszanowania życzeń użytkownika wypełniasz lekarzy zgodnie z tym, kto nie robił nocnych zmian od dłuższego czasu. Procedura powtarza się podobnie dla trzeciego rodzaju przedziału czasowego, dzień się zmienia. Jeśli nie można pogodzić dwóch życzeń użytkownika, możesz śledzić, jak często życzenie użytkownika zostało spełnione, a następnie nadać priorytet lekarzowi z mniejszą liczbą spełnionych życzeń.
Niestety widzę kilka sposobów grania w ten system: np. Jeśli lekarz zostałby wybrany do pracy w weekendową nocną zmianę, ale zgłasza żądanie „nie mogę tam pracować”, ich wybór byłby opóźniony o tydzień - zmniejszając ich częstotliwość nocnych zmian weekendowych kosztem ich kolegów. Jeśli wdrożona zostanie procedura rozstrzygania życzeń, która sprawdza liczbę odrzuconych żądań, użytkownik może wprowadzić kilka niemożliwych żądań, aby zwiększyć jedno żądanie, które chce zrealizować. Jednak przy założeniu dobrej wiary (i elastyczności lekarzy w zakresie zamiany zmian), taki algorytm powinien dać wystarczająco dobre rozwiązanie.
źródło
Możesz użyć symulowanego wyżarzania .
Zrobiłem coś takiego, zanim dostałem swoją pierwszą pracę - patrz https://vimeo.com/20610875 (demo od 2:50, algorytm wyjaśniony od 6:15).
Symulowane wyżarzanie jest rodzajem algorytmu genetycznego i być może nie było odpowiednie w teorii (jak utrzymuje @amon w swojej odpowiedzi ), ale działało bardzo dobrze w praktyce i dotyczyło tego samego przypadku użycia.
Kod źródłowy jest dostępny (C #), ale chociaż działa, obawiam się, że jest okropny, to było kilka lat temu i będąc samoukiem, nie wiedziałem nic o konserwacji. Dało to jednak bardzo dobre wyniki.
Jak to w skrócie działa:
Wygeneruj 1 możliwy (może nie być bardzo dobry, ale fizycznie możliwy) harmonogram jako punkt wyjścia. Algorytm genetyczny nie jest w tym momencie potrzebny - możesz po prostu brutalnie wywalczyć sobie drogę do pierwszego znalezionego rozwiązania. Użyłem cofania . Złożoność obliczeniową można przezwyciężyć, rozwiązując zadania oddzielnie dla każdego dnia. Jeśli nie ma żadnego rozwiązania (w zależności od przypadku), w tym momencie go wykrywasz.
Zrób pulę rozwiązań - na przykład 100 kopii tego podstawowego rozwiązania.
Zmutuj każde rozwiązanie losowo: poproś lekarzy, aby zamienili się między sobą zmianami, zdejmij przypadkowego lekarza ze zmiany i umieść na nim losową dostępną osobę itp.
Oceń każde rozwiązanie za pomocą funkcji fitness, która określa, jak jest dobra. Jeden facet pracuje więcej nocy niż inny? Odejmij punkty karne. Ktoś chciał zrobić w poniedziałek, ale nie robi? Ponownie odejmij punkty karne.
Weźmy - powiedzmy - 20 najlepszych rozwiązań i skopiuj każde z nich 5 razy, nadpisując pozostałe 80, przenosząc je do następnej generacji. Ewolucja drogą doboru naturalnego.
Opłucz i powtórz.
Liczby są oczywiście arbitralne, być może trzeba będzie manipulować parametrami, aby znaleźć optymalne ustawienia dla swojego scenariusza.
Jeśli chodzi o mutowanie rozwiązania, symulowane wyżarzanie wprowadza coś, co nazywa się temperaturą. Zasadniczo oznacza to, że na początku powinieneś mutować swoje rozwiązania dość mocno (powiedzmy, zawsze wykonuj 10 prób zamiany zmian za jednym razem) i stopniowo stawaj się mniej agresywny z kolejnymi iteracjami, aby stały się bardziej dostrajające (powiedzmy w dół) tylko 2 próby poprawek na generację).
źródło
Obowiązują tutaj algorytmy genetyczne . Podczas mojego programu licencjackiego jeden z moich kolegów napisał artykuł na temat bardzo podobnego twojego problemu.
Możesz poszukać Job Shop Scheduling, a także Open Shop Scheduling lub Flow Shop Scheduling mogą być interesującymi punktami wyjścia
Aby użyć algorytmu genetycznego, nie potrzebujesz idealnego rozwiązania, możesz zacząć od N losowych kandydatów i zastosować funkcję fitness dla każdego z nich, na przykład:
Generując N kandydatów wybrałbyś X najlepszych z nich , to oni narzucaliby ograniczenia w mniejszym stopniu. Pracując z nimi, krzyżując i mutując przez kilka pokoleń, można uzyskać dobre rozwiązanie.
Mówiąc o tym wszystkim, za każdym razem, gdy używałem algorytmu genetycznego, który polegał bardziej na mutacji niż na skrzyżowaniu, mogłem opracować symulowane wyżarzanie, które działałoby znacznie lepiej, z łatwiejszą implementacją. Koszt / sprawność i funkcja mutacji dla algorytmu genetycznego będą prawdopodobnie bardzo podobne do zastosowanego w symulowanym wyżarzaniu. Zacznę od tego, spójrz na odpowiedź @Konrad Morawski
Wyszukiwarka Google znajduje dobre wyniki dla Job Shop i GA
źródło