Entorno de prueba de algoritmos de Bin-Packing tridimensional

Abstract

Se ha diseñado un entorno que permite la aplicación de diversos algoritmos de bin-packing 3-D (empaquetamiento en tres dimensiones, como los bultos que se almacenan en un contenedor) para un conjunto de cajas de tamaños diversos que se ubican en un volumen dado, con algunas restricciones (por ejemplo, sólo cajas en forma de prismas rectangulares). Se da soporte gráfico a los siguientes aspectos: a. Algoritmos de empaquetamiento tanto on-line (que ubican cada nueva caja a medida que van llegando, de un modo rápido y lo más eficiente posible) como off-line (que analizan el mejor empaquetado para un conjunto de cajas previamente conocido) , siempre teniendo como objetivo minimizar la altura del empaquetamiento. b. Se incluiye también una herramienta de visualización tridimensional que permite representar gráficamente el empaquetado y su evolución a medida que avanza el empaquetamiento. c. Se incluiyen herramientas que permitan comparar los resultados de los distintos algoritmos. El proyecto ha sido realizado en un lenguaje de alto nivel como es C++ y para manejar los gráficos OpenGL. La mayor parte de la pantalla está dedicada a la visualización de la simulación, representando una imagen de la FPGA y las tareas hardware que en ella han sido distribuidas por el algoritmo elegido, pudiendo el usuario escoger el tipo de vista, la posición de la cámara, la escala, emplear un zoom o incluso rotar los objetos de la imagen. La aplicación, diseñada para un entorno Windows, necesita de las DLLs BORLNDMM.DLL y CC3250MT.DLL incluidas en el CD de instalación. La resolución de la pantalla ha de ser 1024x768 o superior. Los requisitos hardware de la aplicación incluyen un procesador a 400 MHz o superior y un mínimo 64 Mb de RAM.

[ABSTRACT]

Description: We have designed an environment that allows running multiple bin packing 3D algorithms (packing in a three dimensional space, like the packages that are stored in a container) that work with a set of boxes of different sizes that are placed in a certain volume, with estrictions (for example, the boxes have to be rectangular prism shaped). There is graphics support for the following feaures: a. Bin packing 3D algorithms, both online (that places the boxes on the fly, in a fast manner while trying to be as much efficient as posible) and offline (that search for the best placement of a previously known set of boxes), always trying to minimize the height component. b. There is a 3D visualization tool that shows graphicaly the result of the bin packing 3D algorithms and it´s evolution while that algorithms are running. c. There are tools that allows to compare the results of the several algorithms. This proyect has been coded in a high level programming language (C++) and the graphics have been done with the OpenGL graphics library. The greater part of the screen is used to show the simulation as an image that represents the FPGA and the RFU operations that have been placed on it by the choosed algorithm. User can choose the type of view, as well as the camera position, the scale, the use of the zoom and it’s allowed to rotate the image objects. This application, that runs under Windows, need the following DLLs: BORLNDMM.DLL and CC3250MT.DLL. These DLLs are included in the installation CD. The screen resolution must be of 1024x768 or higher. The hardware requirements of the application include a 400 MHz processor or higher and 64 Mb of RAM.