Andrés Saldaña Crovo   Cristian Oliva San Martín   Lorena Pradenas Rojas

1 Departamento de Planeamiento de la Producción. Compañía Siderúrgica Huachipato S.A. Avenida Gran Bretaña 2910. Talcahuano, Chile. E-mail: andres.saldana@csh.cl

2 Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de Concepción. Casilla 160-C. Correo 3. Concepción, Chile. E-mail: oliva@udec.cl

3 Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de Concepción. Casilla 160-C. Correo 3. Concepción, Chile. E-mail: lpradena@udec.cl

RESUMEN

En esta investigación se formulan dos modelos de Programación Lineal Entera para un problema de Programación de Horarios para Universidades y se presentan dos estrategias de solución para cada uno de ellos. El problema consiste en programar las asignaturas a ser dictadas, considerando los profesores, días, horarios, aulas y la necesidad de dictar las asignaturas en periodos consecutivos determinados. El objetivo es minimizar la asignación en periodos no deseados, balanceando la carga de trabajo diaria para cada grupo de alumnos. Las estrategias de solución combinan modelos de asignación directa a aulas o asignación a tipos de aulas. Las estrategias de solución que consideran relajación de restricciones, permiten resolver problemas de gran tamaño, a niveles de calidad razonables y utilizando pequeños tiempos computacionales. Los enfoques fueron aplicados a instancias de la Facultad de Ingeniería de la Universidad de Concepción, Chile. Los modelos utilizados en esta investigación pueden ser aplicados a una gran cantidad de problemas de Programación de Horarios en Universidades , proporcionando una gran flexibilidad de resolución.

Palabras clave: Problemas de programación de horarios para universidades, programación lineal entera, optimización combinatoria.

ABSTRACT

In this research, two models of Integer Programming for a University Timetabling Problem are formulated and two solution strategies for each model are presented. The problem consists of programming the courses to be taught, considering teaching faculty, days, periods, classrooms and requirements for courses that are taught in consecutive periods. The objective is to minimize the allocation of undesired time slots as well as balancing the daily workload for each group of students. The solution strategies are based on either combining models of direct allocation to classrooms or types of classrooms. The solution strategies that include reducing constraints, allow solving big problems with reasonable levels of efficiency, using the computer system for a short time. The approaches were used with real data obtained from the Facultad de ingeniería of the Universidad de Concepción, Chile. The models used in this research can be used in more general University Timetabling Problems, providing a great flexibility of resolution.

Keywords: University timetabling problems, integer programming, combinatorial optimization.

AGRADECIMIENTOS

El presente trabajo ha sido presentado a la Escuela de Graduados de la Universidad de Concepción, en el programa de Magíster en Ingeniería Industrial. Este trabajo es apoyado parcialmente por el proyecto ALFA N^o II-0457-FA-FCD-FI-FC, proyecto DIUC N^o 205.093.010-1.0 y por proyecto FUNDACIÓN ANDES, CHILE N^o C-13955/18.

REFERENCIAS

[1] S. Abdennadher and M. Marte. "University Course Timetabling using Constraint Handling Rules". Journal of Applied Artificial Intelligence. Special Issue on Constraint Handling Rules (Holzbaur, C. y Frühwirth, T. Editores.). Vol. 14 N^o 4, pp. 311-325. 2000.

[2] A. Asratian and D. de Werra. "A Generalized Class-Teacher Model for Some Timetabling Problems". European Journal of Operational Research. Vol. 143 N^o 3, pp. 531-542. 2002.

[3] P. Avella and I. Vasil'ev. "A Computational Study of a Cutting Plane Algorithm for University Course Timetabling". Journal of Scheduling. Vol. 8 N^o 6, pp. 497-514. 2005 .

[4] V. Bardadym. "Computer Aided School and University Timetabling. The New Wave". Lecture Notes in Computer Science Series, Vol. 1153, pp. 22-45. 1996 .

[5] P. Brucker and S. Knust. "Resource-Constrained Project Scheduling and Timetabling". Lecture Notes in Computer Science. Vol. 2079, pp. 277-293. 2001 .

[6] E. Burke, D. de Werra and J. Kingston. "Applications to Timetabling". Gross and Yellen Editores. Handbook of Graph Theory, pp. 445-474. 2003.

