UNA SOLUCIÓN BASADA EN AGENTES AL PROBLEMA DE GENERACIÓN DE HORARIOS
Resumen
La generación de horarios de clase es una actividad académico-administrativa inevitable en las organizaciones educativas. Además de su carácter periódico, es de alta complejidad computacional: se trata de un problema NPcompleto. Las interacciones típicas en una organización educativa tienden a mantener la solución del problema en ese orden de complejidad computacional. Se ha acostumbrado que quien controla los recursos de infraestructura, en una orientación jerárquica, gobierna la generación de horarios. No obstante, en un contexto en el que los proveedores de infraestructura –la organización educativa–, los profesores y los estudiantes actúan como pares, los horarios de clase pueden emerger de las interacciones. Suponiendo que la organización educativa está al mismo nivel que cada docente y que cada estudiante, se tiene un entorno apropiado para un sistema multiagente. Este artículo da cuenta de los resultados de pruebas realizadas a una aplicación basada en agentes para la resolución del problema de generación de horarios.
Citas
R. M Karp, «Reducibility among combinatorial problems» in R.E. Miller and J.W. Tatcher (Eds.), Complexity of computer computations. New York. Plenum Press. Pp. 85-103, 1972.
V. Bardadym, «Computer Aided School and University Timetabling. The New Wave» Lecture Notes in Computer Science Series, Vol. 1153, pp.
-45, 1996.
E. Burke, K. Jackson, J. Kingston y R. Weare, «Automated University Timetabling: The State of the Art» The Computer Journal. 1998; 40(9):565- 571.
M. Carter y G. Laporte, «Recent Developments in Practical Course Timetabling» Lecture Notes in Computer Science. Vol. 1408, pp. 3-19, 1998.
R. Hernández, J. Miranda P., P.A. Rey, «Programación de Horarios de Clases y Asignación de Salas para la Facultad de Ingeniería de la Universidad Diego Portales Mediante un Enfoque de Programación Entera» Revista Ingeniería de Sistemas, Vol. XXII, Año 2008. pp. 121-141, 2008.
J. Gallart Suárez, F. Alva Manchego, N. A. Alama, G. Bejarano Nicho, «Generación Inteligente de Horarios Empleando Heurísticas GRASP con Búsqueda Tabú para la Pontificia Universidad Católica
del Perú» Revista de Ingeniería Informática PUCP, Vol. 1 No.1, Artículo 2, abril 2010. Pp.15-23, 2010.
J.M. Mejía Caballero, C. Paternina Arboleda, «Asignación de Horarios de Clases Universitarias Mediante Algoritmos Evolutivos» Revista Educación en Ingeniería, Universidad del Norte, Barranquilla (Colombia), ISSN 1900-8260, Junio de 2010 • N°. 9 • Pp 140-149 (2010). • Publicada en línea por la Asociación Colombiana de Facultades de Ingeniería -ACOFI- www.acofi.edu.co, 2010.
A. Barr, E.A. Feigenbaum, The Handbook of Artificial Intelligence. Vol. 1. Addison Wesley. Stanford, CA., 1989.
N. Graham, Artificial Intelligence: Making machines «think». Tab Books. Blure Ridge Summit, 1979.
P.H. Winston, Artificial Intelligence. Addison Wesley. Phillipines, 1979.
J. Negrete, De la filosofía a la inteligencia artificial. Noriega, España, 1992.
L.Von Bertalanffy, Teoría general de los sistemas. Fondo de Cultura Económica, Bogotá, 1994.
J. Ferber, Multiagent systems, an introduction to distributed artificial intelligence, Addison Wesley, 1999.
Á. Espinosa, «Una visión cibernética de las organizaciones sociales» in: H. Andrade, I. Dyner, Á. Espinosa, H. López, R. Sotaquirá, Pensamiento sistémico: Diversidad en búsqueda de unidad. Ediciones Universidad Industrial de Santander, Bucaramanga, 2001.
R. Ashby, Introducción a la cibernética. Ediciones Nueva Visión, Buenos Aires, 1976.
O. López-Cruz, V. Muñoz, «Trabajador, trabajo y sociedad: Una relación que se complejiza en la interacción» In: Revista de Tecnología, Vol. 5 No.2. Universidad El Bosque. Bogotá D.C. pp.59-77. Jul-
Dic., 2006.
M.J. Wooldridge, An introduction to multiagent systems, 2nd ed. John Wiley & Sons. Great Britain, 2009.
G. Weiss, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, 1999.
C. Iglesias, M. Marijo, J. González «A survey of agent oriented methodologies» in: ATAL ’98 Proceedings of the 5th International Workshop on Intelligent Agents V, Agent Theories, Architectures,
and Languages, 1999.
J. Rodríguez, «Metodología AOPOA» in E. González, C. Bustacara (Eds): Desarrollo de aplicaciones basadas en sistemas multiagentes. Ediciones Pontificia Universidad Javeriana, Bogotá, 2007.
C. Meyers, «J.B. Orlin «Very large-scale neighborhood search techniques in timetabling problems» in Proceeding PATAT’06 Proceedings of the 6th international conference on Practice and theory of
automated timetabling VI, 2007.
G. Veysel «Stability of an Asynchronous Swarm With Time Dependent Communication Links» Transactions on Systems, Man, and Cybernetics, Vol. 38, 2008.
M. Tuga, R. Berretta, A. Mendes, «A Hybrid Simulated Annealing with Kempe Chain Neighborhood for the University Timetabling Problem» in Computer and Information Science, 2007. ICIS 2007. 6th IEEE/ACIS International Conference. Pp. 400-405, 2007.
M. Davoudzadeh, R. Rafeh, R. Rashidi «Linear Solution for the University Timetabling Problem» in Computer and Electrical Engineering, 2009. ICCEE ’09. Second International Conference. Vol. 2 Pp. 54-57, 2009.
K. Nguyen, D. Nguyen, K. Trieu, N. Tran, «Automating a Real-World University Timetabling Problem with Tabu Search Algorithm» in Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), 2010 IEEE RIVF International Conference. Pp. 1-6, 2010.
R.Perzina, «Solving Multicriteria University Timetabling Problem by a Self-adaptive Genetic Algorithm with Minimal Perturbation Information Reuse and Integration» in 2007. IRI 2007. IEEE International Conference. Pp. 98-103, 2007.
H. Kanoh, Y. Sakamoto, «Interactive timetabling system using genetic algorithms». Systems, Man and Cybernetics, 2004 IEEE International Conference. Pp. 5852-5857, 2004.
S. Abdullah, H. Turabieh, «Generating University Course Timetable Using Genetic Algorithms and Local Search. Convergence and Hybrid Information Technology» in 2008. ICCIT ’08. Third
International Conference. Vol. 1. Pp. 254-260, 2008.
T. Lutuksin, P. Pongcharoen, «Best-Worst Ant Colony System Parameter Investigation by Using Experimental Design and Analysis for Course Timetabling Problem» Computer and Network Technology (ICCNT), 2010 Second International Conference. Pp. 467-471, 2010.
M. Ayob, G. Jaradat, «Hybrid Ant Colony systems for course timetabling problems» in Data Mining and Optimization, 2009. DMO ’09. 2nd Conference. Pp. 120-126, 2009.
C.Y. Cheong, K.C. Tan, B. Veeravalli, «Solving the Exam Timetabling Problem via a Multi-Objective Evolutionary Algorithm - A More General
Approach» in Computational Intelligence in Scheduling, 2007. In: SCIS ’07. IEEE Symposium. pp. 165-172, 2007.
M. Aldasht, M. Alsaheb, S. Adi, M.A. Qopita «University Course Scheduling Using Evolutionary Algorithms» in Computing in the Global Information Technology, 2009. ICCGI ’09. Fourth International Multi-Conference. Pp. 47-51, 2009.
L. Di Gaspero, S. Mizzaro, A. Schaerf «A MultiAgent Architecture for Distributed CourseTimetabling» In Proc. of the 5th Int. Conf. on the Practice and Theory of Automated Timetabling (PATAT-2004), pp. 471-474, 2004.
D. Strnad, N.Guid «A Multi-Agent System for University Course Timetabling» Journal Applied Artificial Intelligence Vol. 21 Issue 2, pp.137-153, Feb. 2007.
M. Oprea «Multi-Agent System for University Course Timetable Scheduling» in ICVL Proceedings, pp. 231-238., Bucharest, 2006.
Y. Yang, R. Paranjape, L. Benedicenti «An Agent Based General Solution Model for the Course Timetabling Problem» in The Fifth International Joint conference on Autonomous Agents, (AAMOS’ 06), Hakodate, Kokkaido, 2006.
M.-H.Verrons, P.Mathieu «How to solve a timetabling problem by negotiation?» in Proceedings of 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT), pp. 502-505, 2006.
E. Kaplansky, A. Meisels «Negotiation among Scheduling Agents for Distributed Timetabling» in Proceedings of 5th International Conference on the Practice and Theory of Automated Timetabling (PATAT) pp. 517-520., Pittsburgh, (2004).
