Asignación de recursos a entidades que utilizan recursos.

Un método para asignar un recurso (12) de entre una pluralidad de recursos a una entidad que utiliza recursos de entre una pluralidad de entidades (D1,

D2, D3) que utilizan recursos, en el que una asignación de recurso a entidad que utiliza recursos tiene un coste asociado, incluyendo el método:

computar (304) costes (Cf) de flujo de red de asignaciones para asignar dichos recursos a dicha entidades que utilizan recursos,

construir/actualizar (306) una red (200) de flujo incluyendo nodos fuente (203) que corresponden a los recursos, nodos (205) de transbordo que corresponden a las asignaciones y un nodo (207) de demanda, teniendo la red de flujo arcos (209) que representan flujo entre los nodos, teniendo cada uno de dichos arcos un coste (Cf) de flujo de red mencionado asociado,

resolver (308) un problema de flujo de coste mínimo para la red de flujo con costes de arco anulados para obtener valores (Xf) de flujo para las asignaciones, y

asignar (310, 312) un recurso mencionado a una entidad que utiliza recursos mencionada dependiente del valor de flujo obtenido para una asignación mencionada asociada con ese recurso;

caracterizado el método porque el paso de computar (304) los costes (Cf) de flujo de red incluye computar los costes de flujo de red de acuerdo con un esquema de aproximación de coste de arco de aproximación de red neural aleatoria.

Asignación de recursos a entidades que utilizan recursos

La presente invención se refiere generalmente a la asignación de recursos a entidades que utilizan recursos.

La figura 1 muestra una red 1 de comunicaciones que comprende un conjunto de conexiones 12 de datos para transferir datos entre nodos 14. La figura también ilustra esquemáticamente una pluralidad de elementos (D1, D2, D3 en el ejemplo) de datos que han de ser transferidos mediante las conexiones de datos a uno o más nodos. Se entenderá que la red y los elementos de datos pueden tomar varias formas, por ejemplo, las conexiones de datos pueden ser componentes físicos, canales inalámbricos, etc., y los elementos de datos pueden ser paquetes o cualquier otra disposición transferible de datos.

La capacidad/habilidad de transferencia de cada conexión de datos es limitada. En un caso simple, cada conexión solo puede ser capaz de transferir un elemento de datos en cualquier periodo/espacio de tiempo. Usar cada conexión de datos puede tener un coste asociado, que puede ser expresado de varias maneras, por ejemplo, en términos de transferencia de otros elementos de datos siendo retrasados o nivel de ruido. Además, si un elemento de datos no está atribuido a una conexión de datos entonces también puede haber un coste. Asi, es deseable atribuir conexiones de datos para transferir los elementos de datos de manera rentable. Un objetivo es hacer asignaciones que reduzcan/minimicen el coste total esperado.

Otros ejemplos del problema técnico general de asignar recurso a entidades incluyen asignar medios de transporte a elementos transportables, o asignar recursos de armas a objetivos. En estas aplicaciones también, es deseable proporcionar una buena solución al problema de asignación de recursos, que puede estar basada en reducir/minimizar varios factores de coste.

El documento de Rasmussen, J et al, Resource-optimal scheduling using timed autómata, 9 de marzo de 24, Tools and Algorlthms for the Constructlon and Analysis of Systems, Lecture Notes in Computer Science, Springer- Verlag, Berlín/Heidelber, páginas 22-235, trata cómo la estructura simple de programas lineales encontrados durante el análisis de accesibilidad de coste mínimo simbólico de autómatas de tiempo tasado puede ser explotada con el fin de mejorar el rendimiento.

El documento US 28/221967 divulga un sistema de ordenamiento basado en atributos que permite que las necesidades de los clientes sean especificadas por los atributos de recursos correspondientes en lugar de recursos específicos de manera que pueden conocerse más necesidades de clientes y los costes totales de asignación de recursos a clientes pueden ser minimizados.

Las realizaciones de la presente invención están destinadas a abordar al menos alguno de los problemas tratados anteriormente. Las realizaciones pueden resultaren computación eficiente de una solución de asignación.

De acuerdo con un primer aspecto de la presente invención es provisto un método de asignar un recurso de entre una pluralidad de recursos a una entidad que utiliza recursos de entre una pluralidad de entidades que usan recursos, en el que una asignación de entidad que usa recurso a recurso tiene un coste asociado, incluyendo el método:

computar costes (Cf) de flujo de red de asignaciones de recurso a entidad para asignar dichos recursos a dichas entidades,

construir/actualizar una red de flujo incluidos los nodos fuente correspondientes a los recursos, nodos de transbordo que corresponden a las asignaciones y un nodo de demanda, teniendo la red de flujo arcos que representan flujos entre los nodos, cada uno de dichos arcos teniendo dicho coste (Cf) de flujo de red asociado,

resolver un problema de flujo de coste mínimo para la red de flujo con costes de arco anulados para obtener valores (Xf) de flujo para las asignaciones, y

asignar dicho recurso a dicha entidad dependiente del valor de flujo obtenido para dicha asignación asociada con ese recurso;

en el que el paso de computar los costes de flujo de red incluye computar los costes de flujo de red de acuerdo con un esquema de aproximación de coste de arco de aproximación de red neural aleatoria.

El paso de computar los costes (Cf) de flujo de red puede incluir computar los costes de flujo de red para asignaciones que satisfagan una ecuación:

C,{a, = max{, U{t) E*, !>/(%-*)»,(a, í) - Ca(a,t)) (3)

en la que las variables en la ecuación pueden ser como sigue: a representa un activo/recurso;

t(mt) representa dicho nodo de transbordo en la red de flujo que denota una asignación nvésima a la entidad t;

U(t) representa un coste de penalización U(t) si una entidad t no es servida apropiadamente por un recurso;

Pf(a,t) representa una probabilidad de que un recurso a fallará en servir apropiadamente a una entidad t cuando se asigna a esta;

Ca(a,t) representa un coste para asignar un recurso a a una entidad t.

La red de flujo puede ser configurada de manera que las capacidades de arco y suministros/demandas de los nodos sean ó 1 de manera que una solución que resulta de la resolución del problema de flujo de coste mínimo para la red de flujo será binaria. La asignación de dicho recurso a dicha entidad puede ser hecha si el valor de flujo obtenido para la asignación asociada con ese recurso es igual a 1.

Dicho nodo fuente a en la red de flujo puede estar conectado a una pluralidad de dichos nodos t(riV de transbordo vía dichos arcos. Una capacidad de los arcos entre el nodo fuente y los nodos de transbordo puede ser igual a 1 (de manera que los flujos asociados Xf(a,t(,1V) representan el hecho de que dicho recurso a es una asignación mt-ésima a dicha entidad t). Así, la red de flujo puede ser configurada de manera que como mucho dicho nodo de recurso puede ser asignado a dicho nodo de transbordo. Cada uno de dichos nodos de transbordo puede tener solo dicho arco yendo hacia el nodo d de demanda y el arco puede también tener una capacidad de 1.

El método puede además incluir almacenar y/o visualizar datos electrónicos que representan la asignación o asignaciones.

El método puede además incluir actualizar costes de tareas siguiendo las asignaciones.

De acuerdo con otros aspectos de la presente invención se prevén sistemas configurados para ejecutar métodos substancialmente como se describe aquí.

De acuerdo con otros aspectos de la presente invención se prevén productos de programa de ordenador que comprenden medios legibles de ordenador, teniendo en ellos medios de código de programa de ordenador, cuando el código de programa se carga, para hacer que el ordenador ejecute medios substancialmente como se describe aquí.

El término "recurso" usado aquí generalmente se refiere a un activo y puede ser cualquier tipo de recurso que pueda ser asignado para cualquier tipo de utilización técnica. Un recurso puede ser una entidad física, tal como una máquina o vehículo, o puede ser un recurso electrónico, tal como una memoria de ordenador o capacidad en una conexión de transferencia de datos en una red de comunicaciones. Una entidad de utilización de recursos puede ser una entidad física, tal como un elemento para ser transportado, o puede comprender una tarea que requiera un recurso con el fin de ser realizada, por ejemplo, una tarea de computación que requiera un recurso de computación, tal como tiempo de procesador. Además, debería entenderse que las referencias a "conexión de datos" y "elemento de datos" en la realización de ejemplo y declaraciones asociadas de la invención están destinadas a ser intercambiables con otros términos, tal como "medios de transporte/arma" y "elemento transportable/objetivo", respectivamente.

Aunque la invención ha sido descrita anteriormente, se extiende a cualquier combinación inventiva de características establecidas anteriormente o en la siguiente descripción. Aunque las realizaciones ilustrativas de la invención se describen en detalle aquí en referencia a los dibujos que la acompañan, ha de entenderse que la invención no está limitada a estas realizaciones precisas. Como tal, muchas modificaciones y variaciones serán evidentes para los expertos en la técnica. Además, se contempla que una característica particular descrita tanto individualmente como parte de una realización puede ser combinada con otras características descritas individualmente, o partes de otras realizaciones, incluso si otras características y realizaciones no hacen mención de la característica particular. Así, la invención se extiende a tales combinaciones específicas no descritas todavía.

La invención puede ser realizada de varias formas, y, a modo de ejemplo solo, realizaciones de esta serán... [Seguir leyendo]

1.- Un método para asignar un recurso (12) de entre una pluralidad de recursos a una entidad que utiliza recursos de entre una pluralidad de entidades (D1, D2, D3) que utilizan recursos, en el que una asignación de recurso a entidad que utiliza recursos tiene un coste asociado, incluyendo el método:

computar (34) costes (Cf) de flujo de red de asignaciones para asignar dichos recursos a dicha entidades que utilizan recursos,

construir/actualizar (36) una red (2) de flujo Incluyendo nodos fuente (23) que corresponden a los recursos, nodos (25) de transbordo que corresponden a las asignaciones y un nodo (27) de demanda, teniendo la red de flujo arcos (29) que representan flujo entre los nodos, teniendo cada uno de dichos arcos un coste (Cf) de flujo de red mencionado asociado,

resolver (38) un problema de flujo de coste mínimo para la red de flujo con costes de arco anulados para obtener valores (Xf) de flujo para las asignaciones, y

asignar (31, 312) un recurso mencionado a una entidad que utiliza recursos mencionada dependiente del valor de flujo obtenido para una asignación mencionada asociada con ese recurso;

caracterizado el método porque el paso de computar (34) los costes (Cf) de flujo de red incluye computar los costes de flujo de red de acuerdo con un esquema de aproximación de coste de arco de aproximación de red neural aleatoria.

2.- Un método de acuerdo con la reivindicación 1, en el que el paso de computar (34) los costes (Cf) de flujo de red incluye computar los costes de flujo de red para asignaciones que satisfacen una ecuación:

Ct(a, í<m'+») = max{, U{t)nLi , t)p(a,i) - C(a, t)} (3)

en la que:

a representa dicho recurso;

t(mt) representa dicho nodo de transbordo en la red de flujo que denota una asignación nvésima a la entidad t;

U(t) representa un coste de penalización U(t) si una entidad t no es servida apropiadamente por un recurso;

Pf(a,t) representa una probabilidad de que un recurso a fallará en servir una entidad t cuando se asigne a esta;

Ca(a,t) representa un coste para asignar un recurso a a una entidad t.

3 - Un método de acuerdo con una cualquiera de las reivindicaciones precedentes, en el que la red (2) de flujo es configurada de manera que las capacidades de los arcos (29) y suministros/demandas de los nodos (23, 25, 27) son tanto como 1 de manera que una solución que resulta de la resolución del problema de flujo de coste mínimo para la red de flujo es binaria.

4.- Un método de acuerdo con la reivindicación 3, en el que la asignación (31, 312) de dicho recurso (12) a dicha entidad (D1) que utiliza recursos se hace si el valor de flujo obtenido para la asignación asociada con ese recurso es igual a 1.

5.- Un método de acuerdo con la reivindicación 4, en el que dicho nodo fuente (23) a en la red (2) de flujo es conectado a una pluralidad de dichos nodos (25) de transbordo t(mt) (25) vía dichos arcos (29) y una capacidad de los arcos entre el nodo fuente y los nodos de transbordo es igual a 1.

6.- Un método de acuerdo con la reivindicación 5, en el que la red (2) de flujo se configura de manera que como mucho dicho nodo fuente (23) se asigna a dicho nodo (25) de transbordo.

7.- Un método de acuerdo con la reivindicación 6, en el que dicho nodo (25) de transbordo tiene dicho arco (29) que se va hacia el nodo (27) de demanda d, teniendo ese arco una capacidad de 1.

8.- Un método de acuerdo con una cualquiera de las reivindicaciones precedentes, que incluye almacenar y/o visualizar (32) datos electrónicos que representan la asignación o asignaciones.

9.- Un método de acuerdo con una cualquiera de las reivindicaciones precedentes, que incluye además controlar dicha fuente (12) para servir a dicha entidad (D1) que utiliza recursos de acuerdo con dicha asignación.

1.- Un producto de programa de ordenador que comprende medios legibles de ordenador, teniendo medios de código de programa de ordenador, cuando el código de programa se carga, para hacer que el ordenador ejecute un método de acuerdo con una cualquiera de las reivindicaciones precedentes.

11.- Un sistema (1) de computación configurado para ejecutar un método de acuerdo con una cualquiera de las reivindicaciones 1 a 9.