algorithm - round - ¿Existe un algoritmo de programación que se optimice para los "horarios del fabricante"?

scheduler que es

Question

Usted puede estar familiarizado con el ensayo de Paul Graham, "Horario del creador, Horario del gerente" . El quid de este ensayo es que para los profesionales creativos y técnicos, las reuniones son un anatema para la productividad, ya que tienden a conducir a una "fragmentación del programa", dividiendo el tiempo libre en partes que son demasiado pequeñas para adquirir el enfoque necesario para resolver problemas difíciles.

En mi empresa hemos visto beneficios significativos al minimizar la cantidad de interrupciones causadas, pero el algoritmo de fuerza bruta que utilizamos para decidir los horarios no es lo suficientemente sofisticado para manejar bien la programación de grandes grupos de personas. (*)

Lo que estoy buscando es si hay algoritmos conocidos que minimicen esta interrupción de la productividad, entre un grupo de N fabricantes y gerentes.

En nuestro modelo,

• Hay N personas.
• Cada persona p _i es un creador ( Mk ) o un administrador ( Mg ).
• Cada persona tiene un horario s _i .
• El horario de todos es de H horas de duración.
• Un programa consiste en una serie de intervalos no superpuestos s _i = [ h ₁ , ..., h _j ].
• Un intervalo es libre u ocupado . Dos intervalos libres adyacentes son equivalentes a un único intervalo libre que abarca ambos.
• La productividad P para cada persona es un valor entre 0 y 1.
  • La productividad de un fabricante se maximiza cuando se minimiza el número de intervalos libres.
  • La productividad de un fabricante es igual a 1 / (máx. [1, el número de intervalos libres]).
  • La productividad de un gerente se maximiza cuando se maximiza la duración total del tiempo libre, pero les gustan los largos períodos de tiempo entre las reuniones más que las breves pausas.
  • La productividad de un gerente es igual a la suma de los cuadrados de las longitudes de cada intervalo libre como una proporción del día. Es decir, ( h ₁ / s _i ) ² + ( h ₂ / s _i ) ² + ..., donde cada intervalo es un intervalo libre.
• Objetivo: Maximizar la productividad total del equipo.

Tenga en cuenta que si no hay reuniones, tanto los creadores como los gerentes experimentan una productividad óptima. Si las reuniones deben programarse, entonces los fabricantes prefieren que las reuniones se realicen en forma consecutiva, mientras que a los gerentes no les importa dónde va la reunión. Tenga en cuenta que dado que todas las interrupciones se consideran igualmente perjudiciales para los creadores, no hay diferencia entre una reunión que dura 1 segundo y una reunión que dura 3 horas si segmenta el tiempo libre disponible.

El problema es decidir cómo programar M diferentes reuniones que involucran números arbitrarios de N personas, donde cada persona en una reunión determinada debe colocar un intervalo ocupado en su agenda de modo que no se superponga con ningún otro intervalo ocupado . Para cada reunión, la hora de inicio para el intervalo ocupado debe ser la misma para todas las partes.

¿Existe un algoritmo para resolver este problema o uno similar? Mi primer pensamiento fue que esto se parece mucho a la desfragmentación (minimizar el número de fragmentos distintos), y hay muchos algoritmos al respecto. Pero la desfragmentación no tiene mucho que ver con la programación. ¿Pensamientos?

(*) En la práctica, esto no es realmente un problema, porque es raro que tengamos reuniones con más de ~ 5 personas a la vez, por lo que el espacio de posibilidades es pequeño.

Answer 1

Este problema parece lo suficientemente difícil como para ser NP, pero creo que admite algunas aproximaciones decentes.

En particular, creo que probablemente pueda administrar razonablemente bien con una optimización del tamaño de la reunión , donde ubique de manera óptima la reunión más grande (en términos de la cantidad de fabricantes que deben asistir, ya que son los que está tratando de no interrumpir), y luego hacerlo sucesivamente con reuniones más pequeñas. Para romper lazos en reuniones más pequeñas de la misma duración, puede ponderar las reuniones con la carga de reuniones de los fabricantes a los que se les pide participar (para que tenga la oportunidad de optimizar sobre ellos y no empeorar sus vidas).

Ahora ha dividido el problema para programar una sola reunión, ya que cualquier reunión ya programada reducirá efectivamente el horario de una persona a más corto. Y la solución es bastante sencilla: la solución óptima es la que está alineada con un número máximo de bordes de programaciones de fabricantes para que todos puedan aprovechar ese momento. Debería poder resolver este problema incluso con fuerza bruta en algo como O((k+g)*k*n) donde k es el número de creadores, g el número de administradores y n el número típico de intervalos en una Horario del fabricante.

El único problema sería si este enfoque directo llevara a reuniones que no podrían satisfacerse. En este caso, podría aumentar la prioridad de esa reunión en uno o más espacios e intentarlo de nuevo.

Answer 2

Recuerdo que implementé algo muy similar a tu problema con el algoritmo de búsqueda A *. Encontrará fácilmente varias implementaciones del algoritmo disponible, pero para aplicarlo al problema de programación, tendrá que construir funciones de distancia y heurísticas basadas en su modelo y dividir el tiempo continuo en partes.

Answer 3

Se puede obtener una buena aproximación para esto mediante el uso de un algoritmo genético.

Escriba una función para crear 1000 horarios de muestra aleatorios asignando a los creadores y gerentes al azar.

Escriba otra función (función de aptitud física) que asigne deméritos a los horarios con problemas (personas que trabajan al mismo tiempo, no hay suficientes creadores, no hay suficientes gerentes, alguien no trabajó lo suficiente, alguien trabajó demasiado).

foreach schedule assign calculate fitness keeping a reference to the lowest scoring (best) schedule.

while (best schedule > minimum fitness value)
    foreach schedule s in population of schedules
        foreach time slot
           if (random < .5)
               choose value from best schedule
           else
               choose value from schedule s
           end if
       end foreach
       score schedule s with fitness function
    end foreach
end while

Si bien este método no producirá un cronograma óptimo y tiene la posibilidad de encontrar mínimos locales. Siempre producirá un programa y siempre puede agregar más restricciones a la función de aptitud para cualquier condición que no quiera ver. Este tipo de algoritmo puede manejar muchos tipos diferentes de problemas de satisfacción de restricciones.

Personalmente he usado un algoritmo similar para programar mi preescolar Wifes Co-Op para todo el año en aproximadamente dos horas en mi computadora portátil.

Answer 4

Trate de echar un vistazo a recocido simulado. Es similar a los algoritmos genéticos como describe Jeremy E, pero en lugar de generar aleatoriamente su conjunto de horarios de inicio, usted comienza con un programa válido pero no óptimo. La idea es generar algún "vecino" del programa original mezclando aleatoriamente algunos horarios de reuniones y luego probando la aptitud física antes de iterar.

S'' = Starting Schedule
S = S''    
while( Fitness( S ) < Minimum Fitness ) 
{
    NS = Neighbor( S )
    if( Fitness( NS ) > Fitness( F ) )
    {
         S = NS
    }
}
Return( S )

En lugar de probar contra un nivel mínimo de condición física, también puede especificar un número establecido de iteraciones para que pueda determinar de forma determinista cuándo terminará la ejecución del programa.

Lo que pasa con este algoritmo es que el resultado final tiende a parecerse al estado de inicio, por lo que si desea ponderar una reunión grande (en términos de tamaño de los fabricantes) temprano en el día, podría hacerlo.