Algoritmo ponderado de programación de recursos de equilibrio de carga

Question

Una aplicación de software en la que estoy trabajando debe poder asignar tareas a un grupo de usuarios en función de cuántas tareas tienen actualmente, donde los usuarios con la menor cantidad de tareas tienen más probabilidades de obtener la siguiente tarea. Sin embargo, la carga de la tarea actual debe tratarse como una ponderación, en lugar de una definición de orden absoluta. IOW, necesito implementar un algoritmo ponderado de equilibrio de carga.

Digamos que hay cinco usuarios, con el siguiente número de tareas:

A: 4 B: 5 C: 0 D: 7 E: 9

Quiero priorizar a los usuarios para la siguiente tarea en el orden CABDE, donde C tiene más probabilidades de obtener la asignación y E, la menos probable. Hay dos cosas importantes a tener en cuenta aquí:

• El número de usuarios puede variar de 2 a docenas.
• El número de tareas asignadas a cada usuario puede variar de 1 a cientos.

Por ahora, podemos tratar todas las tareas como iguales, aunque no me importaría incluir la tarea difícil como una variable que pueda usar en el futuro, pero esto es pura guinda del pastel.

Las ideas que se me han ocurrido hasta ahora no son muy buenas en algunas situaciones. Podrían ponderar a los usuarios demasiado juntos si hay una gran cantidad de usuarios, o podrían fallar si un usuario no tiene tareas actuales, o ...

He intentado hurgar en la web, pero no he tenido mucha suerte. ¿Alguien puede darme un resumen rápido de un algoritmo que funcione bien? No necesito una implementación real, haré esa parte, solo una buena descripción. Alternativa, ¿hay un buen sitio web que sea de libre acceso?

Además, aunque ciertamente aprecio la calidad, esto no necesita ser estadísticamente perfecto. Entonces, si puedes pensar en una técnica buena pero no excelente, ¡estoy interesado!

Answer 1

Como usted señala, este es un problema de equilibrio de carga. No es realmente un problema de programación, ya que no está tratando de minimizar nada (tiempo total, número de trabajadores concurrentes, etc.). No hay restricciones especiales (duración del trabajo, enfrentamientos de tiempo, conjuntos de habilidades para igualar, etc.) Así que realmente su problema se reduce a seleccionar una función de ponderación adecuada.

Usted dice que hay algunas situaciones que desea evitar, como las ponderaciones de los usuarios que están demasiado juntas. puedes darme mas detalles? Por ejemplo, ¿qué tiene de malo hacer que la posibilidad de asignación sea proporcional a la carga de trabajo actual, normalizada por la carga de trabajo de los otros trabajadores? Puede visualizar esto como una secuencia de bloques de diferentes longitudes (las tareas), que se empaquetan en un conjunto de contenedores (los trabajadores), donde intenta mantener la altura total de los contenedores lo más uniforme posible.

Con más información, podríamos hacer recomendaciones específicas de funciones que podrían funcionar para usted.

Editar: ejemplo de funciones de equilibrio de carga

En función de sus comentarios, aquí hay algunos ejemplos de funciones simples que pueden proporcionarle un comportamiento de equilibrio diferente. Una pregunta básica es si desea un comportamiento determinista o probabilístico. Daré un par de ejemplos de cada uno.

Para usar el ejemplo en la pregunta, hay 4 + 5 + 0 + 7 + 9 = 25 trabajos actualmente asignados. Desea elegir quién obtiene el trabajo 26.

1) Granja de tareas simple. Para cada trabajo, elija siempre al trabajador con menos trabajos actualmente pendientes. Los trabajadores rápidos tienen más que hacer, pero todos terminan aproximadamente al mismo tiempo.

2) Garantice una carga de trabajo justa. Si los trabajadores trabajan a diferentes velocidades y no quiere que algunos hagan más que otros, entonces rastree el número de trabajos completados + pendientes para cada trabajador. Asigne el próximo trabajo para mantener este número uniformemente distribuido (los trabajadores rápidos obtienen descansos gratis).

3) Normalización lineal básica. Elija un número máximo de trabajos que cada trabajador puede tener. La carga de trabajo de cada trabajador se normaliza a ese número. Por ejemplo, si el número máximo de trabajos / trabajador es 15, se pueden agregar 50 trabajos más antes de alcanzar la capacidad. Entonces, para cada trabajador, la probabilidad de que se le asigne el siguiente trabajo es

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

Si no desea utilizar un umbral máximo específico, puede utilizar el trabajador con el mayor número actual de trabajos pendientes como límite. En este caso, ese es el trabajador E, por lo que las probabilidades serían

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

Tenga en cuenta que en este caso, la normalización asegura que al trabajador E no se le puede asignar ningún trabajo, ya está en el límite. Además, el hecho de que C no tenga nada que hacer no significa que se le garantice que se le dará un nuevo trabajo (es más probable).

Puede implementar fácilmente la función de elección generando un número aleatorio r entre 0 y 1 y comparándolo con estos límites. Entonces, si r es & Lt; 0.25, A obtiene el trabajo, 0.25 & Lt; r < 0.45, B obtiene el trabajo, etc.

4) Normalización no lineal. Usar una función de registro (en lugar de la resta lineal) para ponderar sus números es una manera fácil de obtener una normalización no lineal. Puede usar esto para sesgar las probabilidades, p. para que sea mucho más probable que los trabajadores sin muchos trabajos reciban más.

El punto es que la cantidad de formas de hacerlo es prácticamente ilimitada. La función de ponderación que use dependerá del comportamiento específico que esté intentando habilitar. Esperemos que te haya dado algunas ideas que puedas usar como punto de partida.