Palabras clave
combinatorial optimization
schedule problem
investigación de operaciones
optimización combinatoria
problema de horarios
Cómo citar
Resumen
Se presenta un problema de horarios que incluye además de la asignación de espacios de tiempo (turnos) a actividades docentes, la asignación a estas de aulas con capacidades que pueden ser distintas y que suponemos disponibles en todos los turnos.
Probando que una sencilla condición garantiza que las actividades en cada turno son acomodables en las aulas disponibles, se concluye que la asignación de las actividades usando la cantidad mínima de turnos puede hacerse en tiempos polinomial.
Citas
Even, S.; Idtai, A.; Shamir, A. (1976) “On the complexity of time-table and multicom-modity flow problems”, SIAM Journal on Computing5: 691–703.
Jungnickel, D. (1987) Graphen, Netzwerke und Algorithmen. Bibliographiches Institut Mannheim/Wien/Zurich.
Thulasiraman, K.; Swamy, M.N.S. (1982) Graphs: Theory and Algorithms. John Wiley & Sons, New York.
de Werra, D. (1985) “Graphs, Hypergraphs and Timetabling”, Methods of Operations Research 49: 201–213.
de Werra, D. (1981) “Remarks on the requirement matrix of school timetabling. Problems and regular embeddings”, European Journal of Operational Research 6: 298–301.
de Werra, D. (1979) “On the use of alternating chains and hypergraphs in edge coloring”, Journal of Graph Theory 3: 175–182.