Problema de asignación para varios días.

Tengo un problema que se puede reducir a un problema de asignación. (En una pregunta anterior descubrí cómo hacerlo).

Lo que significa que tenemos un conjunto de agentes y un conjunto de tareas, así como una función de costo . Necesitamos encontrar una asignación para que el costo total sea mínimo.$A$$T$$c(i,j)$

El algoritmo húngaro puede encontrar una solución óptima en al menos . Lo que me suena bien.$O(n^4)$

Mi nuevo problema es: hay un número determinado de días. Tengo que resolver el problema de asignación para cada día para que cada tarea se realice todos los días y ningún agente realice la misma tarea dos veces .

Lo que he intentado: podríamos ejecutar el algoritmo húngaro por separado para cada día y limitar el número de combinaciones posibles en función del resultado del día anterior. Pero esto nos metería en problemas en algunos de los días posteriores, donde lo más probable es que sea imposible encontrar una solución factible.

Otra idea es integrar de alguna manera la búsqueda local para cambiar las decisiones tomadas en un día anterior. Pero creo que no podemos confiar en esto.

Las instancias problemáticas que debo enfrentar estarán en algún lugar alrededor de . La matriz de costos tendrá muchos valores iguales (por ejemplo, en su mayoría 1 o infinito, solo unos 2 o 3). Entonces, durante el algoritmo húngaro, hay mucho espacio para crear diferentes soluciones óptimas para un solo día.$|A| = |T| = 500$$C(i,j)$

Me alegraría escuchar algunas ideas o consejos sobre cómo encontrar una buena solución para el problema. Gracias por adelantado.

Hay una manera de hacer esto en tiempo polinómico. Dibujaré el algoritmo (en orden inverso ... haga el paso 2 primero y el paso 1 segundo).

1. si podemos encontrar un conjunto de pares de tareas de agente ( i , j ) de modo que cada tarea esté exactamente en k pares, cada agente esté en exactamente k pares, y ningún par aparezca más de una vez, entonces podemos encontrar k asignaciones que juntas cubren estos n k pares de agente-tarea. Hacemos esto usando repetidamente un algoritmo de coincidencia bipartita máxima para encontrar una coincidencia perfecta en el gráfico bipartito correspondiente, y eliminando esa asignación del gráfico. El teorema del matrimonio de Hall garantiza que podemos hacer esto.$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$

Hay muchos algoritmos que pueden resolver el flujo de costo mínimo ; Es un caso especial de programación lineal. Para su problema de tamaño, el algoritmo que bosquejo no solo debe ser de tiempo polinómico, sino también práctico.