Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos

En este estudio se presenta un modelo de programación no lineal en variables enteras para un problema de programación de horarios universitarios vespertinos y se propone un algoritmo para su solución. El problema consiste en programar asignaturas en un horizonte de planificación considerando profeso...

Full description

Autores:
Oliva San Martín, Cristian David
Ramírez Guzmán, Gastón Marcelo
Tipo de recurso:
Article of journal
Fecha de publicación:
2014
Institución:
Corporación Universidad de la Costa
Repositorio:
REDICUC - Repositorio CUC
Idioma:
spa
OAI Identifier:
oai:repositorio.cuc.edu.co:11323/2636
Acceso en línea:
https://hdl.handle.net/11323/2636
https://repositorio.cuc.edu.co/
Palabra clave:
Problema de programación de horarios universitarios vespertinos
Algoritmo de tipo búsqueda tabú
Metaheurísticas
Evening university timetabling problem
Algorithm of tabu search type
Metaheuristics
Rights
openAccess
License
http://purl.org/coar/access_right/c_abf2
id RCUC2_7f519288727c477b536ad084be63f6d7
oai_identifier_str oai:repositorio.cuc.edu.co:11323/2636
network_acronym_str RCUC2
network_name_str REDICUC - Repositorio CUC
repository_id_str
dc.title.spa.fl_str_mv Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
dc.title.translated.eng.fl_str_mv A tabu search algorithm for an evening university timetabling problem
title Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
spellingShingle Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
Problema de programación de horarios universitarios vespertinos
Algoritmo de tipo búsqueda tabú
Metaheurísticas
Evening university timetabling problem
Algorithm of tabu search type
Metaheuristics
title_short Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
title_full Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
title_fullStr Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
title_full_unstemmed Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
title_sort Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos
dc.creator.fl_str_mv Oliva San Martín, Cristian David
Ramírez Guzmán, Gastón Marcelo
dc.contributor.author.spa.fl_str_mv Oliva San Martín, Cristian David
Ramírez Guzmán, Gastón Marcelo
dc.subject.spa.fl_str_mv Problema de programación de horarios universitarios vespertinos
Algoritmo de tipo búsqueda tabú
Metaheurísticas
topic Problema de programación de horarios universitarios vespertinos
Algoritmo de tipo búsqueda tabú
Metaheurísticas
Evening university timetabling problem
Algorithm of tabu search type
Metaheuristics
dc.subject.eng.fl_str_mv Evening university timetabling problem
Algorithm of tabu search type
Metaheuristics
description En este estudio se presenta un modelo de programación no lineal en variables enteras para un problema de programación de horarios universitarios vespertinos y se propone un algoritmo para su solución. El problema consiste en programar asignaturas en un horizonte de planificación considerando profesores, aulas, alumnos, días y un conjunto de restricciones, buscando minimizar la penalidad de no satisfacer los requerimientos de profesores, el número de cambios de sala y el número de periodos libres entre cursos. Se propone un modelo matemático y una implementación de un algoritmo de tipo búsqueda tabú. Para evaluar la efectividad del algoritmo se utilizaron casos de prueba con datos reales del Instituto IPEGE (Chile), en los que el algoritmo es capaz de obtener soluciones factibles en un tiempo razonable. Los parámetros de dicho algoritmo fueron calibrados con los casos de prueba, para posteriormente evaluar su desempeño. Se muestra que este obtuvo mejores soluciones que el método manual.
publishDate 2014
dc.date.issued.none.fl_str_mv 2014-10-03
dc.date.accessioned.none.fl_str_mv 2019-02-19T23:06:06Z
dc.date.available.none.fl_str_mv 2019-02-19T23:06:06Z
dc.type.spa.fl_str_mv Artículo de revista
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.content.spa.fl_str_mv Text
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/article
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/ART
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/acceptedVersion
format http://purl.org/coar/resource_type/c_6501
status_str acceptedVersion
dc.identifier.citation.spa.fl_str_mv Oliva San Martín, C., & Ramírez Guzmán, G. (2014). Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos. INGE CUC, 9(2), 58-65. Recuperado a partir de https://revistascientificas.cuc.edu.co/ingecuc/article/view/7
dc.identifier.issn.spa.fl_str_mv 0122-6517, 2382-4700 electrónico
dc.identifier.uri.spa.fl_str_mv https://hdl.handle.net/11323/2636
dc.identifier.eissn.spa.fl_str_mv 2382-4700
dc.identifier.instname.spa.fl_str_mv Corporación Universidad de la Costa
dc.identifier.pissn.spa.fl_str_mv 0122-6517
dc.identifier.reponame.spa.fl_str_mv REDICUC - Repositorio CUC
dc.identifier.repourl.spa.fl_str_mv https://repositorio.cuc.edu.co/
identifier_str_mv Oliva San Martín, C., & Ramírez Guzmán, G. (2014). Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos. INGE CUC, 9(2), 58-65. Recuperado a partir de https://revistascientificas.cuc.edu.co/ingecuc/article/view/7
0122-6517, 2382-4700 electrónico
2382-4700
Corporación Universidad de la Costa
0122-6517
REDICUC - Repositorio CUC
url https://hdl.handle.net/11323/2636
https://repositorio.cuc.edu.co/
dc.language.iso.none.fl_str_mv spa
language spa
dc.relation.ispartofseries.spa.fl_str_mv INGE CUC; Vol. 9, Núm. 2 (2013)
dc.relation.ispartofjournal.spa.fl_str_mv INGE CUC
INGE CUC
dc.relation.references.spa.fl_str_mv [1] J. Franco, E. Toro y R. Gallego, “Problema de asignación óptima de salones resuelto con búsqueda tabú”, Ingeniería y Desarrollo (Universidad del Norte), vol. 24, pp. 149-175, 2008.
[2] A. Saldaña, C. Oliva, and L. Pradenas, “Models of integer programming for an university Timetabling problem”, Ingeniare , vol. 15, pp. 245-259, 2007.
[3] R. Alvarez, E. Crespo, and J. Tamarit, “A tabú Search algorithm to schedule university examinations”, QUES -TIIO , vol. 21, pp. 201-215, 1997.
[4] E. Mooney and R. Rardin, “Tabu search for a class of scheduling problems”, Annals of Operations Research, vol. 41, pp. 253-278, 1993.
[5] W. Parmenter, E. Mooney, and R. Rardin, “Large scale classroom scheduling”, IIE Transactions, vol. 28, pp.369-378, 1996.
[6] A. Molina, “Algoritmos evolutivos para la resolución de un problema de tipo Timetabling”, tesis, Universidad de Valparaíso, Chile, 2007.
[7] R. Hernández, J. Miranda, and P. 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”, Ingeniería de Sistemas, vol. 22, pp. 123-143, 2008.
[8] S. Abarca, “Sistema de asignación de horarios de clases”, tesis, Universidad Católica de Valparaíso, Chile, 1996.
[9] A. Moura, and R. Scaraficci, International journal of operational research, vol. 7, 19, pp. 152-170, 2010.
[10] T. Cura (2007) Istanbul Ticaret Üniversitesi [Online]. Disponible: http://www.iticu.edu.tr/kutuphane/dergi/ f12/M00196.pdf.
[11] J. Mejía, “Asignación de horarios de clases universitarias mediante algoritmos evolutivos”, tesis, Universidad del Norte, Barranquilla(Colombia), 2008.
[12] P. Flores, E. Brau, J. Monteverde, N. Salazar, J. Figueroa, E. Cadena y C. Lizárraga, “Experimentos con algoritmos genéticos para resolver un problema real de programación Maestros-Horarios-Cursos”, Revista Iberoamericana de Sistemas, Cibernética e Informática, vol. 1, pp. 42-46, 2004.
[13] ILOG CPLEX 9.0 User’s Manual. IBM Co., 2003.
[14] S. Abdullah and H. Turabieh, “On the use of multineighborhood structures within a Tabu-based memetic approach to university timetabling problems”, Information Sciences, Vol 191, pp.146-168, 2012.
dc.relation.ispartofjournalabbrev.spa.fl_str_mv INGE CUC
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
rights_invalid_str_mv http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Corporación Universidad de la Costa
dc.source.spa.fl_str_mv INGE CUC
institution Corporación Universidad de la Costa
dc.source.url.spa.fl_str_mv https://revistascientificas.cuc.edu.co/ingecuc/article/view/7
bitstream.url.fl_str_mv https://repositorio.cuc.edu.co/bitstreams/29cbb6ba-33fa-4927-91fc-9f59a9696b94/download
https://repositorio.cuc.edu.co/bitstreams/50af486e-876b-407b-a9c8-25c8a843ab30/download
https://repositorio.cuc.edu.co/bitstreams/29ccfed0-7c68-45d5-839c-18831e772732/download
https://repositorio.cuc.edu.co/bitstreams/f262b71c-f6f2-4f7a-8866-3b95766123f2/download
bitstream.checksum.fl_str_mv 921eebf02871dd3aa30c8d60d5f2e368
8a4605be74aa9ea9d79846c1fba20a33
e779520eca466e8dec5bfafa283bd322
8f3121f83bb46c9e4532bdff8accca30
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio de la Universidad de la Costa CUC
repository.mail.fl_str_mv repdigital@cuc.edu.co
_version_ 1811760783418195968
spelling Oliva San Martín, Cristian DavidRamírez Guzmán, Gastón Marcelo2019-02-19T23:06:06Z2019-02-19T23:06:06Z2014-10-03Oliva San Martín, C., & Ramírez Guzmán, G. (2014). Algoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos. INGE CUC, 9(2), 58-65. Recuperado a partir de https://revistascientificas.cuc.edu.co/ingecuc/article/view/70122-6517, 2382-4700 electrónicohttps://hdl.handle.net/11323/26362382-4700Corporación Universidad de la Costa0122-6517REDICUC - Repositorio CUChttps://repositorio.cuc.edu.co/En este estudio se presenta un modelo de programación no lineal en variables enteras para un problema de programación de horarios universitarios vespertinos y se propone un algoritmo para su solución. El problema consiste en programar asignaturas en un horizonte de planificación considerando profesores, aulas, alumnos, días y un conjunto de restricciones, buscando minimizar la penalidad de no satisfacer los requerimientos de profesores, el número de cambios de sala y el número de periodos libres entre cursos. Se propone un modelo matemático y una implementación de un algoritmo de tipo búsqueda tabú. Para evaluar la efectividad del algoritmo se utilizaron casos de prueba con datos reales del Instituto IPEGE (Chile), en los que el algoritmo es capaz de obtener soluciones factibles en un tiempo razonable. Los parámetros de dicho algoritmo fueron calibrados con los casos de prueba, para posteriormente evaluar su desempeño. Se muestra que este obtuvo mejores soluciones que el método manual.This study presents a model of non-linear integer programming for an evening university timetabling problem and proposes an algorithm for its solution. The problem consists of programming subjects over a planning horizon considering teachers, classrooms, students, days and a set of constraints, trying to minimize the penalty of unsatisfied requirements of teachers, the number of changes of classrooms and the numbers of free periods between courses. A mathematical model is proposed beside the implementation of tabu search algorithm. Test cases are proposed to evaluate the effectiveness of the algorithm, which have real data obtained from IPEGE Institute (Chile), where the algorithm could obtain feasible solutions within a reasonable time. The parameters of the algorithm were calibrated with the test cases to later evaluate its performance, showing that it obtained better solutions than the manual method by an average of 66,5 % and it is about 62,7 % of lower bound calculatedOliva San Martín, Cristian David-f75ca816-3ad6-4ea4-a9c9-a3a7d0f4ed1a-0Ramírez Guzmán, Gastón Marcelo-d43abf09-3325-4b28-a57d-1380d4736309-0application/pdfspaCorporación Universidad de la CostaINGE CUC; Vol. 9, Núm. 2 (2013)INGE CUCINGE CUC[1] J. Franco, E. Toro y R. Gallego, “Problema de asignación óptima de salones resuelto con búsqueda tabú”, Ingeniería y Desarrollo (Universidad del Norte), vol. 24, pp. 149-175, 2008.[2] A. Saldaña, C. Oliva, and L. Pradenas, “Models of integer programming for an university Timetabling problem”, Ingeniare , vol. 15, pp. 245-259, 2007.[3] R. Alvarez, E. Crespo, and J. Tamarit, “A tabú Search algorithm to schedule university examinations”, QUES -TIIO , vol. 21, pp. 201-215, 1997.[4] E. Mooney and R. Rardin, “Tabu search for a class of scheduling problems”, Annals of Operations Research, vol. 41, pp. 253-278, 1993.[5] W. Parmenter, E. Mooney, and R. Rardin, “Large scale classroom scheduling”, IIE Transactions, vol. 28, pp.369-378, 1996.[6] A. Molina, “Algoritmos evolutivos para la resolución de un problema de tipo Timetabling”, tesis, Universidad de Valparaíso, Chile, 2007.[7] R. Hernández, J. Miranda, and P. 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”, Ingeniería de Sistemas, vol. 22, pp. 123-143, 2008.[8] S. Abarca, “Sistema de asignación de horarios de clases”, tesis, Universidad Católica de Valparaíso, Chile, 1996.[9] A. Moura, and R. Scaraficci, International journal of operational research, vol. 7, 19, pp. 152-170, 2010.[10] T. Cura (2007) Istanbul Ticaret Üniversitesi [Online]. Disponible: http://www.iticu.edu.tr/kutuphane/dergi/ f12/M00196.pdf.[11] J. Mejía, “Asignación de horarios de clases universitarias mediante algoritmos evolutivos”, tesis, Universidad del Norte, Barranquilla(Colombia), 2008.[12] P. Flores, E. Brau, J. Monteverde, N. Salazar, J. Figueroa, E. Cadena y C. Lizárraga, “Experimentos con algoritmos genéticos para resolver un problema real de programación Maestros-Horarios-Cursos”, Revista Iberoamericana de Sistemas, Cibernética e Informática, vol. 1, pp. 42-46, 2004.[13] ILOG CPLEX 9.0 User’s Manual. IBM Co., 2003.[14] S. Abdullah and H. Turabieh, “On the use of multineighborhood structures within a Tabu-based memetic approach to university timetabling problems”, Information Sciences, Vol 191, pp.146-168, 2012.INGE CUCINGE CUChttps://revistascientificas.cuc.edu.co/ingecuc/article/view/7Problema de programación de horarios universitarios vespertinosAlgoritmo de tipo búsqueda tabúMetaheurísticasEvening university timetabling problemAlgorithm of tabu search typeMetaheuristicsAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinosA tabu search algorithm for an evening university timetabling problemArtículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1Textinfo:eu-repo/semantics/articlehttp://purl.org/redcol/resource_type/ARTinfo:eu-repo/semantics/acceptedVersioninfo:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2PublicationORIGINALAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos.pdfAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos.pdfapplication/pdf725896https://repositorio.cuc.edu.co/bitstreams/29cbb6ba-33fa-4927-91fc-9f59a9696b94/download921eebf02871dd3aa30c8d60d5f2e368MD51LICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://repositorio.cuc.edu.co/bitstreams/50af486e-876b-407b-a9c8-25c8a843ab30/download8a4605be74aa9ea9d79846c1fba20a33MD52THUMBNAILAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos.pdf.jpgAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos.pdf.jpgimage/jpeg58858https://repositorio.cuc.edu.co/bitstreams/29ccfed0-7c68-45d5-839c-18831e772732/downloade779520eca466e8dec5bfafa283bd322MD54TEXTAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos.pdf.txtAlgoritmo de tipo búsqueda tabú para un problema de programación de horarios universitarios vespertinos.pdf.txttext/plain28352https://repositorio.cuc.edu.co/bitstreams/f262b71c-f6f2-4f7a-8866-3b95766123f2/download8f3121f83bb46c9e4532bdff8accca30MD5511323/2636oai:repositorio.cuc.edu.co:11323/26362024-09-17 11:08:08.911open.accesshttps://repositorio.cuc.edu.coRepositorio de la Universidad de la Costa CUCrepdigital@cuc.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo=

Publicaciones similares