Mostrar el registro sencillo del ítem

Profesor guíadc.contributor.advisorSoto San Martín, José
Autordc.contributor.authorArancibia Castillo, Ricardo Emmanuel
Profesor colaboradordc.contributor.otherKiwi Krauskopf, Marcos Abraham
Profesor colaboradordc.contributor.otherCorrea Haeussler, José
Profesor colaboradordc.contributor.otherVerdugo Silva, Víctor Ignacio
Fecha ingresodc.date.accessioned2021-12-21T14:33:33Z
Fecha disponibledc.date.available2021-12-21T14:33:33Z
Fecha de publicacióndc.date.issued2021
Identificadordc.identifier.urihttps://repositorio.uchile.cl/handle/2250/183317
Resumendc.description.abstractEl 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
Patrocinadordc.description.sponsorshipANID/CONICYT FONDECYT Regular 1181180, CMM ANID PIA AFB170001, CMM ANID BASAL ACE210010 y CMM ANID BASAL FB210005es_ES
Idiomadc.language.isoeses_ES
Publicadordc.publisherUniversidad de Chilees_ES
Tipo de licenciadc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
Link a Licenciadc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
Palabras clavesdc.subjectProgramación dinámica
Palabras clavesdc.subjectAlgoritmos
Palabras clavesdc.subjectAgendamientos crecientes
Palabras clavesdc.subjectK-Sum lateness
Palabras clavesdc.subjectMaximum lateness
Títulodc.titleAlgoritmos para variantes del problema de minimizar la suma de los k mayores retrasos de trabajos en agendamientos en una máquinaes_ES
Tipo de documentodc.typeTesises_ES
dc.description.versiondc.description.versionVersión original del autores_ES
dcterms.accessRightsdcterms.accessRightsAcceso abiertoes_ES
Catalogadoruchile.catalogadorgmmes_ES
Departamentouchile.departamentoDepartamento de Ingeniería Matemáticaes_ES
Facultaduchile.facultadFacultad de Ciencias Físicas y Matemáticases_ES
uchile.titulacionuchile.titulacionDoble Titulación
uchile.gradoacademicouchile.gradoacademicoMagisteres_ES
uchile.notadetesisuchile.notadetesisTesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadases_ES
uchile.notadetesisuchile.notadetesisMemoria para optar al título de Ingeniero Civil Matemático


Descargar archivo

Icon
Icon

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Attribution-NonCommercial-NoDerivs 3.0 United States
Excepto si se señala otra cosa, la licencia del ítem se describe como Attribution-NonCommercial-NoDerivs 3.0 United States