Problème d'affectation pendant plusieurs jours

J'ai un problème qui peut être réduit à un problème d'affectation. (Dans une question précédente, j'ai découvert comment procéder.)

Ce qui signifie que nous avons un ensemble d'agents et un ensemble de tâches ainsi qu'une fonction de coût . Nous devons trouver une affectation afin que le coût total soit minime. $A$ $T$ $c(i,j)$

L' algorithme hongrois peut trouver une solution optimale dans au moins . Ce qui me semble bien. $O(n^4)$

Mon nouveau problème est: il y a un nombre de jours donné. Je dois résoudre le problème d'affectation pour chaque jour afin que chaque tâche soit effectuée tous les jours et qu'aucun agent n'effectue la même tâche deux fois .

Ce que j'ai essayé: nous pourrions exécuter l'algorithme hongrois séparément pour chaque jour et limiter le nombre de combinaisons possibles en fonction du résultat de la journée précédente. Mais cela nous poserait des problèmes certains des derniers jours, où il sera très probablement impossible de trouver une solution viable.

Une autre idée est d'intégrer en quelque sorte la recherche locale pour changer les décisions prises la veille. Mais je pense que nous ne pouvons pas compter sur cela.

Les cas de problème auxquels je devrai faire face se situeront quelque part . La matrice de coût aura beaucoup de mêmes valeurs (par exemple, principalement 1 ou infini, seulement 2 ou 3). Ainsi, pendant l'algorithme hongrois, il y a beaucoup d'espace pour créer différentes solutions optimales pour une seule journée. $|A| = |T| = 500$ $C(i,j)$

Je serais heureux d'entendre des idées ou des conseils sur la façon de trouver une bonne solution au problème. Merci d'avance.

algorithms graph-theory assignment-problem Patrick Schmidt
la source

C'est une excellente question! Je suggérerais d'utiliser un flux à coût min, le théorème de mariage de Hall et une correspondance bipartite maximale.

Peter Shor

Réponses:

Il y a un moyen d'y parvenir en temps polynomial. Je vais esquisser l'algorithme (dans l'ordre inverse ... faites l'étape 2 en premier et l'étape 1 en deuxième).

si nous pouvons trouver un ensemble de paires agent-tâche telles que chaque tâche est dans exactement paires, chaque agent est dans exactement paires, et aucune paire n'apparaît plus d'une fois, alors nous pouvons trouver affectations qui couvrent ensemble ces paires agent-tâche. Nous le faisons en utilisant à plusieurs reprises un algorithme de correspondance bipartite maximale pour trouver une correspondance parfaite dans le graphique bipartite correspondant, et en supprimant cette affectation du graphique. Le théorème du mariage de Hall garantit que nous pouvons le faire. $nk$ $(i,j)$ $k$ $k$ $k$ $nk$
$nk$ $s$ $t$ $k$ $0$ $k$ $0$ $i$ $j$ $1$ $c(i,j)$ $0$ $1$ $(i,j)$ $1$

Il existe de nombreux algorithmes qui peuvent résoudre le flux à moindre coût ; c'est un cas particulier de programmation linéaire. Pour votre problème de taille, l'algorithme que je dessine ne doit pas seulement être polynomial, mais aussi pratique.

Peter Shor
la source

Une dernière question: l'algorithme de flux min-cost à l'étape 2 (j'ai choisi l'annulation de cycle pour commencer) fournit une solution optimale. L'algorithme de correspondance maximale de l'étape 1 fait cela pour. Cela signifie-t-il nécessairement que toute la solution est optimale? Parce que, je suppose que le problème est NP-Complete.

Patrick Schmidt

Toute la solution est optimale. Ce serait une bonne question à attribuer dans un cours d'optimisation combinatoire, car il est quelque peu surprenant que vous puissiez le faire.

Peter Shor