Algoritmo de ajuste múltiple
El algoritmo multiajuste es un algoritmo para la partición de números de múltiples vías , desarrollado originalmente para el problema de la programación de máquinas idénticas . Fue desarrollado por Coffman, Garey y Johnson. [1] Su novedad proviene del hecho de que utiliza un algoritmo para otro problema famoso, el problema del empaque de contenedores , como subrutina.
La entrada al algoritmo es un conjunto S de números y un parámetro n . La salida requerida es una partición de S en n subconjuntos, de modo que la suma de subconjuntos más grande (también llamada " makespan " ) sea lo más pequeña posible.
El algoritmo utiliza como subrutina, un algoritmo llamado primer ajuste decreciente bin packing (FFD). El algoritmo FFD toma como entrada el mismo conjunto S de números y una capacidad binaria c . Empaqueta heurísticamente los números en contenedores de modo que la suma de los números en cada contenedor sea como máximo C , con el objetivo de utilizar la menor cantidad posible de contenedores. Multifit ejecuta FFD varias veces, cada vez con una capacidad C diferente , hasta que encuentra algún C tal que FFD con capacidad C empaqueta S en n contenedores como máximo. Para encontrarlo, utiliza la búsqueda binaria de la siguiente manera.
Multifit es un algoritmo de aproximación de factor constante . Siempre encuentra una partición en la que elmakespan es como máximo un factor constante mayor que elmakespan óptimo. Para encontrar esta constante, primero debemos analizar FFD. Mientras que el análisis estándar de FFD considera la aproximación en función del número de contenedores cuando la capacidad es constante, aquí necesitamos analizar la aproximación en función de la capacidad cuando el número de contenedores es constante. Formalmente, para cada tamaño de entrada S y entero n, sea la capacidad más pequeña tal que S pueda empaquetarse en n contenedores de esta capacidad. Tenga en cuenta que es el valor de la solución óptima para la instancia de programación original.
Sea el número real más pequeño tal que, para cada entrada S , FFD con capacidad utiliza como máximo n contenedores.
Coffman, Garey y Johnson prueban los siguientes límites superiores en : [1]