Asignacion cuadratica

INSTITUTO TECNOLOGICO DE PACHUCA

UNIDAD 2, DISTRIBUCIÓN DE INSTALACIONES

PRESENTAN:
RAMOS CASTAÑÓN JACOBO FELIPE
TERRAZAS CARBAJAL SANDRA
MARTINEZ ORTIZ JOHNATHAN DAVID

NOMBRE DE LA ASIGNATURA:
PLANEACIÓN Y DISEÑO DE INSTALACIONES

CARRERA:
INGENIERÍA INDUSTRIAL
SÉPTIMO SEMESTRE

PACHUCA DE SOTO A 22 DE FEBRERO DEL 2011

TEMARIO:2. DISTRIBUCIÓN DE INSTALACIONES

3.1 ELEMENTOS CONCEPTUALES

3.2.1 DISTRIBUCIÓN DE PLANTA

2.1.1. METODO S.L.P. (SISTEMATIC LAYOUT PLANNING) O (PLANEACION SISTEMATICA DE LA DISTRIBUCION EN PLANTA).

2.1.2. ASIGNACIÓN CUADRATICA (QAP – QUADRATIC ASSIGNMENT PROBLEM)

2.1.3. ALMACENES, OFICINAS, SU LOCALIZACIÓN Y DISTRIBUCIÓN DENTRO DE LAORGANIZACIÓN

2.1.4. MODELOS AUTOMATIZADOS PARA GENERACIÓN DE ALTERNATIVAS

2.1.5. SERVICIOS GENERALES Y DE SOPORTE

2.1.2. Algoritmo Evolutivo Paralelo para problemas de Asignación Cuadrática – QAP

INTRODUCCIÓN
El Problema de Asignación Cuadrática (QAP – Quadratic Assignment Problem) es un problema clásico de optimizacióncombinatorio, en el cual se encuentra un vasto número de problemas de diseño y de distribución de recursos en diferentes campos, donde la decisión a tomar es una asignación de elementos de un conjunto en otro. El QAP es considerado como un problema complejo y dificultoso de resolver y puede establecerse como un conjunto de n elementos distintos que deben ser localizados (asignados) en nlocalidades distintas de forma óptima [1][2]. Aunque se han propuesto numerosas heurísticas y procedimientos, los Algoritmos Evolutivos (AEs) han emergido como una clase de búsqueda aleatoria de varios puntos concurrentemente sobre un espacio de soluciones factibles; tales algoritmos son inspirados por mecanismos de la evolución natural y mecanismos genéticos introducidos por J. Holland en los años 70 [3].Experimentos reales sobre algoritmos evolutivos para QAP se iniciaron a principios de los 90’s; David M. Tate y Alice E. Smith (1.992) establecen mecanismos de selección y reproducción (cruce) así como una posible codificación para problemas de Asignación Cuadrática [4]. Para el año 1.995 B. R. Sarker y un grupo de colaboradores implementan un algoritmo secuencial: Depth – First InsertionHeuristic (DIH) [5]; para el problema de retrocesos (backtracking) de trabajos en la localización de una máquina en una línea unidimensional de flujo. Otra manera de tratar a los Algoritmos Genéticos es analizando su paralelismo intrínseco, tal como lo hizo G. Larrazábal en el año 1.996, cuando plantea un Algoritmo Genético Grano Grueso para un problema de alta dimensionalidad [6]. Más tarde, PatriceRoger Calégari (1.999) en su trabajo de tesis doctoral [2], muestra la paralelización eficiente de Algoritmos Evolutivos. Recientemente fue tratado un problema cuadrático de asignación de facilidades por N. Maneiro (2.001) empleando un algoritmo evolutivo simple [1]; el cual consistió en localizar un grupo de m máquinas de tal manera que se minimice el retroceso (backtracking) dentro de una línea deflujo generalizado.
Este trabajo trata la paralelización de un algoritmo evolutivo desarrollado con tecnología de programación orientada a objetos, el cual está enfocado a resolver problemas de asignación cuadrática de facilidades de alta dimensionalidad; el mismo se inicia con una exposición breve de los Problemas de Asignación Cuadrática en donde se detalla el problema de QAP tratado. Luego seexplica el funcionamiento de los Algoritmos Evolutivos y enseguida se describe el Algoritmo Evolutivo Propuesto. Más adelante se habla de Paralelismo y de la Paralelización del Algoritmo Evolutivo; para finalizar con la exposición de los resultados en dos partes: Resultados de Corrida Secuencial y Resultados de Corrida Paralela.

ALGORITMO EVOLUTIVO PARA PROBLEMAS QAP
Problemas de Asignación...