Please use this identifier to cite or link to this item:
http://cimat.repositorioinstitucional.mx/jspui/handle/1008/1037
Metaheurísticas aplicadas al Problema de Planificación para Producción Tipo Taller | |
OSCAR HERNANDEZ CONSTANTINO | |
Acceso Abierto | |
Atribución-NoComercial | |
MATEMÁTICAS INDUSTRIALES | |
El problema de planificación para producción tipo taller (JSSP, Job Shop Scheduling Problem) consiste en determinar la forma en que se deben utilizar un conjunto de recursos para realizar un conjunto de trabajos de forma que se minimice el tiempo requerido para procesar los mismos respetando a su vez un conjunto de restricciones, entre las que se incluyen restricciones relativas al orden en que se procesan las operaciones de los trabajos. El JSSP es un problema NP-Difícil que ha sido estudiado desde hace varias décadas y para el cual se han propuesto múltiples estrategias de resolución. En este trabajo se realizó un análisis del estado del arte y se desarrolló un optimizador que incluyó algunas de las mejores componentes publicadas hasta la fecha, así como nuevas componentes diseñadas en esta tesis. En concreto, se desarrolló un algoritmo memético que incorporó un mecanismo de intensificación basado en Búsqueda Tabú que ha ofrecido muy buenos resultados al ser integrado en otros algoritmos híbridos. Como novedades de la tesis cabe destacar el desarrollo de un nuevo operador de cruce que se diseñó de forma específica para el problema tratado, así como la inclusión de un mecanismo de gestión de diversidad que ha obtenido resultados muy promisorios en otros problemas. Además, se desarrolló un nuevo mecanismo de gestión de diversidad, cuyo propósito es acelerar el proceso de búsqueda para lograr obtener resultados de alta calidad en menores tiempos de ejecución. Se propuso también una nueva medida de similitud entre soluciones y se verificó experimentalmente que al aplicarla en el mecanismo de gestión de diversidad previamente mencionado, se logran mejores resultados que con otras medidas que han sido utilizadas en otros algoritmos del estado del arte. Debido a la complejidad del problema, en las instancias más grandes se requiere una gran cantidad de recursos computacionales para obtener soluciones de alta calidad, por lo cual se propone la paralelización del método propuesto, así como de dos algoritmos del estado del arte para el JSSP. En particular, con el método propuesto se logró superar el mejor resultado conocido hasta la fecha en 31 instancias, logrando obtener soluciones óptimas al menos en dos de ellas. Este logro se ha verificado utilizando plataformas dedicadas a este problema en específico, y en las cuales el método desarrollado en esta tesis está listado actualmente como el método a batir. | |
10-12-2019 | |
Tesis de maestría | |
OTRAS | |
Versión aceptada | |
acceptedVersion - Versión aceptada | |
Appears in Collections: | Tesis del CIMAT |
Upload archives
File | Description | Size | Format | |
---|---|---|---|---|
TE 762.pdf | 1.72 MB | Adobe PDF | View/Open |