Optimización de la distribución del trabajo mediante el algoritmo bin packing unidimensional_3.Implementación (1)

3. Implementación del algoritmo de embalaje de contenedores

Se requiere un entorno de desarrollo para ingresar la lista de elementos y restricciones, implementar el algoritmo y verificar los resultados. Hay varios entornos de desarrollo como Excel VBA, Python y R. Entre ellos, Excel VBA no tiene una biblioteca abierta, por lo que debe escribir la mayor parte del código fuente usted mismo. Python y R pueden implementar el algoritmo de empaquetado en contenedores directamente o usar un paquete ya proporcionado. Aquí, veré cómo usar la herramienta que implementa el algoritmo yo mismo con Excel VBA y el paquete provisto en Python.

3.1. Herramienta basada en Excel VBA

Una herramienta o lenguaje que implementa un algoritmo generalmente recibe un archivo de datos como entrada por separado del código fuente del programa. Excel VBA tiene la característica de poder administrar el código fuente y los datos del programa en un archivo y administrarlos por separado. Aquí, el código fuente del programa y los datos se administran en un archivo.

A continuación, se presentará brevemente la configuración y el código fuente de la herramienta que administra la lista de artículos introduciéndolos en una hoja de Excel e implementa el algoritmo bin packing unidimensional con VBA. El código fuente completo se proporciona como un apéndice. https://github.com/DAToolset/1D-bin-packing también se puede comprobar.

**Nota: este artículo no cubre el concepto o la sintaxis de Excel VBA, pero se escribirá en detalle en un artículo separado en el futuro.

La configuración general de la herramienta se muestra en la siguiente figura. Ingrese los datos en la hoja "Ejecutar", configure las opciones y haga clic en el botón "Ejecutar embalaje de contenedores" para verificar el resultado de la ejecución.

Los detalles de las cuatro áreas en la figura anterior se explican en la siguiente tabla de contenido.

3.1.1. Configuración del material de entrada

En la lista de artículos, ingrese Nombre y Tamaño en el siguiente formato.

Aquí, el nombre del elemento del contenedor es un nombre para identificar el tipo de un elemento, y puede designarse adecuadamente de acuerdo con el tipo de elemento. Por ejemplo:

• Si el elemento es una tabla de base de datos, el nombre de la tabla
• Si el elemento es un trabajo, el nombre del trabajo
• Además, también es posible un nombre adecuado para identificar cada artículo (número de pedido, etc.)

Tenga en cuenta que no debe haber nombres duplicados en la lista de elementos. Esto se debe a que, aunque el tamaño sea el mismo, es necesario saber que son objetos diferentes para determinar qué objeto llenar en el contenedor.

En Tamaño, ingrese el tamaño de cada artículo. Para el tamaño, se puede usar el número de filas y bytes en el caso de una tabla, y en el caso de un trabajo, se puede ingresar el tiempo de ejecución en minutos o segundos. El tiempo requerido debe verificarse en el registro de ejecución del trabajo, pero se recomienda calcular y utilizar el valor promedio excluyendo los valores máximo y mínimo entre los últimos 5 o más tiempos requeridos.

Si necesita varios conjuntos de datos, puede copiar e ingresar la hoja "Ejecutar". El nombre de la hoja puede ser cualquier nombre, Es bueno especificarlo en forma de para poder distinguirlo de otras hojas. Por ejemplo, designe "Run_Org" como se muestra en la siguiente figura.

Bin Packing se puede ejecutar creando múltiples conjuntos de datos y configurando diferentes datos o diferentes opciones en cada hoja de conjunto de datos. La hoja en la que se muestra el resultado de la ejecución no se crea para cada conjunto de datos, sino que se utiliza de forma permanente. Si desea conservar los resultados de cada conjunto de datos, puede guardar el archivo de Excel con un nombre diferente y crear un archivo separado.

3.1.2. Configuración de opciones

El tamaño máximo del contenedor, que es una restricción, y si ordenar la columna de referencia en orden descendente se ingresan en el siguiente formato.

Max Bin Size es el tamaño máximo que se asignará a un contenedor. En otras palabras, cuando se llenan varios artículos en un contenedor, existe una restricción en la suma de los tamaños de los artículos.

La columna estándar Tamaño de artículo es una columna que especifica qué valor usar cuando hay varios valores de tamaño en un artículo de contenedor. Por ejemplo, suponga que está configurado para que se puedan ingresar varios tamaños en un artículo de la siguiente manera.

