Problema de atribuição por vários dias

Eu tenho um problema que pode ser reduzido a um problema de atribuição. (Em uma pergunta anterior, descobri como fazer isso.)

O que significa que temos um conjunto de agentes e um conjunto de tarefas, bem como uma função de custo c (i, j) . Precisamos encontrar uma tarefa para que o custo total seja mínimo.$A$$T$$c(i,j)$

O algoritmo húngaro pode encontrar uma solução ótima em pelo menos $O(n^4)$ . Isso me parece bom.

Meu novo problema é: Há um determinado número de dias. Eu tenho que resolver o problema de atribuição de cada dia para que cada tarefa seja executada todos os dias e nenhum agente faça a mesma tarefa duas vezes .

O que tentei: poderíamos executar o algoritmo húngaro separadamente para cada dia e limitar o número de combinações possíveis com base no resultado do dia anterior. Mas isso nos causaria problemas em alguns dias posteriores, onde provavelmente será impossível encontrar uma solução viável.

Outra idéia é de alguma forma integrar a pesquisa local para alterar as decisões tomadas no dia anterior. Mas acho que não podemos confiar nisso.

As instâncias de problemas que tenho que enfrentar estarão em algum lugar ao redor . A matriz de custos terá muitos valores iguais (por exemplo, principalmente 1 ou infinito, apenas 2 ou 3). Portanto, durante o algoritmo húngaro, há muito espaço para criar diferentes soluções ideais para um único dia.$|A| = |T| = 500$$C(i,j)$

Ficaria feliz em ouvir algumas idéias ou aconselha como encontrar uma boa solução para o problema. Desde já, obrigado.

Existe uma maneira de fazer isso no tempo polinomial. Esboçarei o algoritmo (na ordem inversa ... faça o passo 2 primeiro e o passo 1 segundo).

1. se pudermos encontrar um conjunto de pares agente-tarefa modo que cada tarefa esteja exatamente em pares, cada agente esteja exatamente em pares e nenhum par apareça mais de uma vez, podemos encontrar atribuições que juntos, cobrem esses pares agente-tarefa. Fazemos isso repetidamente usando um algoritmo de correspondência bipartida máxima para encontrar uma correspondência perfeita no gráfico bipartido correspondente e removendo essa atribuição do gráfico. O teorema do casamento de Hall garante que podemos fazer isso.$nk$$(i,j)$$k$$k$$k$$nk$

2. Podemos encontrar o conjunto de custo mínimo de pares agente-tarefa, como na etapa 1, usando o fluxo de custo mínimo. Considere uma rede com uma fonte , um coletor e nós para cada um dos agentes e cada uma das tarefas. Conecte a origem a cada agente com uma borda de capacidade custo . Conecte cada tarefa ao coletor com uma borda de capacidade custo . Agora, conecte o agente à tarefa com um limite de capacidade e custo$nk$$s$$t$$k$$0$$k$$0$$i$$j$$1$$c(i,j)$. É garantido que o fluxo de custo mínimo nessa rede seja integral (porque todas as capacidades são integrais e há um teorema dizendo que isso implica que existe um fluxo de custo mínimo ideal ideal), de modo que o fluxo em cada borda da tarefa do agente é ou . As arestas com o fluxo formam o conjunto de pares na etapa 1.$0$$1$$(i,j)$$1$

Existem muitos algoritmos que podem resolver o fluxo de custo mínimo ; é um caso especial de programação linear. Para o seu problema de tamanho, o algoritmo que eu esboço não deve ser apenas em tempo polinomial, mas também prático.