info:eu-repo/semantics/masterThesis
Metaheurísticas aplicadas al Problema de Planificación para Producción Tipo Taller
Autor
OSCAR HERNANDEZ CONSTANTINO
Institución
Resumen
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.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Compendio de innovaciones socioambientales en la frontera sur de México
Adriana Quiroga -
Caminar el cafetal: perspectivas socioambientales del café y su gente
Eduardo Bello Baltazar; Lorena Soto_Pinto; Graciela Huerta_Palacios; Jaime Gomez -
Cambio social y agrícola en territorios campesinos. Respuestas locales al régimen neoliberal en la frontera sur de México
Luis Enrique García Barrios; Eduardo Bello Baltazar; Manuel Roberto Parra Vázquez