Problem przydziału na wiele dni

Mam problem, który można sprowadzić do problemu przydziału. (W poprzednim pytaniu dowiedziałem się, jak to zrobić.)

Co oznacza, że ​​mamy zestaw $A$ agentów i zestaw zadań, a także funkcję kosztu . Musimy znaleźć zadanie, aby całkowity koszt był minimalny.c ( i , j $T$$c(i,j)$

Algorytm węgierski może znaleźć optymalne rozwiązanie, w co najmniej . Które brzmi dla mnie dobrze.$O(n^4)$

Mój nowy problem to: Dana liczba dni. Muszę rozwiązać problem przypisania na każdy dzień, aby każde zadanie było wykonywane codziennie, a żaden agent nie wykonał tego samego zadania dwa razy .

Co próbowałem: Możemy uruchomić węgierski algorytm osobno dla każdego dnia i ograniczyć liczbę możliwych kombinacji w oparciu o wynik z poprzedniego dnia. Wpadłoby to jednak w kłopoty w późniejszych dniach, w których najprawdopodobniej niemożliwe będzie znalezienie realnego rozwiązania.

Innym pomysłem jest integracja wyszukiwania lokalnego w celu zmiany decyzji podjętych poprzedniego dnia. Ale myślę, że nie możemy na tym polegać.

Przypadki, z którymi muszę się zmierzyć, będą gdzieś . Macierz kosztów będzie miała wiele takich samych wartości (np. Głównie 1 lub nieskończoność, tylko około 2 lub 3). Tak więc podczas węgierskiego algorytmu jest dużo miejsca na stworzenie różnych optymalnych rozwiązań na jeden dzień.$|A| = |T| = 500$$C(i,j)$

Z przyjemnością usłyszę kilka pomysłów lub doradzę, jak znaleźć dobre rozwiązanie problemu. Z góry dziękuję.

Jest na to sposób w czasie wielomianowym. Naszkicuję algorytm (w odwrotnej kolejności ... najpierw wykonaj krok 2, a drugi krok 1).

1. $nk$$(i,j)$$k$$k$$k$$nk$

2. $nk$$s$$t$$k$$0$$k$$0$$i$$j$$1$$c(i,j)$$0$$1$$(i,j)$$1$

Istnieje wiele algorytmów, które mogą rozwiązać minimalny przepływ ; jest to szczególny przypadek programowania liniowego. W przypadku twojego problemu algorytm, który szkicuję, powinien być nie tylko czasem wielomianowym, ale także praktyczny.