Biblioteca21.440 documentos en línea

Artículo

A New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90oUn nuevo algoritmo genético de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotación de 90o

Resumen

Dado un conjunto de piezas rectangulares con ancho fijo y con longitud infinita, el problema de strip-packing (SPP) de dos dimensiones, con una rotación de las piezas de 90°, consiste en la colocación ortogonal de todas las piezas en la tira, sin sobreponerlas, a fin de minimizar la altura de la tira usada. Se han propuesto varios algoritmos para resolver este problema, pero los genéticos constituyen uno de los enfoques más populares, debido a su eficacia en la solución en problemas NP-hard. En este trabajo se presentan tres representaciones binarias, una operación crossover clásica y operadores de mutación. Las tres representaciones binarias se comparan en un subconjunto de instancias de benchmarking. La representación R2 supera los resultados obtenidos por la representación R1 y R3. De hecho, se mejoran algunos de los mejores resultados encontrados por los trabajos publicados anteriormente.

INTRODUCCIÓN

El Problema de Empaquetamiento en Tiras (SPP) se deriva de los problemas de corte y empaquetamiento, y es considerado como NP-Hard debido a su dificultad combinatoria [1]. Este problema se encuentra en las industrias productivas, donde la optimización de las materias primas se convierte en beneficios económicos al reducir los costes de producción [2]. El SPP considera dos casos: bidimensional y tridimensional. Aunque los casos tridimensionales suelen ser más atractivos para la comunidad investigadora debido a su practicidad, los casos bidimensionales han logrado avances significativos en los enfoques algorítmicos y en el tamaño de las instancias resueltas, aumentando el número de elementos [3]. En particular, el Problema de Empaquetamiento en Tiras en dos dimensiones (2D-SPP) se define como una región rectangular con una anchura W y una altura infinita, donde todas las piezas rectangulares i ∈ I = {1,2,..., n} con una anchura W y una altura hdefinidas, no deben solaparse y pueden girar 90°. El objetivo de este problema es minimizar la altura H obtenida de la tira posicionando todas las piezas sobre ella [4]. El 2D-SPP ha sido formulado matemáticamente en [5]. El 2D-SPP requiere que se coloquen n rectángulos minimizando la altura de la tira H. Si consideramos la esquina inferior izquierda de la tira como el origen de la región del plano xy, x debe corresponder al ancho de la dirección de la región, y a la dirección de la altura. Además, la ubicación de cada rectángulo en la franja estaría representada por una coordenada (xi, yi) desde la esquina inferior izquierda. El conjunto de coordenadas π = {(xi, yi) ∨ iI} se denomina colocación de I. El 2D-SPP puede formularse como sigue:

minimizar H                        (1)

  • Tipo de documento:
  • Formato:pdf
  • Idioma:Inglés
  • Tamaño:875 Kb

Cómo citar el documento

Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.

Este contenido no est� disponible para su tipo de suscripci�n

Información del documento

  • Titulo:A New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90o
  • Autor:Gatica, Gustavo; Villagrán, Gonzalo; Contreras-Bolton, Carlos; Linfati, Rodrigo; Escobar, John Willmer
  • Tipo:Artículo
  • Año:2016
  • Idioma:Inglés
  • Editor:Pontificia Universidad Javeriana.
  • Materias:Algoritmos (Computadores) Algoritmos (Matemáticas) Algoritmos genéticos Genotipos
  • Descarga:4