Algoritmo para asignación eficiente de elementos

Hola,
Tengo ante mi un problema complejo que creo que podría suponer un reto interesante para cualquier aficionado a los algoritmos. Tiene que ver con una herramienta en Visual Basic que estoy desarrollando.
El problema es el siguiente:
Tengo un numero limitado de servidores "origen" con distintas características (por simplificar, supongamos solo 2: CPU Y RAM). Estos servidores deben encajarse en un numero ilimitado de servidores "destino", con gran capacidad - pero limitada - de CPU y RAM.
La dificultad consiste en cómo asignar de forma *optima* los servidores origen en los servidores destino, sin exceder las capacidades de estos últimos. Cuando digo "optima" me refiero a utilizando el menor numero posible de servidores destino.
Ejemplo:
SERVIDOR ORIGEN 1: CPU 30 Y RAM 20
SERVIDOR ORIGEN 2: CPU 40 Y RAM 40
SERVIDOR ORIGEN 3: CPU 20 Y RAM 80
SERVIDOR ORIGEN 4: CPU 60 Y RAM 70
SERVIDOR ORIGEN 5: CPU 10 Y RAM 20
SERVIDOR ORIGEN 6: CPU 20 Y RAM 30
SERVIDOR ORIGEN 7: CPU 50 Y RAM 80
SERVIDOR ORIGEN 8: CPU 60 Y RAM 50
Si los servidores destino tiene una pacidad de CPU 100 y RAM 100, el algoritmo debería dar este resultado:
Servidor destino 1 (quedaría con cpu 50 y memoria 100): serv. Origen 1 + serv. Origen 3
servidor destino 2 (quedaría con cpu 80 y memoria 100): serv. Origen 4 + serv. Origen 6
servidor destino 3 (quedaría con cpu 100 y memoria 90): serv. Origen 2 + serv. Origen 8
servidor destino 4 (quedaría con cpu 60 y memoria 100): serv. Origen 5 + serv. Origen 7
Como se puede apreciar, en este caso se necesitan, como mínimo, 4 servidores destino.
Lo que intento buscar es una algoritmo para, partiendo de los servidores origen (CPU y RAM de cada uno) y de la capacidad máxima de los servidores destino (en este caso 100 de CPU y 100 de RAM), obtener la asignación de servidores origen a servidores destino que devuelva el menor numero posible de servidores destino.
¿Alguna idea?
Gracias,
Luis

1 respuesta

Respuesta
En principio se me ocurre que puedes usar algoritmos utilizados en sistemas operativos para asignación de páginas y segmentos tales como first fit, worst fit.
Puedes encontrar información sobre estos algoritmos en http://www.monografias.com/trabajos/so2/so2.shtml#_Toc471305916
Aunque hay muchas más páginas por ahí que te pueden explicar el algoritmo.
Suerte

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas