I have a problem that can be reduced to an assignment problem. (In a previous question i found out how to do that.)
Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost function $c(i,j)$. We need to find an assignment so that the total cost is minimal.
The hungarian algorithm can find an optimal solution in at least $O(n^4)$. Which sounds good to me.
My new Problem is: There is a given number of days. I have to solve the assignment problem for each day so that every task is done every day and no agent does the same task twice.
What I have tried: We could run the hungarian algorithm separately for each day and limit the number of possible combinations based on the result of the previous day. But this would get us into trouble at some of the later days, where most likely it will be impossible to find a feasibly solution.
Another idea is to somehow integrate local search to change decisions made at a previous day. But I think we can't rely on this.
The problem instances I have to face will be somewhere around $|A| = |T| = 500$. The cost matrix $C(i,j)$ will have lots of same values (E.g. mostly 1 or infinity, only some 2 or 3). So during the hungarian algorithm there is a lot of space to create different optimal solutions for a single day.
I'd be glad to hear some ideas or advises how to find a good solution for the problem. Thanks in advance.