21 votos

Hay un algoritmo de programación que se optimiza para el "creador del programa"?

Usted puede estar familiarizado con el ensayo de Paul Graham, el"Creador de Calendario, Administrador de la Programación". El quid de la composición es que para los creativos y profesionales técnicos, reuniones son un anatema para la productividad, ya que tienden a conducir a la "planificación de la fragmentación", rompiendo el tiempo libre en trozos que son demasiado pequeños para adquirir la concentración necesaria para resolver problemas difíciles.

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

Lo que estoy buscando es si hay algún conocido algoritmos que minimicen este productividad de la interrupción, entre un grupo de N de decisiones y gerentes.

En nuestro modelo,

  • Hay N personas.
  • Cada persona pi es un fabricante (Mk) o un administrador (Mg).
  • Cada persona tiene un horario sque yo.
  • Todo el mundo tiene un horario H horas de duración.
  • Una programación se compone de una serie de intervalos no se solapan si = [h1, ..., h,j].
  • Un intervalo es libre o ocupado. Dos adyacentes intervalos libres son equivalentes a un único intervalo libre que abarca.
  • La productividad de P para cada persona es un valor entre 0 y 1.
    • Un fabricante de la productividad se maximiza cuando el número de intervalos es minimizado.
    • Un fabricante de la productividad es igual a 1 / (max[1, el número de intervalos libres de]).
    • Un gerente de la productividad se maximiza cuando la longitud total de tiempo libre se maximiza, pero les gusta largos tramos entre las reuniones de más de escapadas cortas.
    • Un gerente de la productividad es igual a la suma de los cuadrados de las longitudes de cada intervalo libre como una proporción de la jornada. Es decir, (h1/si)2 + (h2/si)2 + ... , donde cada intervalo es de un intervalo libre.
  • Objetivo: Maximizar el equipo de la productividad total.

Aviso de que si no hay reuniones, tanto de los creadores y los gestores de la experiencia óptima productividad. Si las reuniones deben ser programados, fabricantes prefieren que se realizan reuniones de back-to-back, mientras que los gerentes no importa de donde la reunión va. Tenga en cuenta que debido a que todas las interrupciones son tratados como igualmente perjudiciales a los responsables, no hay ninguna diferencia entre una reunión que dura 1 segundo y en una reunión que dura 3 horas si los segmentos de la disposición de tiempo libre.

El problema es decidir cómo programar M diferentes reuniones en las que participan arbitraria de números de N personas, donde cada persona en una determinada reunión tiene lugar una concurrida intervalo en su programa, que no se solapa con ninguna otra ocupado intervalo. Para cada reunión, Mt el tiempo de inicio de los ocupados intervalo debe ser el mismo para todas las partes.

Hace un algoritmo que existen para resolver este problema o uno similar? Mi primer pensamiento fue que esto se ve muy similar a la desfragmentación (minimizar el número de los distintos fragmentos), y hay una gran cantidad de algoritmos acerca de eso. Pero la desfragmentación no tiene mucho que ver con la programación. Los pensamientos?


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

11voto

Jeremy E Puntos 1523

Una buena aproximación para esto puede ser tenido por el uso de un algoritmo Genético.

Escribir una función para crear 1000 muestras aleatorias de los horarios de la asignación de responsables y gestores de forma aleatoria.

Escribe una función (función de aptitud) que asigna los deméritos de los horarios de trabajo con problemas (las personas que trabajan al mismo tiempo, no es suficiente políticos, no es suficiente gerentes, alguien que no trabajó lo suficiente, alguien trabajado 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

Mientras que este método no producirá una programación óptima y tiene la posibilidad de encontrar mínimos locales. Siempre producirá un horario y siempre se puede añadir más restricciones a la función de aptitud para cualquier condición que no quiere ver. Este tipo de algoritmo puede manejar muchos tipos diferentes de restricción satisifaction problemas.

Yo personalmente he utilizado un algoritmo similar para programar mi Mujer Co-Op preescolar durante todo el año en alrededor de dos horas en mi portátil.

1voto

Rex Kerr Puntos 94401

Este problema se ve suficientemente duro para ser NP, pero creo que admite algo decente aproximaciones.

En particular, creo que usted probablemente puede administrar razonablemente bien con una reunión de optimización de tamaño, donde de manera óptima el lugar de reunión más grande (en términos de número de decisiones que deben asistir, ya que son los que usted está tratando de no interrumpir) y, a continuación, hacer así sucesivamente con reuniones más pequeñas. Para romper lazos en reuniones más pequeñas de la misma longitud, se puede ponderar las reuniones por la reunión de carga de los fabricantes invitado a participar (de modo que usted tendrá una oportunidad para optimizar sobre ellos, y no a hacer su vida mucho peor).

Ahora que hemos roto el problema hacia abajo para programar una sola reunión, desde ya-reunión programada efectivamente se trata sólo de reducir a una persona, para más corta. Y la solución es bastante sencilla: la solución óptima es la alineado con un número máximo de aristas de los horarios de los fabricantes de que todo el mundo puede hacer que el tiempo. Usted debe ser capaz de resolver este problema, incluso con la fuerza bruta en algo como O((k+g)*k*n) donde k es el número de fabricantes, g el número de gerentes, y n el número típico de intervalos en un fabricante de horario.

El único problema sería si este sencillo planteamiento llevaría a reuniones que no podía ser satisfecha. En este caso, se podría aumentar la prioridad de la reunión por una o más ranuras de e inténtelo de nuevo.

0voto

ForeignCat Puntos 1

Trate de tomar un vistazo en el Recocido Simulado. Es similar a la de los Algoritmos Genéticos como Jeremy E describe, pero en lugar de al azar de generar el conjunto inicial de los horarios de inicio con algunos válida, pero no programación óptima. La idea es generar algún "vecino" de la agenda original por azar arrastrando los pies alrededor de algunas horas de reunión, entonces la prueba de aptitud antes de la iteración.

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 pruebas en contra de algunos mínimo nivel de condición física, también puede especificar un número determinado de iteraciones por lo que podría determinista decir cuando el programa ha terminado de ejecutar.

La cosa acerca de este algoritmo es el resultado final tiende a verse como el estado inicial, por lo que si usted quería peso decir una reunión grande (en términos de tamaño de los fabricantes) temprano en el día, usted podría hacerlo.

-1voto

gleb Puntos 38

Recuerdo la implementación de algo muy similar a tu problema con Un* algoritmo de búsqueda. Encontrarás fácilmente varias implementación del algoritmo disponible, pero con el fin de aplicarlo al problema de programación que se tiene para la construcción de la distancia y la heurística de las funciones basadas en el modelo y de división de tiempo continuo en trozos.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by: