Asignacion eficiente de elementos
Publicado por Luis (1 intervención) el 17/08/2004 16:59:35
Hola,
tengo ante mi un problema complejo que creo que podria suponer un reto interesante para cualquier aficionado a los algoritmos. Tiene que ver con una herramienta en Visual Basic que estoy desarrollando para ayudar a la virtualizacion de servidores.
Tengo un numero limitado de servidores "origen" con distintas caracteristicas (por simplificar, supongamos solo 2: CPU Y RAM). Estos servidores deben encajarse en un numero ilimitado servidores "destino", con gran capacidad de CPU y RAM.
El problema es como asignar de forma *optima* los servidores origen en los servidores destino, sin exceder las capacidades de estos. 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 deberia dar este resultado:
SERVIDOR DESTINO 1 (QUEDARIA CON CPU 50 Y MEMORIA 100): SERV. ORIGEN 1 + SERV. ORIGEN 3
SERVIDOR DESTINO 2 (QUEDARIA CON CPU 80 Y MEMORIA 100): SERV. ORIGEN 4 + SERV. ORIGEN 6
SERVIDOR DESTINO 3 (QUEDARIA CON CPU 100 Y MEMORIA 90): SERV. ORIGEN 2 + SERV. ORIGEN 8
SERVIDOR DESTINO 4 (QUEDARIA CON CPU 60 Y MEMORIA 100): SERV. ORIGEN 5 + SERV. ORIGEN 7
Como se puede apreciar, se necesitan 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 maxima de los servidores destino (en este caso 100 de CPU y 100 de RAM), obtener la asignacion de servidores origen a servidores destino que devuelva el menor numero posible de servidores destino.
Gracias por vuestras sugerencias.
tengo ante mi un problema complejo que creo que podria suponer un reto interesante para cualquier aficionado a los algoritmos. Tiene que ver con una herramienta en Visual Basic que estoy desarrollando para ayudar a la virtualizacion de servidores.
Tengo un numero limitado de servidores "origen" con distintas caracteristicas (por simplificar, supongamos solo 2: CPU Y RAM). Estos servidores deben encajarse en un numero ilimitado servidores "destino", con gran capacidad de CPU y RAM.
El problema es como asignar de forma *optima* los servidores origen en los servidores destino, sin exceder las capacidades de estos. 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 deberia dar este resultado:
SERVIDOR DESTINO 1 (QUEDARIA CON CPU 50 Y MEMORIA 100): SERV. ORIGEN 1 + SERV. ORIGEN 3
SERVIDOR DESTINO 2 (QUEDARIA CON CPU 80 Y MEMORIA 100): SERV. ORIGEN 4 + SERV. ORIGEN 6
SERVIDOR DESTINO 3 (QUEDARIA CON CPU 100 Y MEMORIA 90): SERV. ORIGEN 2 + SERV. ORIGEN 8
SERVIDOR DESTINO 4 (QUEDARIA CON CPU 60 Y MEMORIA 100): SERV. ORIGEN 5 + SERV. ORIGEN 7
Como se puede apreciar, se necesitan 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 maxima de los servidores destino (en este caso 100 de CPU y 100 de RAM), obtener la asignacion de servidores origen a servidores destino que devuelva el menor numero posible de servidores destino.
Gracias por vuestras sugerencias.
Valora esta pregunta
0