dc.rights.license | http://creativecommons.org/licenses/by-nc/4.0 - Atribución-NoComercial | es_MX |
dc.contributor | FEDERICO ALONSO PECINA | es_MX |
dc.contributor.author | ANGEL RICARDO DIEZ GONZALEZ | es_MX |
dc.contributor.other | director - Director | es_MX |
dc.coverage.spatial | MEX - México | es_MX |
dc.date | 2022-03-31 | |
dc.date.accessioned | 2022-05-04T17:15:47Z | |
dc.date.available | 2022-05-04T17:15:47Z | |
dc.identifier.uri | http://riaa.uaem.mx/handle/20.500.12055/2336 | |
dc.description | RESUMEN
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. | es_MX |
dc.description | 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.format | pdf - Adobe PDF | es_MX |
dc.language | spa - Español | es_MX |
dc.publisher | El autor | es_MX |
dc.rights | openAccess - Acceso Abierto | es_MX |
dc.subject | 1 - CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA | es_MX |
dc.subject.other | 11 - LÓGICA | es_MX |
dc.subject.other | 12 - MATEMÁTICAS | es_MX |
dc.title | Recocido simulado y Hill Climbing con doble vecindad para el problema de calendarización en talleres de manufactura | es_MX |
dc.type | masterThesis - Tesis de maestría | es_MX |
uaem.unidad | Facultad de Contaduría Administración e Informática - Facultad de Contaduría Administración e Informática | es_MX |
uaem.programa | Maestría en Optimización y Cómputo Aplicado - Maestría en Optimización y Cómputo Aplicado | es_MX |
dc.type.publication | acceptedVersion | es_MX |
dc.audience | researchers - Investigadores | es_MX |
dc.date.received | 2022-04-26 | |