Please use this identifier to cite or link to this item: http://repositorioinstitucional.uson.mx/handle/unison/1102
Title: Algoritmo genético para calendarización en un casco especial del flujo de tareas con dos etapas
Authors: CASTRO GARCIA YAIR
BRIZUELA RODRIGUEZ, CARLOS ALBERTO
Issue Date: Dec-2007
Publisher: Universidad de Sonora
Abstract: En este trabajo aplicamos la computación como una herramienta poderosa para resolver problemas en el área de Investigación de Operaciones (IO). Uno de los problemas de gran interés en la IO es el problema de flujo de tareas, conocido en inglés como Flexible Flow Shop problem (FFS), en donde uno de los criterios a optimizar ha sido minimizar los tiempos globales de manufactura de productos, como lo muestra Gupta (1988) en un problema de calendarización con dos etapas. La programación de operaciones y particularmente la optimización del tiempo de secuenciación de las tareas que conllevan los procesos de esas operaciones, es el tema en el que nos enfocamos en este trabajo. Esta no es una tarea fácil si tenemos en cuenta una serie de aspectos como las múltiples soluciones sub-óptimas que puede generar el problema y lo difícil que es llegar a obtener el óptimo global del mismo, como se ve en el trabajo de Sriskandarajah y Sethi (1989), quienes abordan el problema de flujo híbrido de tareas con dos etapas: una máquina en la primera etapa y múltiples máquinas en la segunda etapa, dicho trabajo es importante porque allí se establecen cotas inferiores para diferentes heurísticas. Una adecuada programación de tareas permite el buen funcionamiento de cualquier sistema, manteniendo la eficiencia y el control sobre las operaciones, por lo que en este trabajo se plantea como problema de investigación, encontrar una secuencia óptima de n tareas, de tal forma que el retraso total (T, tardiness) o el tiempo de finalización de todas las tareas (Cmax, makespan) sea el mínimo posible, en un ambiente de flujo de tareas flexible (FFS). En nuestro sistema FFS de interés, las máquinas están configuradas de la forma 1+m , es decir, dos etapas sucesivas de máquinas en donde la primera etapa tiene sólo una máquina y la segunda etapa tiene m máquinas idénticas que trabajan en paralelo. El número de tareas n debe ser mayor al número m de máquinas. El problema planteado se clasifica como NP-difícil (NP-Hard), en base al análisis presentado en (Gupta., 1988). Desde el punto de vista de optimización combinatoria, el problema de flujo de tareas consiste en encontrar una permutación de las n tareas que permita minimizar algún criterio que mida la calidad del calendario. Este es un problema típico de secuenciación de tareas, y para encontrar el calendario óptimo nos apoyamos en los Algoritmos Genéticos (AG), dados a conocer por Holland (1975), padre de dicha heurística.
Description: Tesis de licenciatura en ciencas de la computación
URI: http://www.repositorioinstitucional.uson.mx/handle/unison/1102
ISBN: 18962
Appears in Collections:Tesis de Licenciatura

Files in This Item:
File Description SizeFormat 
castrogarciayairl.pdf5.56 MBAdobe PDFThumbnail
View/Open
Show full item record

Google ScholarTM

Check

Altmetric


This item is licensed under a Creative Commons License Creative Commons