Show simple item record

dc.contributor.authorMagaña Lozano, Dulce Jacqueline
dc.creatorMagaña Lozano, Dulce Jacqueline; 221704es_MX
dc.date.accessioned2015-08-17T10:11:19Zen
dc.date.available2015-08-17T10:11:19Zen
dc.date.issued2008-12-01
dc.identifier.urihttp://hdl.handle.net/11285/568966en
dc.description.abstractEl problema de Calendarización de Cursos (CTT - Course Timetabling), también conocido como Calendarización de Universidad (UTT - University Timetabling), se refiere a la programación de un conjunto de cursos dentro de un número finito de salones y en periodos de tiempo predeterminados. Este problema se considera interesante porque en cada ciclo escolar las instituciones educativas de nivel superior dedican días a la construcción de sus horarios, los cuáles a veces no resultan ser los que mejor se adaptan a las necesidades de sus estudiantes. Técnicas de investigación de operaciones, interacción humano-computadora, e inteligencia artificial se han utilizado para resolver el problema de CTT. En este trabajo se propone el uso de un algoritmo híbrido que utiliza las técnicas de satisfacción de restricciones (CSPs), búsqueda local y algoritmos meméticos para calendarizar un conjunto de cursos en un tiempo razonable, respetando todas las restricciones de asignación y tratando de cumplir con un conjunto de preferencias. Las restricciones de asignación de cursos que se deben de satisfacer forzosamente en los problemas de CTT se conocen como restricciones duras, mientras que las preferencias se manejan como restricciones suaves, y son aquellas que son deseables más no obligatorias. Este algoritmo híbrido se compone de tres fases, la primera fase tiene que ver con la generación de una población de individuos, los cuales representan posibles soluciones al problema. Una parte de estos individuos serán creados con ayuda de un algoritmo de satisfacción de restricciones y la otra parte de manera aleatoria. La segunda fase consiste en evolucionar la población inicial de individuos mediante un algoritmo memético, con el fin de reducir las inconsistencias existentes en la población con respecto al conjunto de restricciones duras y blandas del problema, de forma rápida. La última fase de este algoritmo consiste en ejecutar una búsqueda local sobre el mejor individuo encontrado por el algoritmo memético, con el fin de eliminar cualquier posible conflicto persistente con restricciones duras. El objetivo de combinar estas tres técnicas es generar soluciones factibles y al mismo tiempo con un menor número de restricciones suaves violadas que cuando se aplican los algoritmos de forma independiente. Los resultados obtenidos con el algoritmo híbrido se comparan con los resultados producidos independientemente mediante algoritmos genéticos, CSPs y el buscador local utilizado, y se demuestra que la combinación de algoritmos propuesta produce resultados competitivos en instancias del problema de CTT clasificadas como difíciles, ya que siempre obtiene soluciones factibles y con pocas restricciones suaves violadas, y mejores conforme se complica el problema a resolver.
dc.languagespa
dc.publisherInstituto Tecnológico y de Estudios Superiores de Monterrey
dc.relationInvestigadoreses_MX
dc.relationEstudianteses_MX
dc.relation.isFormatOfversión publicadaes_MX
dc.relation.isreferencedbyREPOSITORIO NACIONAL CONACYT
dc.rightsopenAccess
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0*
dc.subject.classificationArea::INGENIERÍA Y TECNOLOGÍA::CIENCIAS TECNOLÓGICAS::TECNOLOGÍA DE LOS ORDENADORES::LENGUAJES ALGORÍTMICOSes_MX
dc.subject.classificationINGENIERÍA Y TECNOLOGÍA--CIENCIAS TECNOLÓGICAS--TECNOLOGÍA DE LOS ORDENADORES--LENGUAJES ALGORÍTMICOS
dc.titleFusión de algoritmos meméticos con técnicas de satisfacción de restricciones y búsqueda local para calendarización de cursos
dc.typeTesis de Maestría / master Thesis
dc.contributor.departmentTecnológico de Monterrey, Campus Monterreyen
dc.contributor.committeememberConant Pablos, Santiago E.es
dc.contributor.committeememberTerashima Marín, Hugo
dc.contributor.committeememberValenzuela Rendón, Manueles
refterms.dateFOA2018-03-17T21:25:10Z
refterms.dateFOA2018-03-17T21:25:10Z
html.description.abstractEl problema de Calendarización de Cursos (CTT - Course Timetabling), también conocido como Calendarización de Universidad (UTT - University Timetabling), se refiere a la programación de un conjunto de cursos dentro de un número finito de salones y en periodos de tiempo predeterminados. Este problema se considera interesante porque en cada ciclo escolar las instituciones educativas de nivel superior dedican días a la construcción de sus horarios, los cuáles a veces no resultan ser los que mejor se adaptan a las necesidades de sus estudiantes. Técnicas de investigación de operaciones, interacción humano-computadora, e inteligencia artificial se han utilizado para resolver el problema de CTT. En este trabajo se propone el uso de un algoritmo híbrido que utiliza las técnicas de satisfacción de restricciones (CSPs), búsqueda local y algoritmos meméticos para calendarizar un conjunto de cursos en un tiempo razonable, respetando todas las restricciones de asignación y tratando de cumplir con un conjunto de preferencias. Las restricciones de asignación de cursos que se deben de satisfacer forzosamente en los problemas de CTT se conocen como restricciones duras, mientras que las preferencias se manejan como restricciones suaves, y son aquellas que son deseables más no obligatorias. Este algoritmo híbrido se compone de tres fases, la primera fase tiene que ver con la generación de una población de individuos, los cuales representan posibles soluciones al problema. Una parte de estos individuos serán creados con ayuda de un algoritmo de satisfacción de restricciones y la otra parte de manera aleatoria. La segunda fase consiste en evolucionar la población inicial de individuos mediante un algoritmo memético, con el fin de reducir las inconsistencias existentes en la población con respecto al conjunto de restricciones duras y blandas del problema, de forma rápida. La última fase de este algoritmo consiste en ejecutar una búsqueda local sobre el mejor individuo encontrado por el algoritmo memético, con el fin de eliminar cualquier posible conflicto persistente con restricciones duras. El objetivo de combinar estas tres técnicas es generar soluciones factibles y al mismo tiempo con un menor número de restricciones suaves violadas que cuando se aplican los algoritmos de forma independiente. Los resultados obtenidos con el algoritmo híbrido se comparan con los resultados producidos independientemente mediante algoritmos genéticos, CSPs y el buscador local utilizado, y se demuestra que la combinación de algoritmos propuesta produce resultados competitivos en instancias del problema de CTT clasificadas como difíciles, ya que siempre obtiene soluciones factibles y con pocas restricciones suaves violadas, y mejores conforme se complica el problema a resolver.
dc.identificator7
dc.identificator33
dc.identificator3304
dc.identificator120302


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

openAccess
Except where otherwise noted, this item's license is described as openAccess