Algoritmo para calcular el horario dado restricciones

Question

Estoy considerando un problema hipotético, y buscando una guía sobre cómo abordar la solución del problema, desde un punto de vista algorítmico.

El problema:

Considérese una universidad. Tiene los siguientes objetos:

• Personal docente. Cada miembro del personal enseña uno o más documentos.
• Estudiantes. Cada estudiante toma uno o más papeles.
• Habitaciones. Las habitaciones tienen un cierto número de estudiantes y contienen ciertos tipos de equipos.
• Papeles. Requiere un cierto tipo de equipo y una cierta cantidad de tiempo cada semana.

Dada la información sobre la matrícula (IE-cuántos estudiantes están inscritos en cada papel, y lo que el personal se asignan para enseñar a cada papel), ¿cómo puedo calcular un calendario que obedece a las siguientes restricciones:

1. El personal solo puede enseñar una cosa a la vez.
2. Los estudiantes solo pueden asistir a un trabajo a la vez.
3. Las habitaciones solo pueden albergar a un cierto número de estudiantes.
4. Los papeles que requieren cierto tipo de equipo solo se pueden guardar en una habitación que proporcione ese tipo de equipo.
5. El horario de atención es de lunes a viernes, 8-12 y 1-5.

Discusión:

En realidad no estoy demasiado preocupado por la situación antes descrita - es la clase general de problema que tengo curiosidad por saber. A primera vista Me parece una buena opción para un algoritmo genético, pero la función de aptitud para tal algoritmo sería increíblemente compleja.

¿Cuál es un buen enfoque para tratar de resolver este tipo de problema de restricción de satisfacción?

Supongo que probablemente no haya manera de resolver esto perfectamente, ya que los estudiantes pueden tomar una combinación de documentos que conducen a situaciones imposibles, especialmente a medida que crece el número de estudiantes &.

Answer 1

Siguiendo con los algoritmos genéticos, no creo que la función de aptitud para esto sea muy compleja, sino todo lo contrario.

Básicamente, simplemente verifique su solución candidata (cualquiera que sea la codificación) para cada una de las restricciones (solo tiene 5) y asigne un peso a ellas para que cuando una restricción no se satisfaga el peso se agregue a una puntuación total que podría representar aptitud.

En ese caso, solo minimiza la función de aptitud (porque la mejor forma física posible es 0, lo que significa que se cumplen todas las restricciones) y deja que la GA reduzca los números.

La codificación se necesitará un poco de averiguar, pero una vez que lo ha hecho debe ser sencillo, a menos que me falta algo, por supuesto :)

Answer 2

Una versión muy restringida de este problema es NP-Complete.

Considere el caso cuando exactamente un estudiante puede tomar un papel.

Ahora, para un intervalo de tiempo dado (digamos que el documento se enseña todo el día), puede construir un gráfico de 3 partes con Salas, Papeles y Estudiantes, con una ventaja entre un papel y un alumno si ese alumno desea tómalo. También agregue bordes entre un papel y sus posibles habitaciones.

Ahora vemos que el 3 Dimensional matching problem es una instancia de su problema: necesita elegir una combinación que no se solape (estudiante, papel, sala) para ese intervalo de tiempo en particular.

Probablemente esté mejor con algunas heurísticas para el problema general. Lo siento, no puedo ayudarte allí.

Espero que ayude.