Una solución basada en agentes al problema de generación de horarios

• LÓPEZ-CRUZ, ORLANDO ^[1]
  1. [1] Pontífica Universidad Javeriana

     Pontífica Universidad Javeriana

     Colombia

     
• Localización: Revista Ingeniería, Matemáticas y Ciencias de la Información, ISSN-e 2357-3716, Vol. 2, Nº. 3, 2015 (Ejemplar dedicado a: Revista Ingeniería, Matemáticas y Ciencias de la Información), págs. 73-85
• Idioma: español
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    Course timetabling generation is an unavoidable academic-administrative activity in educational organizations.Besides its periodicity, it is a high computational complex NP-Complete problem. Typical interactions in an educationalorganization cause the solution to remain in that complexity order. It is used that those whom hierarchical controlresources, governs course timetabling generation. Nevertheless, when infrastructure providers –the educationalorganization-, teachers and students act as peers, course timetabling may emerge from interactions. When assumingthat an educational organization is at the same level that teachers and students, there is an appropriate environmentfor an agent-based system. This paper shed light on results from tests performed on an agent-based application tosolve the timetable problem.

• Referencias bibliográficas
  • R. M Karp, «Reducibility among combinatorial problems» in R.E. Miller and J.W. Tatcher (Eds.), Complexity of computer computations. New York....
  • V. Bardadym, «Computer Aided School and University Timetabling. The New Wave» Lecture Notes in Computer Science Series, Vol. 1153, pp.-45,...
  • E. Burke, K. Jackson, J. Kingston y R. Weare, «Automated University Timetabling: The State of the Art» The Computer Journal. 1998; 40(9):565-...
  • 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...
  • 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...
  • 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...
  • 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...
  • 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....
  • 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...
  • J. Rodríguez, «Metodología AOPOA» in E. González, C. Bustacara (Eds): Desarrollo de aplicaciones basadas en sistemas multiagentes. Ediciones...
  • C. Meyers, «J.B. Orlin «Very large-scale neighborhood search techniques in timetabling problems» in Proceeding PATAT’06 Proceedings of the...
  • automated timetabling VI, 2007.
  • G. Veysel «Stability of an Asynchronous Swarm With Time Dependent Communication Links» Transactions on Systems, Man, and Cybernetics, Vol....
  • M. Tuga, R. Berretta, A. Mendes, «A Hybrid Simulated Annealing with Kempe Chain Neighborhood for the University Timetabling Problem» in Computer...
  • M. Davoudzadeh, R. Rafeh, R. Rashidi «Linear Solution for the University Timetabling Problem» in Computer and Electrical Engineering, 2009....
  • K. Nguyen, D. Nguyen, K. Trieu, N. Tran, «Automating a Real-World University Timetabling Problem with Tabu Search Algorithm» in Computing...
  • R.Perzina, «Solving Multicriteria University Timetabling Problem by a Self-adaptive Genetic Algorithm with Minimal Perturbation Information...
  • H. Kanoh, Y. Sakamoto, «Interactive timetabling system using genetic algorithms». Systems, Man and Cybernetics, 2004 IEEE International Conference....
  • S. Abdullah, H. Turabieh, «Generating University Course Timetable Using Genetic Algorithms and Local Search. Convergence and Hybrid Information...
  • 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...
  • M. Ayob, G. Jaradat, «Hybrid Ant Colony systems for course timetabling problems» in Data Mining and Optimization, 2009. DMO ’09. 2nd Conference....
  • 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...
  • L. Di Gaspero, S. Mizzaro, A. Schaerf «A MultiAgent Architecture for Distributed CourseTimetabling» In Proc. of the 5th Int. Conf. on the...
  • D. Strnad, N.Guid «A Multi-Agent System for University Course Timetabling» Journal Applied Artificial Intelligence Vol. 21 Issue 2, pp.137-153,...
  • 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...
  • M.-H.Verrons, P.Mathieu «How to solve a timetabling problem by negotiation?» in Proceedings of 6th International Conference on the Practice...
  • E. Kaplansky, A. Meisels «Negotiation among Scheduling Agents for Distributed Timetabling» in Proceedings of 5th International Conference...