Mostrar el registro sencillo del ítem
Algoritmos para variantes del problema de minimizar la suma de los k mayores retrasos de trabajos en agendamientos en una máquina
Profesor guía | dc.contributor.advisor | Soto San Martín, José | |
Autor | dc.contributor.author | Arancibia Castillo, Ricardo Emmanuel | |
Profesor colaborador | dc.contributor.other | Kiwi Krauskopf, Marcos Abraham | |
Profesor colaborador | dc.contributor.other | Correa Haeussler, José | |
Profesor colaborador | dc.contributor.other | Verdugo Silva, Víctor Ignacio | |
Fecha ingreso | dc.date.accessioned | 2021-12-21T14:33:33Z | |
Fecha disponible | dc.date.available | 2021-12-21T14:33:33Z | |
Fecha de publicación | dc.date.issued | 2021 | |
Identificador | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/183317 | |
Resumen | dc.description.abstract | El problema de minimizar k-sum lateness en una máquina es una generalización de los problemas de minimizar maximum lateness y total lateness, casos que se recuperan cuando k=1 y k=n respectivamente, y consiste en encontrar un agendamiento de n trabajos en una máquina, que minimice la suma de los k mayores lateness. Podemos resolver el problema de minimizar maximum lateness en tiempo polinomial mediante una regla de despacho simple que prioriza los trabajos de menor a mayor deadline, mientras que para resolver el problema de minimizar total lateness se priorizan los trabajos de acuerdo a sus tiempos de proceso, de menor a mayor. A diferencia de los casos particulares anteriores, para el problema general del k-sum lateness mostramos que no existen reglas de despacho simples que permitan encontrar un agendamiento óptimo priorizando los trabajos ni según sus tiempos de proceso ni según sus deadlines. En esta tesis realizamos un estudio robusto del problema de k-sum lateness y presentamos algoritmos polinomiales para tres variantes importantes del problema. Cuando k es una constante fija, mostramos que el problema puede ser resuelto en tiempo O(n^{2k-1}) extendiendo el trabajo de Woeginger para k-sum tardiness. Cuando hay a lo más una cantidad P constante de tiempos de proceso distintos, reformulamos el problema de k-sum lateness como uno de optimización a dos niveles que puede ser resuelto en tiempo O(n^{2P+5}). Finalmente, cuando hay a lo más una cantidad D constante de deadlines distintos, mostramos una serie de resultados estructurales de agendamientos óptimos que nos permiten resolver el problema en tiempo O(n^{3D+1}D). | es_ES |
Patrocinador | dc.description.sponsorship | ANID/CONICYT FONDECYT Regular 1181180, CMM ANID PIA AFB170001, CMM ANID BASAL ACE210010 y CMM ANID BASAL FB210005 | es_ES |
Idioma | dc.language.iso | es | es_ES |
Publicador | dc.publisher | Universidad de Chile | es_ES |
Tipo de licencia | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
Link a Licencia | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
Palabras claves | dc.subject | Programación dinámica | |
Palabras claves | dc.subject | Algoritmos | |
Palabras claves | dc.subject | Agendamientos crecientes | |
Palabras claves | dc.subject | K-Sum lateness | |
Palabras claves | dc.subject | Maximum lateness | |
Título | dc.title | Algoritmos para variantes del problema de minimizar la suma de los k mayores retrasos de trabajos en agendamientos en una máquina | es_ES |
Tipo de documento | dc.type | Tesis | es_ES |
dc.description.version | dc.description.version | Versión original del autor | es_ES |
dcterms.accessRights | dcterms.accessRights | Acceso abierto | es_ES |
Catalogador | uchile.catalogador | gmm | es_ES |
Departamento | uchile.departamento | Departamento de Ingeniería Matemática | es_ES |
Facultad | uchile.facultad | Facultad de Ciencias Físicas y Matemáticas | es_ES |
uchile.titulacion | uchile.titulacion | Doble Titulación | |
uchile.gradoacademico | uchile.gradoacademico | Magister | es_ES |
uchile.notadetesis | uchile.notadetesis | Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas | es_ES |
uchile.notadetesis | uchile.notadetesis | Memoria para optar al título de Ingeniero Civil Matemático |
Descargar archivo
Este ítem aparece en la(s) siguiente(s) colección(ones)
-
Tesis Postgrado
Tesis Postgrado