Rutina para optimizar cortes. Versión 2.0

Probablemente la solución al anterior fracaso sea empezar a valorar si, en el momento de poner el último elemento de la agrupación, es la decisión correcta. ¿Y si ésa última pieza que cabe en la agrupación no hubiera existido? ¿Qué agrupación se formaría? ¿El retal es menor?

Pero antes, algunas definiciones imprescindibles:

Desperdicio

Supongamos que la suma de las longitudes de todas las piezas es bastante menor que la suma de todas las barras consumidas. A la diferencia le podemos llamar desperdicio. No se puede hacer desaparecer todo el desperdicio, hay una parte que no podremos reducir nada.

Desperdicio inevitable y piezas solitarias

Hay una serie de piezas, que serán las más grandes, que deben ocupar una barra cada una. Ocurrirá con todas las piezas cuya diferencia con la dimensión de barra sea menor que el tamaño de la piea más pequeña. No podremos encontrar ninguna pieza que se pueda sacar de una barra que usemos para cada una de estas piezas. Serán piezas solitarias en su barra. Por éso, esta parte del desperdicio es inevitable.

Así, las piezas solitarias no tienen mejor solución, no tiene sentido andar probando a combinarlas. Cada pieza solitaria consumirá una barra y hay que resignarse. Se pueden sacar del problema.

Desperdicio evitable y piezas combinables

El desperdicio evitable será la diferencia que hay entre la suma de las longitudes de todas las piezas combinables y las barras que se consumen para obtener las piezas combinables. De las piezas solitarias nos olvidamos de momento, las sacamos de la optimización

Desperdicio compensado, guardando piezas pequeñas para el final

Las piezas pequeñas son más versátiles, porque caben en mas huecos y se pueden combinar de más maneras.

Por ese motivo, al organizar la primera agrupación en la que se va a cortar la primera barra, no debería buscar la solución que da el retal más pequeño, si es a costa de consumir demasiadas piezas pequeñas.Porque si se utilizan todas las piezas pequeñas en las primeras barras que se agrupan, las últimas barras quedarán muy descompensadas, con retales demasiado grandes.

El número teórico de barras que vamos a consumir en las piezas combinables es la suma de la longitud de las piezas combinables entre la longitud de barra (redondeado hacia arriba porque no se venden porciones de barra).

Desperdicio admisible por barra, d

El desperdicio mínimo que podemos obtener será la diferencia que hay entre la suma de las longitudes de las barras y la suma de las longitudes de las piezas. Y este valor, dividido entre el número de barras es el desperdicio que debería aparecer en cada barra si en todas hubiera el mismo (que lo voy a llamar d).

Versión 2.0

La versión 2.0, aparta las piezas solitarias, cada una en su agrupación, consumiendo una barra por pieza.

Después calcula el número teórico de barras para las piezas combinables, el desperdicio optimizable y el valor d.

En el momento de crear una agrupación, comprueba si hay un retal. Si lo hay, entrará en un bucle que combinará todas las piezas disponibles dejando fija la primera pieza de esa agrupación (la pieza más grande). El bucle que va generando combinaciones se repite hasta que el retal sea más pequeño que d, y se selecciona la última combinación. Si no se da ninguna combinación que cumpla esta condición se escoge la menos mala, la que dé un retal menor.

Volvemos a probar con el listado de piezas que empleamos en la versión 1.0:

  1. Ordena las piezas de mayor a menor (nº de piezas · longitud): 1 · 6.00, 1 · 4.00, 4 · 3.00, 1 · 2.40, 2 · 2, 20 · 1.5, 2 · 1.20, 1 · 1.00
  2. Agrupa. según el orden que tiene, en listas cuya suma sea menor o igual a 6:
    {6.00}, {4.00, 2.00}, {3.00, 3.00}, {3.00, 3.00},
  1. {2.40, 2.00, 1.50} tiene un resto de 0.1, se valora la agrupación sin usar el 1.5 o sin usar ni el 1.5 ni el 2:
    1. {2.4, 2, 1.2} tiene un resto de 0.6
    2. {2.4, 1.2, 1.2} tiene un resto de 0. Es la solución escogida.
  2. Sigue la rutina con {1, 2, 3}

Y parece que funciona.

Pero seguro que es mejorable…

Anuncios

Acerca de Pablo Nieto Cabezas

Arquitecto

Publicado el 9 enero, 2017 en Informática, Tecnología y etiquetado en , . Guarda el enlace permanente. Deja un comentario.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: