Show simple item record

Recocido simulado y Hill Climbing con doble vecindad para el problema de calendarización en talleres de manufactura

dc.rights.licensehttp://creativecommons.org/licenses/by-nc/4.0 - Atribución-NoComerciales_MX
dc.contributorFEDERICO ALONSO PECINAes_MX
dc.contributor.authorANGEL RICARDO DIEZ GONZALEZes_MX
dc.contributor.otherdirector - Directores_MX
dc.coverage.spatialMEX - Méxicoes_MX
dc.date2022-01-17
dc.date.accessioned2022-06-08T15:01:29Z
dc.date.available2022-06-08T15:01:29Z
dc.identifier.urihttp://riaa.uaem.mx/handle/20.500.12055/2397
dc.descriptionRESUMEN Uno de los problemas clásicos del área de optimización combinatoria es el Problema de Calendarización para Talleres de Manufactura (del inglés Job shop Scheduling Problem), el cual se puede entender como un proceso de toma de decisiones y asignación de recursos para completar un número de tareas con períodos de tiempo determinados. Actualmente el estudio de este problema sigue vigente, ya que está clasificado como de complejidad NP-Completo y por lo tanto no existen métodos que puedan encontrar la mejor solución con algoritmos determinísticos que presentan prueba de optimalidad en un tiempo polinomial. En esta tesis se propone un algoritmo aproximado de cuatro fases para resolver el problema del Job Shop. Este algoritmo presenta una implementación de Recocido Simulado junto a una Mejora Iterativa de Búsqueda Local ampliada a una Doble Vecindad. Las instancias usadas en la experimentación pertenecen a benchmarks clásicos de la literatura y los resultados fueron comparados con los óptimos conocidos de dichas instancias. Se encontró el óptimo en más de la mitad de las instancias de prueba. ABSTRACT The Job Shop Scheduling Problem is one of the most well-known problems of Combinatorial Optimization, it can be seen as a process of decision-making and resource allocation for the completion of a number of tasks within a certain time. The study of this problem is still relevant today as it has been classified as NP- Complete in complexity and thus there isn’t a method that can find the best solution by means of a deterministic algorithm with optimality proof in a polynomial time. In this thesis we propose a four-step approximate algorithm to solve the Job Shop problem. This algorithm features an implementation of Simulated Annealing along with an Iterative Improvement Local Search expanded to a Double Neighborhood. The instances used in the experimentation belong to classical benchmarks from the literature and the results were compared with the known optima of these instances. The algorithm found the optimum for more than half the instances used as a benchmark.es_MX
dc.formatpdf - Adobe PDFes_MX
dc.languagespa - Españoles_MX
dc.publisherEl autores_MX
dc.rightsopenAccess - Acceso Abiertoes_MX
dc.subject1 - CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRAes_MX
dc.subject.other11 - LÓGICAes_MX
dc.titleRecocido simulado y Hill Climbing con doble vecindad para el problema de calendarización en talleres de manufacturaes_MX
dc.typemasterThesis - Tesis de maestríaes_MX
uaem.unidadFacultad de Contaduría Administración e Informática - Facultad de Contaduría Administración e Informáticaes_MX
uaem.programaMaestría en Optimización y Cómputo Aplicado - Maestría en Optimización y Cómputo Aplicadoes_MX
dc.type.publicationacceptedVersiones_MX
dc.audienceresearchers - Investigadoreses_MX
dc.date.received2022-04-22


Files in this item

Thumbnail

This item appears in the following Collection(s)

  • Colección Tesis Posgrado [2717]
    Se trata de tesis realizadas por estudiantes egresados de programas de posgrado de nuestra institución.

Show simple item record