Las columnas que se pueden usar como valores de tamaño son C a I. Ingrese el nombre de la columna para seleccionar qué columna usar como el valor de entrada de tamaño entre ellos. Para simular creando un valor aleatorio en Tamaño, copie el valor generado por la fórmula en la columna J (Tamaño aleatorio), péguelo como un valor en la columna I (Simulación) y luego ejecútelo designando la columna de referencia como I . . La razón por la que no debe especificar la columna J es porque se usa una fórmula en la columna J y se crea un nuevo valor cada vez que se calcula, por lo que es imposible saber qué valor se usó como valor de entrada.

Si se selecciona (marca) la opción de ordenación descendente del tamaño del artículo, primero, el tamaño del artículo se ordena en orden descendente y se aplica el algoritmo de embalaje en contenedores.

3.1.3. Ejecutar embalaje de contenedores

Cuando se complete la configuración de datos de entrada y la configuración de opciones, haga clic en el botón "Ejecutar BinPacking" para ejecutar.

Si hay un duplicado en "Nombre del elemento del contenedor" al ejecutar, puede ocurrir un error. Verifique y elimine el duplicado y ejecute.

3.1.4. Comprobar el resultado de la ejecución

El resultado de la ejecución consta de 5 hojas. El resumen general se verifica en la hoja de resumen de resultados, que recopila los resultados de ejecución de cada algoritmo, y los resultados detallados de cada algoritmo se verifican en cada hoja.

• Resumen de resultados: una hoja en la que se pueden ver de un vistazo los resultados de ejecutar cada algoritmo
• Next Fit: la hoja de resultados de ejecutar el algoritmo Next Fit
• First Fit: la hoja de resultados de ejecutar el algoritmo First Fit
• Peor ajuste: la hoja de resultados de ejecutar el algoritmo de peor ajuste
• Best Fit: la hoja de resultados de ejecutar el algoritmo Best Fit

El contenido de la hoja de resumen de resultados es el siguiente.

En la parte superior se muestra información de referencia para el tamaño máximo de contenedor establecido en las opciones, y en la parte inferior se muestra un gráfico de los resultados de ejecutar cada uno de los cuatro algoritmos.

La composición de la información que se muestra en la hoja de resultados después de ejecutar cada algoritmo es la siguiente.

Artículo	Contenido
① Lista de resultados	Como resultado de ejecutar el algoritmo de empaque en contenedores, puede verificar qué artículos se llenan en qué contenedores. Aquí, el nombre del contenedor se crea con la regla de "Bin_" + número de secuencia (5 dígitos) en el proceso de procesamiento del programa.
② Total de contenedores	Esta es una tabla dinámica para calcular la suma de los tamaños de artículos en unidades bin. <④ Bin Sum Chart> se crea con esta tabla dinámica como fuente de datos.
③ Información de ejecución	Muestra el tiempo necesario para procesar el algoritmo, el total del espacio restante en todos los contenedores, el espacio total y la información de ineficiencia del espacio. La ineficiencia del espacio se calcula como (Suma total del espacio residual del contenedor)/(Suma total del espacio).
④ Gráfico de total de contenedores	Esta es una visualización de <② Bin Sum Pivot Table> como un gráfico de barras verticales.

▼ Resultados de ejecución de ajuste siguiente

▼ Resultados de la ejecución del primer ajuste

▼ Resultados de ejecución de peor ajuste

▼ Resultados de ejecución de mejor ajuste

3.1.5. Configuración de código VBA

Se describe brevemente el código fuente que implementa Bin Packing con VBA. La composición general del Proyecto VBA es la siguiente.

• Sheet (interfaz de usuario de Excel) administra la lista de datos de entrada y muestra la entrada y salida del resultado del procesamiento del algoritmo.
• Un módulo es responsable de manejar y controlar todo el proceso de procesamiento, creando instancias de clases y funciones comunes.
• La clase es responsable de funciones como la carga de datos de entrada en la memoria, la implementación de algoritmos y la salida de datos de resultados.

El propósito de los elementos detallados es el siguiente.

• Sábana
  • Cada hoja: datos de entrada/configuración de opciones, salida de resultados de ejecución
• módulo
  • modControl: administra todo el proceso de objetivación de una clase, carga de datos de entrada, implementación de cada algoritmo de empaque de contenedores y salida de resultados
  • modFactory: Administrar instanciación de clases
    • La clase de VBA no puede especificar el parámetro de entrada del constructor, por lo que está configurada para crear un objeto utilizando el patrón de fábrica.
  • modUtil: Administre funciones como el registro y la configuración del formato de la cadena de tiempo requerida
    • Aquí, Logging no deja un archivo, pero está configurado para que los mensajes de registro se puedan verificar en el depurador con OutputDebugString entre las API de Windows.
    • El depurador recomienda usar DebugView
