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
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 de ajenjonst