Qué algoritmo usar para generar el horario de las escuelas

Question

Estoy trabajando en una aplicación simple que generará un horario (planificador diario) para las escuelas. He leído los conceptos básicos de los algoritmos, pero estoy confundido en cuanto a dónde comenzar.

El problema:
Asignar maestros a clases, teniendo en cuenta un gran número de limitaciones como:
1) Asunto
2) Experiencia del maestro
3) No más de 2 clases de forma continua .. etc

Sobra decir que no debe haber superposición. Básicamente, necesito asignar N maestros a M clases con un número fijo de horas de trabajo todos los días (8).

Las entradas:
1) Número total de clases
2) Maestros junto con su experiencia en la materia
3) Materias/Cursos para cada clase
4) Número de conferencias por clase por día
5) Otras restricciones flexibles como mínimo/máximo de horas de trabajo de un profesor por día, horas de trabajo totales por maestro por semana, etc

Mis preguntas:
1) ¿es correcto para verlo como un problema de asignación con múltiples restricciones?
2) ¿Qué algoritmo debería usar? (¿Algún algoritmo húngaro?)
3) ¿Debería comenzar obteniendo todo el conjunto de restricciones de una vez, y luego generar la tabla, o debería hacerse en pasos intermedios?

¡Soy un principiante para aprender/los algoritmos de la aplicación, así que cualquier ayuda apuntarme en la dirección correcta apreciada! Gracias.

Answer 1

Para empezar, ha elegido un gran problema. La optimización de programación como esta es NP completa. Hay una tonelada de artículos sobre cómo lidiar con problemas como este, la clase de problema se conoce como restricción de satisfacción. Puede realizar una búsqueda exhaustiva que es más fácil pero que consume mucho tiempo, si tiene más de un puñado de clases, no funcionará. Puede echar un vistazo a la base de solucionador, que es un conjunto de herramientas para .net para resolver este tipo de cosas. Scott Hanselman hizo un podcast al respecto aquí http://www.hanselminutes.com/default.aspx?showID=209 y puede encontrar más información al respecto aquí http://code.msdn.microsoft.com/solverfoundation. Si te apetece hacerlo tú mismo, prueba mirar a GSAT o, por el contrario, algunos de estos algoritmos evolutivos parecen interesantes http://www.springer.com/engineering/book/978-3-540-48582-7.

Answer 2

Esta pregunta sigue apareciendo al menos una vez a la semana aquí y las respuestas (incluida la mía) son siempre las mismas. Creo que deberíamos crear una etiqueta específica para los algoritmos de programación si no existe.

Reitero que la técnica de solución más adecuada para problemas de programación como esta se encuentra en el área de la programación de restricciones. Mientras que otras técnicas de optimización están bien para problemas pequeños, la formulación a menudo es dolorosa para algunas limitaciones. Considere todas las variables enteras que debe crear para algunas restricciones simples. Debido a que el problema a menudo requiere un conjunto de programas viables (o para determinar la inviabilidad) en lugar de una solución óptima, CP es el enfoque preferido, ya que eso es lo que está diseñado para hacer. La mayoría de los otros enfoques requieren que el usuario "fuerce" una condición de optimalidad en el problema donde uno realmente no existe.