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 hi definidas, 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) ∨ i ∈ I} se denomina colocación de I. El 2D-SPP puede formularse como sigue:
minimizar H (1)
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.
Artículo:
Evaluación de enfoques de integración entre los sistemas ERP e BPM
Artículo:
Análisis empírico del efecto del tamaño de la información de entrada en el desempeño de herramientas de compresión sin pérdida
Artículo:
Desarrollo de aplicaciones móviles bajo la plataforma de Iphone
Video:
V. Completa. La mejor ciberseguridad es la prevención. Silvia Barrera, experta en ciberseguridad
Artículo:
Plataforma de descubrimiento de servicios para ambientes de computación ubicua basada en preferencias de usuario, especificaciones de dispositivos y contexto de entrega
Informe, reporte:
El carbón como recurso : una visión general del carbón
Libro:
Manual del artesano electroquímico
Capítulo de libro:
Petróleo y gas natural
Informe, reporte:
Libro blanco para la minimización de residuos y emisiones en procesos de recubrimientos electrolíticos