[grajlord]

W ramach #naukaprogramowania piszę skrypt do optymalizacji grafiku pracy.
Problem jest trywialny - N pracowników do rozdysponowania po K na każdy z M dni.
Chciałbym jednak, żeby skrypt w procesie decyzjnym brał pod uwagę dodatkowe parametry, np: preferencje pracowników (dni preferowane/niemożliwe do obsadzenia przez konkretną osobę), maksymalna liczba dni na pracownika, dotychczasowa historia pracy(weekendy, etc) - czyli generalnie model, który przy optymalizacji nadaje wagi pracownikom i dniom.
Najprostsze rozwiązanie: szukam dni niemożliwych do obsadzenia, jeżeli są - wymuszam (losowo) na którymś z pracowników wzięcie tego dnia. Następnie w iteracjach losuję pracowników na każdy dzień. Biorąc pod uwagę wagi obliczam "karę" za nieoptymalne obsadzenie (nieuwzględnienie preferencji pracowników, nierówny podział pracy) i po ostatniej iteracji wybieram najlepszy model minimalizujący karę.
Czy są jakieś "standardowe" schematy rozwiązywania takich problemów? Jak byście do tego podeszli?
Jak zminimalizować potrzebę losowania i liczbę iteracji w tym procesie?
Korzystam z R i Pythona.

#programowanie #matematyka #statystyka #machinelearning #datascience

[tyrytyty]

taktyk

[koostosh]

Problem jest trywialny

@grajlord: nie

[cxnmlhuipwetr]

@grajlord: Możesz wykorzystać ILP - przykładowo zmienna 0 <= P_i_k <= 1 oznacza że pracownik i został przypisany do k-tego dnia. Jeśli wiesz że j-tego dnia i-ty pracownik nie może pracować, to dodajesz nierówność 0 <= P_i_j <= 0. Jeśli wiesz że pracownik nie może pracować mniej niż jeden i więcej niż 3 dni w danym okresie, to 1 <= (suma po j P_i_j) <= 3. Wrzucasz to w solwer

[grajlord]

@cxnmlhuipwetr: o, dzięki za wskazanie metod. z tego wynika, że ILP, combinatorial optimization, assignment problem - nie wiem jak to jest po polsku, to są chyba te zagadnienia, których szukam?

[cxnmlhuipwetr]

@grajlord: Tak. Po polsku to się zwie programowanie liniowe całkowitoliczbowe (aczkolwiek "programowanie" ma tutaj aspekt matematyczny, niezwiązany z procesem programowania).