problem job español algorithm scheduling np-hard

algorithm - job - Algoritmo de horario de tiempo del maestro



job shop scheduling problem (12)

Este es un problema que he tenido en mente por mucho tiempo. Siendo el hijo de un profesor y un programador, se me ocurrió desde el principio ... pero todavía no he encontrado una solución para ello.

Entonces este es el problema. Uno necesita crear un cronograma para una escuela, usando algunas restricciones. Estos generalmente se dividen en dos categorías:

Comprobaciones de cordura

  • Un maestro no puede enseñar dos clases al mismo tiempo
  • Un estudiante no puede seguir dos lecciones al mismo tiempo
  • Algunos profesores deben tener al menos un día libre durante la semana
  • Todos los días de la semana deben estar cubiertos por la tabla de tiempos
  • El sujeto X debe tener exactamente horas y así cada semana
  • ...

Preferencias

  • El horario de cada maestro debe ser lo más compacto posible (es decir, el maestro debe trabajar todas las horas del día seguidas sin pausas, si es posible)
  • Los maestros que tienen días libres deberían poder expresar una preferencia en qué día
  • Los maestros que trabajan a tiempo parcial deberían poder expresar una preferencia ya sea para trabajar al principio o al final del día escolar.
  • ...

Ahora, después de algunos años de no encontrar una solución (y aprender una o dos cosas mientras tanto ...), me di cuenta de que esto huele a un problema NP-difícil.

¿Está probado como NP-hard?

¿Alguien tiene una idea sobre cómo crackear esto?

Mirar esta pregunta me hizo pensar sobre este problema, y ​​si los algoritmos genéticos serían utilizables en este caso. Sin embargo, sería muy difícil cambiar las posibilidades mientras se mantienen las reglas de control de cordura. Tampoco es claro para mí cómo distinguir los requisitos incompatibles.

Un pequeño apéndice para especificar mejor el problema. Esto se aplica a las aulas de estilo de escuela italiana donde todos los estudiantes están asociados en diferentes clases (por ejemplo: año 1 sección A) y los profesores se mueven entre las clases. Todos los estudiantes de la misma clase tienen el mismo horario, y no tienen opción sobre qué lecciones asistir.

Respondiendo mi propia pregunta:

El proyecto FET mencionado por gnud utiliza este algoritmo:

Algunas palabras sobre el algoritmo: FET usa un algoritmo heurístico, colocando las actividades a su vez, comenzando con las más difíciles. Si no puede encontrar una solución, lo señala a las posibles actividades imposibles, por lo que puede corregir los errores. El algoritmo intercambia actividades recursivamente si es posible para crear espacio para una nueva actividad o, en casos extremos, retrocede y cambia el orden de evaluación. El código importante está en src / engine / generate.cpp. Por favor envíeme un correo electrónico para más detalles o únase a la lista de correo. El algoritmo imita el funcionamiento de un calendario humano, creo.

Enlazar

Siguiendo el ejemplo de "Constraint Based Razoning" de Stringent Software en Wikipedia, diríjanme a estas páginas que tienen un párrafo interesante:

Resolver un problema de satisfacción de restricciones en un dominio finito es un problema de NP completo en general. La investigación ha demostrado una cantidad de subcampos de tiempo polinomial, en su mayoría obtenidos al restringir los dominios o restricciones permitidos o la forma en que las restricciones se pueden colocar sobre las variables. La investigación también ha establecido una relación entre el problema de la satisfacción de restricciones y los problemas en otras áreas, como la teoría del modelo finito y las bases de datos.

Creo que es posible que te falten algunas limitaciones.

Uno preferiría, cuando sea posible, tener profesores programados para las clases para las que están certificados.

Uno podría sospechar que las clases solicitadas y el recuento esperado en cada una de ellas serían significativas.

Creo que el lugar para comenzar sería enumerar todas sus restricciones, encontrar una estructura de datos para representarlas.

Luego crea algún tipo de motor para crear una solución de prueba y luego evalúa su aptitud de acuerdo con las limitaciones.

