Práctica 4 Algoritmos Heurísticos

Mètodes Quantitatius d’Organització Industrial II        [pic 1]

Práctica 4 Algoritmos Heurísticos

Ejercicio 1: Resuelto en clase

Enunciado

Diseñar algoritmos heurísticos para una de las variantes del problema binpackin, que se puede enunciar como sigue:

Se dispone de contenedores cuya forma es la de prismas huecos idénticos y unas piezas, prismas sólidos, de base igual a la de los contenedores y gruesos diferentes. Se trata de determinar el número mínimo de contenedores necesarios para colocar todas las piezas (y la forma de colocarlas).

Aplicaciones:

• Empaquetamiento,
• Corte unidimensional: Cuando el número de contenedores está restringido a 1 y cada artículo se caracteriza por un volumen y un valor, el problema de maximizar el valor de los artículos que pueden caber en el contenedor se conoce como el problema de la mochila.
• Asignación de tareas a estaciones de una línea de producción (si no existen precedencias ni incompatibilidades),
• Determinación del número de vehículos para cubrir unas rutas de duración conocida y origen y destino situado en el mismo punto con un tiempo disponible limitado...

Aplicar los algoritmos heurísticos diseñados al siguiente ejemplar: contenedores de grosor 30 y 20 piezas de grosores, respectivamente, 18, 16, 18, 1, 6, 13, 6, 8, 3, 11, 10, 20, 16, 9, 3, 9, 17, 2, 5 y 15.

Resolución

1º definición de cotas

Cota 1: Suma total de las piezas dividido entre 30 (Capacidad de los contenedores) = 206/30

Cota 2: Cada pieza que tenga un grosor superior a la mitad de la capacidad del contenedor necesitará su propio contenedor = 6 piezas con más de 15 de grosor (18, 16, 18, 20, 16, 17)

Capacidad del contenedor = 30                                                                                

2º Preprocesos (Nos llevan al menos a 1 de las soluciones óptimas)

• Si las piezas de mayor y menor grosor no caben en un mismo contenedor la de mayor irá en su propio contenedor.

• Parejas de piezas con gi+gj=G van en su propio contenedor. (20+10-> Contenedor 1;17+13->Contenedor 2)

Tripletas no: Contraejemplo 24,21,21,5,5,5,3,3 (24+3+3,21+5,21+5.5),(24+5,21+5+3,21+5+3).

3º Formalización

1. Ordenar las piezas de mayor a menor grosor.
2. Mientras quede alguna pieza por asignar:

1. Asignamos la siguiente pieza en el primer contenedor que quepa.
2. Si no cabe en ninguno, se abre uno nuevo y se asigna ese.

Información Extra: Offline Algorithms

En la versión fuera de línea del embalaje en contenedores, el algoritmo puede conocer todos los artículos antes de comenzar a colocarlos. Esto permite alcanzar relaciones de aproximación mejoradas.

Existen muchos algoritmos de aproximación:

• Algoritmo de primer ajuste (First-fit bin packing) proporciona una solución rápida, pero a menudo no óptima, que implica colocar cada artículo en el primer contenedor en el que quepa. Tiempo: n*log(n), donde n es el número de artículos a embalar. 20*log(20) = 26,02.

• Algoritmo decreciente de primer ajuste, partiendo del algoritmo del primer ajuste ordenando primero la lista de elementos en orden decreciente, aunque esto todavía no garantiza una solución óptima, y ​​para listas más largas puede aumentar el tiempo de ejecución del algoritmo. Sin embargo, se sabe que siempre existe al menos un pedido de artículos que permite que el primer ajuste produzca una solución óptima.

Piezas ordenadas de mayor a menor: 20, 18, 18, 17, 16, 16, 15, 13, 11, 10, 9, 9, 8, 6, 6, 5, 3, 3, 2, 1.

Ejercicio 2: Entrega grupo

Enunciado

Proponer algoritmos heurísticos sencillos para el problema de llenado de camiones, en dos dimensiones, con cargas rectangulares no homogéneas y el objetivo de minimizar el número de camiones necesarios, considerando que todos los camiones son de iguales longitudes y costes.

Resolución

Introducción

En esta práctica se aborda el problema de binpacking de una y dos dimensiones, conocidos como One-Dimensional Bin Packing Problem (1D-BPP) y Two-Dimensional Bin Packing Problem (2D-BPP) respectivamente. Para el problema 1D-BPP se va a diseñar un algoritmo heurístico y se va a aplicar para un ejemplar propuesto. Para el problema 2D-BPP se van a proponer algoritmos heurísticos existentes en la literatura.

...