Evaluation of parallel search for a large scheduling problem

"El problema de planificar los exámenes finales de una universidad puede categorizarse naturalmente como un problema de satisfacción de restricciones. Planificar es un problema abordado extensamente por la comunidad de la programación orientada a restricciones. Sin embargo, debido al tamaño que...

Full description

Autores:
Agudelo Cruz, Daniel Esteban
Ramos Correa, Juan Felipe
Tipo de recurso:
Trabajo de grado de pregrado
Fecha de publicación:
2020
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
spa
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/49302
Acceso en línea:
http://hdl.handle.net/1992/49302
Palabra clave:
Programación paralela (Computadores electrónicos)
Restricciones (Inteligencia artificial)
Método de descomposición
Optimización matemática
Ingeniería
Rights
openAccess
License
http://creativecommons.org/licenses/by-nc-nd/4.0/
id UNIANDES2_a130fcad3355ab845b4cefd92aebc825
oai_identifier_str oai:repositorio.uniandes.edu.co:1992/49302
network_acronym_str UNIANDES2
network_name_str Séneca: repositorio Uniandes
repository_id_str
spelling Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.http://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Cardozo Álvarez, Nicolásvirtual::12638-1Agudelo Cruz, Daniel Esteban850f7397-683f-4c06-996c-90c39221d696500Ramos Correa, Juan Felipe3be3b881-3446-4103-a76f-8c8340e071625002021-02-18T12:47:55Z2021-02-18T12:47:55Z2020http://hdl.handle.net/1992/49302u833207.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/"El problema de planificar los exámenes finales de una universidad puede categorizarse naturalmente como un problema de satisfacción de restricciones. Planificar es un problema abordado extensamente por la comunidad de la programación orientada a restricciones. Sin embargo, debido al tamaño que representa el problema aplicado a los examenes finales de una universidad, las técnicas estándar resultan insatisfactorias al intentar proveer una solución, dado su tiempo de ejecución. En este documento presentamos un algoritmo de descomposición en paralelo, que extiende el solver OscaR. Evaluamos el desempeño del algoritmo y lo contrastamos con el del algoritmo existente en OscaR. Nuestro problema de clasificación involucra más de 1100 variables, sin embargo las pruebas con un conjunto de 320, ya empiezan a mostrar una mejora super lineal en la etapa de descomposición." -- Tomado del formato de documento de grado"The final exam scheduling problem can be naturally characterized as a constraint satisfaction problem, defining the relations between exams and available resource as constraints. Such problem, has been widely studied in the constraint programming community. However, due to the increasing size of the problem, and the complexity of the relations between constraints, applying standard constraint programming solutions is unsatisfactory to provide an answer to large exam scheduling problems. In this paper we present a parallel problem decomposition algorithm, that extends the OscaR solver. We evaluate the performance of the proposed algorithm, in contrast to the existing algorithm in OscaR. Our scheduling problem considers over 1100 variables. The evaluation results for 321 variables, show a superlinear speedup on the problem decomposition phase." -- Tomado del formato de documento de gradoIngeniero de Sistemas y ComputaciónPregrado47 hojasapplication/pdfspaUniandesIngeniería de Sistemas y ComputaciónFacultad de IngenieríaDepartamento de Ingeniería de Sistemas y Computacióninstname:Universidad de los Andesreponame:Repositorio Institucional SénecaEvaluation of parallel search for a large scheduling problemTrabajo de grado - Pregradoinfo:eu-repo/semantics/bachelorThesishttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/TPProgramación paralela (Computadores electrónicos)Restricciones (Inteligencia artificial)Método de descomposiciónOptimización matemáticaIngenieríaPublicationhttps://scholar.google.es/citations?user=3iTzjQsAAAAJvirtual::12638-10000-0002-1094-9952virtual::12638-1a77ff528-fc33-44d6-9022-814f81ef407avirtual::12638-1a77ff528-fc33-44d6-9022-814f81ef407avirtual::12638-1ORIGINALu833207.pdfapplication/pdf734038https://repositorio.uniandes.edu.co/bitstreams/0cd7d451-c9d7-4ec2-af21-423bda314240/download2d727ca2b5cf0b163796eb43bafa1d5eMD51TEXTu833207.pdf.txtu833207.pdf.txtExtracted texttext/plain47782https://repositorio.uniandes.edu.co/bitstreams/faa93fb0-78e8-49d4-8c6b-c8235ac25e82/download3b4ee57d3cbce23a09ad43583b451886MD54THUMBNAILu833207.pdf.jpgu833207.pdf.jpgIM Thumbnailimage/jpeg736https://repositorio.uniandes.edu.co/bitstreams/2f402188-a628-434e-a3ba-900d6e89f220/downloadfaceea5cdffea9cc9e836352d4544118MD551992/49302oai:repositorio.uniandes.edu.co:1992/493022024-03-13 14:44:15.569http://creativecommons.org/licenses/by-nc-nd/4.0/open.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co
dc.title.es_CO.fl_str_mv Evaluation of parallel search for a large scheduling problem
title Evaluation of parallel search for a large scheduling problem
spellingShingle Evaluation of parallel search for a large scheduling problem
Programación paralela (Computadores electrónicos)
Restricciones (Inteligencia artificial)
Método de descomposición
Optimización matemática
Ingeniería
title_short Evaluation of parallel search for a large scheduling problem
title_full Evaluation of parallel search for a large scheduling problem
title_fullStr Evaluation of parallel search for a large scheduling problem
title_full_unstemmed Evaluation of parallel search for a large scheduling problem
title_sort Evaluation of parallel search for a large scheduling problem
dc.creator.fl_str_mv Agudelo Cruz, Daniel Esteban
Ramos Correa, Juan Felipe
dc.contributor.advisor.none.fl_str_mv Cardozo Álvarez, Nicolás
dc.contributor.author.none.fl_str_mv Agudelo Cruz, Daniel Esteban
Ramos Correa, Juan Felipe
dc.subject.armarc.es_CO.fl_str_mv Programación paralela (Computadores electrónicos)
Restricciones (Inteligencia artificial)
Método de descomposición
Optimización matemática
topic Programación paralela (Computadores electrónicos)
Restricciones (Inteligencia artificial)
Método de descomposición
Optimización matemática
Ingeniería
dc.subject.themes.none.fl_str_mv Ingeniería
description "El problema de planificar los exámenes finales de una universidad puede categorizarse naturalmente como un problema de satisfacción de restricciones. Planificar es un problema abordado extensamente por la comunidad de la programación orientada a restricciones. Sin embargo, debido al tamaño que representa el problema aplicado a los examenes finales de una universidad, las técnicas estándar resultan insatisfactorias al intentar proveer una solución, dado su tiempo de ejecución. En este documento presentamos un algoritmo de descomposición en paralelo, que extiende el solver OscaR. Evaluamos el desempeño del algoritmo y lo contrastamos con el del algoritmo existente en OscaR. Nuestro problema de clasificación involucra más de 1100 variables, sin embargo las pruebas con un conjunto de 320, ya empiezan a mostrar una mejora super lineal en la etapa de descomposición." -- Tomado del formato de documento de grado
publishDate 2020
dc.date.issued.none.fl_str_mv 2020
dc.date.accessioned.none.fl_str_mv 2021-02-18T12:47:55Z
dc.date.available.none.fl_str_mv 2021-02-18T12:47:55Z
dc.type.spa.fl_str_mv Trabajo de grado - Pregrado
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/bachelorThesis
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TP
format http://purl.org/coar/resource_type/c_7a1f
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/1992/49302
dc.identifier.pdf.none.fl_str_mv u833207.pdf
dc.identifier.instname.spa.fl_str_mv instname:Universidad de los Andes
dc.identifier.reponame.spa.fl_str_mv reponame:Repositorio Institucional Séneca
dc.identifier.repourl.spa.fl_str_mv repourl:https://repositorio.uniandes.edu.co/
url http://hdl.handle.net/1992/49302
identifier_str_mv u833207.pdf
instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
repourl:https://repositorio.uniandes.edu.co/
dc.language.iso.es_CO.fl_str_mv spa
language spa
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/4.0/
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
rights_invalid_str_mv http://creativecommons.org/licenses/by-nc-nd/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.es_CO.fl_str_mv 47 hojas
dc.format.mimetype.es_CO.fl_str_mv application/pdf
dc.publisher.es_CO.fl_str_mv Uniandes
dc.publisher.program.es_CO.fl_str_mv Ingeniería de Sistemas y Computación
dc.publisher.faculty.es_CO.fl_str_mv Facultad de Ingeniería
dc.publisher.department.es_CO.fl_str_mv Departamento de Ingeniería de Sistemas y Computación
dc.source.es_CO.fl_str_mv instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
instname_str Universidad de los Andes
institution Universidad de los Andes
reponame_str Repositorio Institucional Séneca
collection Repositorio Institucional Séneca
bitstream.url.fl_str_mv https://repositorio.uniandes.edu.co/bitstreams/0cd7d451-c9d7-4ec2-af21-423bda314240/download
https://repositorio.uniandes.edu.co/bitstreams/faa93fb0-78e8-49d4-8c6b-c8235ac25e82/download
https://repositorio.uniandes.edu.co/bitstreams/2f402188-a628-434e-a3ba-900d6e89f220/download
bitstream.checksum.fl_str_mv 2d727ca2b5cf0b163796eb43bafa1d5e
3b4ee57d3cbce23a09ad43583b451886
faceea5cdffea9cc9e836352d4544118
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional Séneca
repository.mail.fl_str_mv adminrepositorio@uniandes.edu.co
_version_ 1812134000379035648

Publicaciones similares