A continuación, puede agregar los divertidos algoritmos genéticos y ver si puede aumentar la aptitud con el tiempo a medida que se mezclan los genes.

Comience con un pequeño conjunto de restricciones y aumentelas a medida que vea el éxito (si ve el éxito)

Puede haber una manera de tomar las restricciones y calzarlas juntas con algo así como un algoritmo de programación lineal.

Estoy de acuerdo. Parece un desafío divertido

Este es un problema de mapeo: necesita hacer un mapa de cada hora en una semana y cada maestro una actividad (enseñar a cierta clase o hora libre).

Dividir el problema:

  1. Cree la lista de profesores, clases y preferencias, luego permita que el usuario complete algunas de las preferencias en un mapa para tener como punto de partida.
  2. Tome aleatoriamente un elemento de la lista y colóquelo en una posición libre aleatoria en el mapa si no cruza ninguna verificación de cordura hasta que la lista esté vacía. Si en cualquier iteración determinada no puedes colocar un elemento en el mapa sin cruzar un control de cordura, cambia dos posiciones en el mapa y vuelve a intentarlo.
  3. Cuando el mapa esté lleno, intenta cambiar las posiciones en el mapa para optimizar el resultado.

En los pasos 2 y 3, se muestra cada iteración al usuario: elementos que se dejan en la lista, posiciones en el mapa y el siguiente movimiento calculado y que el usuario interviene.

No probé esto, pero este sería mi enfoque inicial.

Soy uno de los desarrolladores que trabaja en la parte del programador de un sistema de información del estudiante. Durante nuestro enfoque original del problema de programación, investigamos algoritmos genéticos para resolver problemas de satisfacción de restricciones, y aunque tuvimos éxito inicialmente, nos dimos cuenta de que había una solución menos complicada para el problema (después de asistir a un taller de programación escolar)

Nuestra implementación actual funciona de maravilla y usa fuerza bruta con heurística inteligente para obtener un cronograma válido en un corto período de tiempo. El cronograma maestro (la asignación de las clases a los profesores) se construye primero, teniendo en cuenta todas las limitaciones que tiene cada maestro mientras se minimiza la posibilidad de conflictos para los estudiantes (de acuerdo con sus solicitudes de cursos). Luego se programa a los estudiantes en las clases usando el mismo método.

Hacer esto le permite hacer que la máquina construya primero un cronograma maestro, y luego hacer que un humano lo modifique si es necesario.

La implementación actual del programador está escrita en Perl, pero otras opciones que visitamos al principio fueron Prolog y CLIPS (sistema experto)

He abordado problemas similares de planificación / programación en el pasado y la técnica de IA que a menudo es más adecuada para esta clase de problema es "Razonamiento basado en restricciones".

Básicamente es un método de fuerza bruta, como sugirió Laurenty, pero el enfoque implica aplicar restricciones en un orden eficiente para hacer que las soluciones no factibles fallen rápidamente, para minimizar el cálculo requerido.

Buscar en Google "Razonamiento basado en restricciones" trae muchos recursos sobre la técnica y su aplicación a los problemas de programación.

Mirar esta pregunta me hizo pensar sobre este problema, y ​​si los algoritmos genéticos serían utilizables en este caso. Sin embargo, sería muy difícil cambiar las posibilidades mientras se mantienen las reglas de control de cordura. Tampoco es claro para mí cómo distinguir los requisitos incompatibles.

Los algoritmos genéticos son muy adecuados para problemas como este. Una vez que se obtiene una representación decente del cromosoma (en este caso, probablemente sea un vector que representa todas las franjas horarias de clase disponibles), está casi todo el camino hasta allí.

No te preocupes por mantener las verificaciones de cordura durante la fase de mutación. La mutación es aleatoria. Las comprobaciones de cordura y preferencia pertenecen a la fase de selección. Un control de cordura fallido reduciría drásticamente la aptitud de un individuo, mientras que una preferencia fallida solo disminuiría levemente la condición física.

Los requisitos incompatibles son un problema diferente por completo. Si son completamente incompatibles, obtendrá una población que no converge en nada útil.