• clase
  • CBin: Clase de 1 contenedor
    • Métodos principales: AddBinItem, IsAbleToAdd
  • CBinItem: Clase de 1 elemento que se colocará en la papelera
    • Es decir, una clase correspondiente a una línea de datos de entrada.
    • Método principal: CompareTo
  • CBinItemCollection: una clase de colección que administra una lista de varios BinItems.
    • Métodos principales: Añadir, Ordenar, ObtenerCadena
  • CPacker: una clase que administra una lista de contenedores como una colección.
    • Implemente un algoritmo que llene los datos de entrada en un lugar apropiado entre la lista de contenedores existente o cree un nuevo contenedor para llenarlo
    • Métodos principales: DoPacking, Add, GetNewBin, GetBinNextFit, GetBinFirstBit, GetBinWorstFit, GetBinBestFit, PackToBin, DoOutput, GetRemainSizeSum
  • CTimer: una clase para medir el tiempo empleado
    • Usando la API de Windows QueryPerformanceCounter, QueryPerformanceFrequency
    • Métodos principales: StartCounter, TimeElasped

Para aplicar correctamente el concepto de programación orientada a objetos, es estándar exponer propiedades públicas compuestas por Getter/Setter sin variables miembro públicas en la clase. Sin embargo, en esta herramienta, las propiedades públicas no se utilizan por conveniencia de implementación. Sin embargo, las variables miembro, las funciones y los procedimientos a los que se puede acceder desde el exterior se declaran públicos y los objetos a los que se accede desde el exterior se declaran privados.

La relación entre las clases definidas en el código fuente de VBA se expresa brevemente como un diagrama de clases UML de la siguiente manera.

La relación entre clases en el diagrama de clases anterior es una relación. Es decir, en la relación de composición definida entre las dos clases, el rombo lleno (♦) es el contenedor.

 De derecha a izquierda, se puede ver que la clase baja está conectada con la clase alta. La clase CBinItem administra un dato de entrada y la clase CBinItemCollection administra todos los datos de entrada como una colección de CBinItems. La clase CBin administra los objetos bin individuales y administra la lista de elementos llenados en cada bin como un objeto de la clase CBinItemCollection. La clase CPacker implementa el algoritmo y administra todo el objeto Bin de resultados como una colección de la clase CBin. Cada clase tiene una relación de composición, por lo que cuando se elimina el objeto contenedor, se eliminan todos los subobjetos. La clase CTimer se usa en la clase CPacker para medir el tiempo de ejecución del algoritmo.

Aquí, la clase CBinItemCollection se usa para administrar todos los datos de entrada y también para administrar la lista de elementos llenados en cada contenedor. Por ejemplo, suponiendo que 100 elementos se rellenan con 10 elementos en 10 bandejas, el objeto que gestiona los 100 elementos también es del tipo de clase CBinItemCollection y el objeto que gestiona 10 elementos rellenados en cada bandeja también es del tipo de clase CBinItemCollection. ser - estar.

Consulte el apéndice para obtener el código fuente de cada clase y el pseudocódigo de modControl, un módulo que controla todo el proceso de carga de datos de entrada, ejecución de algoritmos y salida de datos de resultados, es el siguiente.

Public Sub RunBinPacking()
    입력자료를 읽어들여 CBinItemCollection type의 oInputItemCol 변수에 적재
    입력자료의 정렬 실행을 선택했으면 oInputItemCol 내림차순 정렬
    각 알고리즘의 실행결과를 담을 변수 선언
    각 변수에 최대 Bin 크기와 PackingType을 설정하여 개체 생성
    각 변수에 입력자료 채우기
    결과출력
    각 변수 메모리에서 삭제하여 정리
End Sub

---

En el próximo artículo, veremos el código fuente implementado usando el paquete Python Bin Packing y el resultado de la ejecución.

---

<< Lista de artículos relacionados >>

• Optimización de la distribución del trabajo utilizando un algoritmo de empaque de contenedores unidimensional_1.Descripción general
• Optimización de la distribución del trabajo mediante bin packing algorítmico unidimensional_2.Algoritmo (1)
• Optimización de la distribución del trabajo utilizando bin packing unidimensional algoritmo_2.Algoritmo(2)
• Optimización de la distribución del trabajo mediante el algoritmo bin packing unidimensional_3.Implementación (1)
• Optimización de la distribución del trabajo mediante el algoritmo bin packing unidimensional_3.Implementación (2)
• Optimización de la distribución del trabajo utilizando un algoritmo de empaque de contenedores unidimensional_4.Adjunto
• Cambios recientes de la herramienta de embalaje de contenedores unidimensionales (al 21 de marzo de 2021)
• Herramienta de optimización de la distribución del trabajo utilizando un algoritmo de empaque de contenedores unidimensional. Contenido completo, Descargar