Una variante del algoritmo húngaro / problema de asignación

Question

¿Existe un algoritmo para la siguiente variante del problema de asignación?

Supongamos que tenemos $n$ trabajadores $A_i$ y $m$ tareas y cada trabajador $A_i$ tiene que hacer exactamente $t_i$ tareas. (Los números se eligen de forma que $m= \sum_{i=1}^n t_i$ .) Para cualquier $i$ dejar $C_i$ sea la suma de los costes del trabajador $A_i$ . Estoy buscando una tarea tal que $\max_i C_i$ es mínima.

He encontrado esta variante pero esto sólo se refiere al coste máximo de una tarea, no a la suma de las tareas de un trabajador.

Answer 1

Yo resolvería este problema mediante programación entera. Sea $x_{ij}$ sea una variable de decisión para el trabajador $A_i$ hacer la tarea $j$ y $c_{ij}$ sea el coste del trabajador $A_i$ hacer la tarea $j$ . Tenemos $C_i = \sum\limits_{j=1}^mc_{ij}x_{ij}$ . Tenemos que resolver la siguiente IP: $\min z$ con sujeción a $\sum\limits_{j=1}^mx_{ij} = t_i$ y $\sum\limits_{j=1}^mc_{ij}x_{ij} \leq z$ para todos $i=1,\ldots,n$ y $x_{ij}\in \{0,1\}$ .

Answer 2

Si todos los $t_i$ s son $1$ Entonces (como se dice en el post enlazado), el problema se convierte en un problema de correspondencia perfecta. Que es fácil de resolver.

Pero aquí, porque se toma una $\max$ de una suma de costes, esto se traduciría en un emparejamiento de hipergrafos (donde los hipergrafos son, para un trabajador, los grupos de tareas cuya suma es inferior al umbral), que ( en general ) es mucho más difícil. No se puede demostrar directamente que la dureza del emparejamiento de hipergrafos generales se traduce en este problema, porque no se pueden codificar los hipergrafos generales como derivados de este problema ; pero parecen malas noticias...

Si el $t_i$ no son fijas (sino que sólo insistimos en que cada tarea se asigne exactamente una vez), se trata del problema de Papá Noel (pero en lugar de dar tareas, se dan regalos), que es difícil pero tiene un algoritmo de aproximación .