[7] E. Burke, K. Jackson, J. Kingston and R. Weare. "Automated University Timetabling: The State of the Art". The Computer Journal. Vol. 40 N^o 9, pp. 565-571, 1998.

[8] M. Carrasco and M. Pato. "A Multiobjective Genetic Algorithm for the Class/Teacher Timetabling Problem". Lecture Notes in Computer Science. Vol. 2079, pp. 3-17. 2001.

[9] M. Carter and G. Laporte. "Recent Developments in Practical Course Timetabling". Lecture Notes in Computer Science. Vol. 1408, pp. 3-19. 1998.

[10] S. Daskalaki and T. Birbas. "Efficient Solutions for a University Timetabling Problem Through Integer Programming". European Journal of Operational Research. Vol. 160 N^o 1, pp. 106-120. 2005.

[11] S. Daskalaki, T. Birbas and E. Housos. "An integer Programming Formulation for a Case Study in University Timetabling". European Journal of Operational Research. Vol. 153, pp. 117-135. 2004.

[12] D. de Werra, A. Arsatian and S. Durand. "Complexity of Some Special Types of Timetabling Problems". Journal of Scheduling. Vol. 5, pp. 171-183. 2002.

[13] D. de Werra. "An Introduction to Timetabling". European Journal of Operational Research. Vol. 19, pp. 151-162. 1985.

[14] S. Deris, S. Omatu and H.Ohta. "Timetable Planning Using the Constraint - Based Reasoning". Computers and Operations Research. Vol. 27 N^o 9, pp. 819-840. 2000.

[15] L. di Gaspero and A. Schaerf. "Multi - Neighbourhood Local Search with Application to Course Timetabling". Lecture Notes in Computer Science. Vol. 2740, pp. 263-278. 2003.

[16] M. Dimopoulou and P. Miliotis. "An Automated University Course Timetabling System Developed in a Distributed Environment: A Case Study". European Journal of Operational Research. Vol. 153, pp. 136-147. 2004.

[17] W. Legierski. "Search Strategy for Constraint - Based Class - Teacher Timetabling". Lectures Notes in Computer Science. Vol. 2740, pp. 247-261. 2003.

[18] S. MirHassani. "A Computational Approach to Enhancing Course Timetabling with Integer Programming". Applied Mathematics and Computation. Vol. 175 N^o 1, pp. 814-822. 2006.

[19] A. Qualizza and P. Serafini. "A Column Generation Scheme for Faculty Timetabling". Lecture Notes in Computer Science. Vol. 3616, pp. 161-173. 2005.

[20] L. Reis and E. Oliveira. "A Language for Specifying Complete Timetabling Problems". Lecture Notes in Computer Science. Vol. 2079, pp. 322-341. 2001.

[21] H. Santos, L. Ochi and M. Souza. "A Tabu Search Heuristic with Eficient Diversification Strategies for the Class/Teacher Timetabling Problem". Lecture Notes in Computer Science. Vol. 3616, pp. 343-358. 2005.

[22] K. Socha, M. Sampels and M. Manfrin. "Ant Algorithms for The University Course Timetabling Problem with Regard to The State - of - The - Art". In Applications of Evolutionary Computing: Proceedings of Evo Workshops 2003. Berlin , Germany . Lecture Notes in Computer Science. Vol. 2611, pp. 334-345. 2003.

[23] A. Tripathy. "School Timetabling - A Case in Large Binary Integer Linear Programming". Management Science. Vol. 30 N^o 12, pp. 1473-1489. 1984.

[24] H. Ueda, D. Ouchi, D. Takahashi and T. Miyahara. "A Co-evolving Timeslot/Room Assignment Genetic Algorithm Technique for University Timetabling". Lecture Notes in Computer Science. Vol. 2079, pp. 48-63. 2001.

[25] K. Zervoudakis and P. Stamatopoulos. "A Generic Object - Oriented Constraint - Based Model for University Course Timetabling". Lecture Notes in Computer Science. Vol. 2079, pp. 28-47. 2001.

[26] ILOG. "ILOG CPLEX 9.0 Reference's Manual". 2003.