Buena suerte. Ser el hijo de un padre con este tipo de problema es lo que me llevó al grupo de investigación en el que terminé ...

Cuando era niño, mi padre programó oficiales de partidos en una liga local de deportes, esta tenía una larga lista de limitaciones y traté de escribir algo para ayudar. Cuando llegué a la Universidad, incluso la utilicé como mi proyecto de último año, finalmente me conformé con la implementación de Monte Carlo (utilizando un modelo de recocido simulado).

La idea básica es que si no es NP, está bastante cerca, así que en lugar de asumir que hay una solución, me gustaría encontrar lo mejor dentro de un marco de tiempo determinado. Consideraría todas las restricciones con los costos de romperlas: los controles de cordura tendrían costos enormes, las preferencias tendrían costos más bajos (pero aumentarían para más descansos, por lo que si se rompiera una vez, sería menos de la mitad del costo de romperla dos veces).

La idea básica es que comencé con una solución ''aleatoria'' y le costé; luego realizó cambios intercambiando un pequeño número de asignaciones, lo revalorizó y luego, de manera probalística, aceptó o rechazó el cambio.

Después de miles de iteraciones, pulgadas más cerca de una solución aceptable.

Créame, sin embargo, que esta clase de problemas tiene grupos de investigación produciendo doctorados, por lo que está en muy buena compañía.

También puede encontrar cierto interés en el campo de Programación lineal, por ejemplo, símplex y demás.

Esto me recuerda esta publicación en el blog sobre la programación de una conferencia , con una explicación en video aquí .

Cómo lo haría:

Haga que la población incluya dos cosas:

  • ¿Quién enseña qué clase (espero que los profesores enseñen una materia).
  • Lo que una clase toma en un intervalo de tiempo específico.

De esta forma no podemos tener conflictos (un maestro en 2 lugares, o una clase que tiene dos asignaturas al mismo tiempo).

La función de aptitud incluiría:

  • Cuántas franjas horarias ofrece cada maestro por semana.
  • Cuántas franjas horarias tiene un maestro el mismo día (no pueden tener un día completo de enseñanza, esto también debe ser equilibrado).
  • Cuántas franjas horarias del mismo tema tiene una clase el mismo día (¡No pueden tener un día completo de matemáticas!).

Tal vez tome la desviación estándar para todos ellos, ya que deben estar equilibrados.

Sí, creo que esto es NP completo, o al menos para encontrar que la solución óptima es NP completa.

Trabajé en un problema similar en la universidad cuando le dije al padre de un amigo (que era profesor) que podía resolver sus problemas de programación si no encontraba un programa adecuado para eso (esto fue en 1990 más o menos)

No tenía idea en qué me metí. Afortunadamente para nosotros todo lo que teníamos que hacer era encontrar una solución que se ajustara a las limitaciones. Pero en mis pruebas siempre me preocupaba determinar si había alguna solución. Nunca tuvo demasiadas limitaciones y el programa utilizó diferentes heurísticas y seguimiento posterior. Fue muy divertido.

Creo que Bill Gates también trabajó en un sistema como este en la escuela secundaria o la universidad para su escuela secundaria. Aunque no estoy seguro

Buena suerte. Todas mis notas se han ido y nunca llegué a implementar una solución que pudiera comercializar. Fue un proyecto especializado que re-codifiqué cuando aprendí nuevos idiomas (Básico, Esquema, C, VB, C ++)

Diviértete con eso

Veo que este problema puede ser resuelto por el programa Prolog conectándolo a una base de datos y el programa puede hacer que el cronograma tenga un conjunto de restricciones de lectura abt "Problema de satisfacción de restricción prólogo"

No estoy seguro si esto cubre el mismo terreno que la respuesta de @Stringent Software (ya que el nombre es un poco diferente), pero tengo un par de muy buenos amigos que están investigando el área de la Programación de Restricciones . Crear horarios es una aplicación de su investigación.

El Dr. Chris Jefferson creó un programa llamado Minion que puedes descargar desde SourceForge, y es un solucionador de problemas de restricción de fuerza bruta muy rápido escrito en C ++.