The present invention relates generally to assigning resources to resource-utilising entities.

Figure 1 shows a communications network 10 comprising a set of data links 12 for transferring data between nodes 14. The Figure also schematically illustrates a plurality of data items (D1 , D2, D3 in the example) that are to be transferred over the data links to one or more nodes. It will be understood that the network and data items can take various forms, e.g. the data links may be physical components, wireless channels, etc, and the data items may be packets or any other transferable arrangement of data.

The capacity/transfer ability to of each data link is limited. In a simple case, each link may only be able to transfer one data item at any one time period/slot. Using each data link may have an associated cost, which may be expressed in various ways, e.g. in terms of transfer of other data items being delayed or noise level. Further, if a data item is not allocated a data link then there can also be a cost. Thus, it is desirable to allocate data links for transferring the data items in a cost-effective manner. An objective is to make assignments that reduce/minimise the total expected cost.

Other examples of the general technical problem of assigning resources to entities include assigning transportation means to transportable items, or assigning weapon resources to targets. In these applications too, it is desirable to provide a good solution to the problem of resource assignment, which may be based on reducing/minimising various cost factors. Embodinnents of the present invention are intended to address at least some of the problems discussed above. Embodiments can result in efficient computation of an assignment solution.

According to a first aspect of the present invention there is provided a method of assigning a resource from amongst a plurality of resources to a resource-utilising entity from amongst a plurality of resource-utilising entities, wherein a resource-to-resource-utilising entity assignment has an associated cost, the method including: computing network flow costs (Cf) of resource-to-entity assignments for assigning said resources to said entities; constructing/updating a flow network including source nodes corresponding to the resources, transhipment nodes corresponding to the assignments and a demand node, the flow network having arcs representing flows between the nodes, each said arc having an associated said network flow cost (Cf); solving a Minimum Cost Flow problem for the flow network with negated arc costs to obtain flow values (Xf) for the assignments, and assigning a said resource to a said entity dependent on the flow value obtained for a said assignment associated with that resource.

The step of computing the network flow costs (Cf) can include computing the network flow costs for assignments satisfying an equation:

C ( _a , i ^(mt+1) ) = max{0, U(t) I Li Pf ( ^a tM , t)Ps(a, t) - C _a {a, t)} (3) where variables in the equation are as defined herein. In some embodiments, the equation variables can be as follows: a represents an asset/resource; t ^(m<) represents a said transhipment node in the flow network denoting a mfth assignment to entity t;

U(t) represents a penalty cost U(t) if an entity t is not properly served by a resource;

Pf(a, t) represents a probability that a resource a will fail in properly serving an entity f when assigned to it;

C _a (a, t) represents a cost for assigning a resource a to an entity t.

The step of computing the network flow costs (Cf) can include computing the network flow costs in accordance with at least one arc cost approximation scheme. The arc cost approximation scheme may include a Random Neural Network approximation scheme.

The flow network may be configured so that a solution resulting from the solving of the Minimum Cost Flow problem for the flow network will be binary. The flow network may be configured so that the arc capacities and supplies/demands of the nodes are 0 or 1 . The assigning of a said resource to a said entity may be made if the flow value obtained for the assignment associated with that resource is equal to 1 .

A said source node a in the flow network may be connected to a plurality of said transshipment nodes f ^md v\a said arcs. A capacity of the arcs between the source node and the transshipment nodes can be equal to 1 (so that associated flows X/(a, ^mt) ) represent the fact that a said resource a is an m*th assignment to a said entity t). Thus, the flow network may be configured so that at most one said resource node can be assigned to a said transshipment node. Each said transshipment node may only have one said arc leaving towards the demand node d and the arc may also have a capacity of 1 .

The method may further include storing and/or displaying electronic data representing the assignment(s).

The method may further including updating task costs following the assignments.

According to an alternative aspect of the present invention there is provided a method of assigning an asset from amongst a plurality of assets to a task from amongst a plurality of tasks, the method including: computing network flow costs (Cf) for assigning said assets to said tasks in accordance with a Random Neural Network-based arc cost approximation scheme.

According to another aspect of the invention there is provided a method of assigning a data transfer link from amongst a plurality of links to a data item from amongst a plurality of data items based on a technique substantially as described herein. A data link-to-data item assignment can have an associated cost. The method may include: computing network flow costs (Cf) of assignments for assigning said data links to a said data item; constructing/updating a flow network including source nodes representing the data links, transhipment nodes representing possible data item assignments and a demand node, the flow network having arcs representing flow from a said source node to a said demand node, each said arc having an associated said network flow cost (Cf); solving a Minimum Cost Flow problem for the flow network with negated arc costs to obtain flow values (Xf) for the assignments, and assigning a said data link to a said data item dependent on the flow value obtained for a said assignment associated with that data link.

According to another aspect of the invention there is provided a method of assigning a transportation means from amongst a plurality of transportation means to a transportable item (load) from amongst a plurality of transportable items based on a technique substantially as described herein. A transportation means-to-transportable item assignment can have an associated cost. The method may include: computing network flow costs (Cf) of assignments for assigning said transportation means to a said transportable items; constructing/updating a flow network including source nodes representing the transportation means, transhipment nodes representing possible transportable item assignments and a demand node, the flow network having arcs representing flow from a said source node to a said demand node, each said arc having an associated said network flow cost (Cf); solving a Minimum Cost Flow problem for the flow network with negated arc costs to obtain flow values (Xf) for the assignments, and assigning a said transportation means to a said transportable item dependent on the flow value obtained for a said assignment associated with that transportation means.

According to another aspect of the present invention there is provided a method of assigning a weapon from amongst a plurality of weapons to a target from amongst a plurality of targets, wherein a weapon-to-target assignment has an associated cost, the method including: computing network flow costs (Cf) of weapon-to-target assignments for assigning said weapons to said targets; constructing/updating a flow network including source nodes corresponding to the weapons, transhipment nodes corresponding to the weapon-to-target assignments and a demand node, the flow network having arcs representing flows between the nodes, each said arc having an associated said network flow cost (Cf); solving a Minimum Cost Flow problem for the flow network with negated arc costs to obtain flow values (Xf) for the weapon-to-target assignments, and assigning a said weapon to a said target dependent on the flow value obtained for a said weapon-to-target assignment associated with that weapon.

According to other aspects of the present invention there are provided systems configured to execute methods substantially as described herein.

According to other aspects of the present invention there are provided computer program products comprising computer readable medium, having thereon computer program code means, when the program code is loaded, to make the computer execute methods substantially as described herein.

The term "resource" used herein generally refers to an asset and may be any kind of resource that can be assigned for any kind of technical utilisation. A resource may be a physical entity, such as a piece of machinery or vehicle, or it may be an electronic resource, such as computer memory or capacity in a data transfer link in a communications network. A resource-utilisation entity may be a physical entity, such as an item to be transported, or it may comprise a task that requires a resource in order to be performed, e.g. a computing task that requires a computing resource, such as processor time. Further, it should be understood that references to "data link" and "data item" in the example embodiment and associated statements of invention are intended to be interchangeable with other terms, such as "transportation means/weapon" and "transportable item/target", respectively.

Whilst the invention has been described above, it extends to any inventive combination of features set out above or in the following description. Although illustrative embodiments of the invention are described in detail herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to these precise embodiments. As such, many modifications and variations will be apparent to practitioners skilled in the art. Furthermore, it is contemplated that a particular feature described either individually or as part of an embodiment can be combined with other individually described features, or parts of other embodiments, even if the other features and embodiments make no mention of the particular feature. Thus, the invention extends to such specific combinations not already described.

The invention may be performed in various ways, and, by way of example only, embodiments thereof will now be described, reference being made to the accompanying drawings in which:

Figure 1 is a schematic diagram of a plurality of data links and data items and a system configured to assign data links to the data items;

Figure 2 is a schematic diagram of a flow network for use in solving the assignment problem, and

Figure 3 is a flowchart showing steps that can be performed when generating assignments.

Referring to Figure 1 again, the example problem posed is which data link(s) to assign to which of the data items. The Figure shows a system 100 configured to perform such assignments. It will be understood that the system can take any suitable form, e.g. a personal computer or distributed computing system, and can include conventional communications interfaces, user interfaces, etc. It may be located remote from the network comprising the data links. The system may directly or indirectly control the data link hardware in accordance with the assignment, or may produce an output describing the assignment for use by one or more human operators or another software application. The system can include a computing device having a processor 102 and a memory 104. The memory 104 can include data 106 relating to the data items, data links and/or other factors, as well as instructions 108 that the computing device can execute to perform the assignments.

Data can be produced describing characteristics of each data link, e.g. speed, capacity, etc. It will be appreciated that the number, types and characteristics of the resources described herein are exemplary only. Data specifying characteristics of each data item can also be produced. For instance, each data item may have associated with it, e.g. size, desired delivery time/date, priority, etc. These costs may be determined by human assessors, or may at least be partially retrieved from a data store or automatically calculated based on known information about at least some of the data items.

Embodiments of the invention use flow network techniques to generate the assignments, which are based on solving a sequence of minimum cost flow problems on appropriately constructed networks with estimated arc costs. In general terms, the system can assign resources to entities which use the resources, where each resource can potentially serve any of the entities, but resources serve the entities with a probabilistic outcome of success (execution uncertainty). In specific embodiments the resources comprise data links and the entities comprise data items which are to be transferred over the data links, but it will be appreciated that the system could be modified to generate assignments for different types of applications, e.g. allocating transportation means for transporting items, or assigning weapons to targets. The skilled person can modify the data link assignment example given herein for solving such alternative problems. In specific cases there can be a cost associated with each possible assignment of a resource to an entity, and if an entity is not served by a resource there is also a cost. An objective in such cases is to make assignments to minimise the total expected cost.

Some formal definitions will now be given. A set of tasks T (a specific type of exemplary resource-utilising entities) need to be executed by a set of resources/assets A. Task t carries a penalty U(t) if it is not executed by an asset, while there is also a cost Ca(a, t) for assigning asset a to task t. It is assumed that any task can be executed by any asset and that any one of the assets suffices to execute any one of the tasks. It is also possible that the task execution may fail despite the fact that an asset has been assigned to it, and this is represented by the probability 0 < Pf (a, t) < 1 that asset a will fail in executing task t when it is assigned to it. To compensate task execution failures and to account for the fact that the incurred assignment cost can increase the overall cost, any number of assets (0-|>A|) can be assigned to one task. Another assumption is that the assets assigned to a particular task have an independent effect, so that the total failure probability for the particular task is given by the product of the failure probabilities of the assets assigned to it. The problem can be formulated as equation (1 ) below: min C =∑∑ C _a (a, t)X(a, t) +∑U(t) JJ P _/ ) ^{(< )} (1)

teT aeA teT aeA

X(a, t) G {0, 1} where the decision variables X(a, t) show whether asset a is assigned to task t. The specific problem belongs to the general class of nonlinear assignment problems. Specific embodiments provide schemes for the approximate solution of problem (1 ) above, and are based on solving a sequence of Minimum Cost Flow (MCF) problems with arc costs associated with the examined problem. Formally, the MCF problem considers a directed graph or network G = (N, E) which consists of a set of vertices or nodes N and a set of directed edges or arcs E connecting the nodes. Each arc (/ ^' ,)) e E is characterised by two parameters: the capacity u(i, j) of the particular arc which is the upper bound of flow X/(i, j) allowed through (/ ^' , j) and an associated cost per unit of flow C/(/ ^' , j).

Each node / e N has a supply s(i) that is interpreted as the amount of flow that enters the node from the outside. Node / is a source or supply node if s(i) > 0, a sink or demand node if s(i) < 0 and a transshipment node if s(i) = 0. Flow networks are governed by the flow conservation constraint, which states that at each node the incoming and outgoing flows are equal. Note that the conservation constraint can hold only if ∑, s(i) = 0. An objective is to find the cheapest flows that satisfy the nodes' supply, under the flow conservation and capacity constraints:

(2a)

s-t. s(i) +∑ _i)&£ Xf i i) =∑ _{j : (ij ) ef} Xf (iJ), Vi G N (2b)

0≤Xf (i )≤ u(i, j), {i, j) e (2c)

Figure 2 depicts a network 200 used for the solution of problem (1 ) above. The network comprises three layers of nodes: the first layer 202 contains the source nodes 203, the second layer 204 contains the transshipment nodes 205 and the third layer 206 the demand node 207 that aggregates the flows send by the source nodes. Each source node a has supply s(a) = 1 and corresponds to asset a. Each transshipment node ^mt) denotes the m _f th asset assignment to task t, while node 0 corresponds to the case that an asset is not assigned to any task. At most M assets can be assigned to task t. The role of the demand node d is to aggregate the flows send in the network and its demand is equal to the total supply of the assets, S(d) = - \A \ .

A source node a is connected to all transshipment nodes f ^md and the capacity of all arcs (209) is equal to 1 , so that the associated flows X/(a, ^m,) ) represent the fact that asset a is the m _f th assignment to task t. Even though there are \A\ arcs arriving at each transshipment node, there is only one arc leaving each such node towards the demand node d. These arcs also have capacity 1 except from the arc (0, d) whose capacity is equal to \A\ so that even if no assignments are made the source nodes' supply reaches the demand node via node 0. Thus, flow X/ ( ^m ' d), t e T denotes whether the m _f th assignment for task t has been made. The resulting configuration guarantees that at most one asset can be assigned to a particular transshipment node. Moreover, as all arc capacities and supplies/demands of the nodes are 0 or 1 , the integrality property guarantees that in the MCF solution all flows X _/ (a, f ^md ) will be binary. We also need to ensure that the assignment of assets to a particular task t is contiguous. This ensures that X/(a, ^mt) ) can only be equal to 1 if X _f (a, t ^m) ) = 1 for all m = 1 , m _t - 1 .

The arc costs represent the net reduction in the cost function from assigning a particular asset to a task so our aim is to maximise the net reduction in the objective function. Thus, to solve the problem as a MCF problem all the costs associated with the network are negated.

Approximation of the arc costs is necessary because only the ones corresponding to first assignments C [a, ^} ) are known and equal to max/Ό, U(t)p _s (a, t)- Ca(a, t)j for all a, t. To correctly determine the arc costs of the (m _t + 1 )th assignment, m _t ≥ 1 , the first m _t assigned assets to task t aw,..., a^„ must be known. If an oracle provides this information C/(a, ^mt+1 >) would be:

C7 _f ( ^(mt+1) ) = m _&X {0, U(t) L _i Pf (a _t ( r , t)p _s (a, t) - C _a {a, t)} (3)

Concerning the cost of the arcs towards node 0, it is taken that C _f (a, 0) = ε > 0, V a. As ε> 0, it is possible to avoid unbounded solutions due to possible zero arc costs. At the same time the value of ε should be small enough so that it is never considered as a beneficial assignment. The arc costs from the transshipment nodes to the demand node are all equal to zero; the role of those flows is to ensure that at most one asset is related to one task.

In practice, the asset assignments are not known beforehand and hence it is not possible to determine the cost values C/(a, ^mt) ),m _t > 1 ; for this reason approximation schemes have been developed. A conservative approach, called MCFmax, is to always assume that the previously assigned asset to a particular task is the least effective one i.e. the one with the largest execution failure probability _:ηα χ(ί) = max^ ^a, 0- Hence, every term Pf (a _fw , t), m = 1 , ...,m _t in Equation (3) above will be replaced by p -m∞(f). An optimistic approach, called MCFmin, is to always consider the most effective asset for previous assignments. If pf _: mm(t) = max^^ p^a, t) then we set Pf (a _fw , f)≡p™»(f). A third approximation scheme, called MCFrnn, is based on the Random Neural Network (RNN, see Timotheou, S.: The Random Neural Network: A Survey. The Computer Journal 53(3) (2010) 251 -267). The approach can involve solving the problem using an RNN algorithm (see Gelenbe, E., Timotheou, S., Nicholson, D.: Fast distributed near optimum assignment of assets to tasks. The Computer Journal (2010)) and then using the derived allocations to obtain the arc costs for the MCF network. Hence, the terms Pf (a _iw , t) are changed to Pf;rnn(t(m)) which denote the execution failure probabilities for the mth asset assigned to task t. As the RNN algorithm is of low time complexity the overall execution time of the MCF approach is not significantly affected.

An important property of the described flow network is that because 0 <Pf (a, t) <1, it is true that: C/(a, t ⁽¹⁾ ) > . . . > C/(a, t ^(m) ) > C/(a, 0) > 0. The fact that this inequality does not include C/(a, t ) implies that C/(a, t ^(m> ) = 0, m = m _t + 1 , ...,M _t , so that after the m _f th assignment asset a cannot be assigned to task t. This inequality also guarantees the contiguous property as the most beneficial assignment for every asset-task pair is always the first available.

An example implementation of an MCF approach for the solution of problem (1 ) above is shown in the flowchart of Figure 3. It will be appreciated that the steps shown are exemplary only and the skilled person will be able to implement the general principles using various data structures and programming techniques. Some of the steps shown may be omitted and/or reordered. For instance, the use of sets/data structures for temporarily storing data representing assignments is only an example implementation and alternative methods could be used. At step 302 initialisation is performed. This can include setting a data structure (Arem) used during execution of the algorithm to store a set of assets (e.g. data transfer links) that have not been so far been assigned to initially include all of the assets, and a solution set of assignment pairs (S) to empty. An array of variables (Ucur(t)) used to store the cost of not executing a task t (e.g. a data item to be transferred to particular destination) is initially set to the task costs U(t). Formally: initialise A _rem ^ A, S <— 0 and Ucur(t) <— U(t), t e T .

At step 304 the network flow costs (Cf), all tasks t and all possible assignments according to equation (3) above and the desired approximation scheme (e.g. MCFmax, MCFmin or MCFrnn) for all remaining assets in ™ are computed. Formally: compute Cf(a,f% a e A _rem , fe T and m _t =1, ...,M _t according to Eq. (3) and the desired cost approximation scheme.

At step 306 a flow network as shown in Figure 1 is constructed for all assignments in the ™ set . Formally: construct flow network for a e ™ and t e T.

At step 308 the flow network is treated as an MCF problem that is solved, using the negated arc costs discussed above, to obtain the flow values

X _f (a, t ^(m >).

At step 310 the assets to be assigned are determined by selecting the network flows corresponding to first assignments computed at step 308 that have a value of 1 . Formally: set A _ass -^- {a : X _f (a, t ^(1> ) = 1, a e Arem, t e Tj. At step 312 the assignments made at step 310 for this iteration are stored in the solution set. Formally: set S _cu/ - <— {(a, t) : X _f (a, t ^<1) ) = 1, a e A _rem , t e Tj and S ^ S u Scur.

At step 314 the assignments made at step 310 are removed from the set

Arem.

At step 316 the current task costs for all assets are updated by multiplying them with the failure probabilities of assignments pairs in S _cur that have been assigned to a particular task t. Formally: Ucur(t) Ucur(t) Π a:<a;t) _e (a, t), t e T

At step 318 a question is asked whether the sets A _rem and Αα∞ are not empty (formally: if A _ass ≠ 0 and A _em ≠ 0 ). If this is the case then control passes back to step 304, otherwise the process ends at step 320.

In the above steps, S is the solution set where the assignments made are stored, A _rem denotes the set of the assets remaining to be assigned and Ucur(t) is the cost of task t at the particular iteration.

The effectiveness of the proposed algorithms has been analysed by the inventors over two data families. In data family 1 , the problem parameters were independently generated, while in data family 2 there was positive correlation between the cost of an assignment and its associated execution success probabilities, so that "better" assignments are more expensive. More details on the generation of the problem instances can be found in the "Fast distributed near optimum assignment of assets to tasks" reference above. Experiments for several ( \A \, \ T |) pairs with up to 200 assets and 100 tasks were performed. Due to the large size of the problems, the algorithms' performance was compared against tight lower bounds obtained by modifying an algorithm proposed for the WTA problem (see Manne, A.: A Target-Assignment Problem. Operations Research 6(3) (1958) 346-351 ). The performance measure used was the average relative percentage deviation from the lower bound, OLB a _LD = 100(N _PJ ) -^ _=I (C _alg ,i - C _LB C _LB - ¹ where CLB _: I IS the cost obtained from the lower bounding algorithm and NPI is the total number of problem instances considered in each case. σ _/ ,βίθΓ the various algorithms is reported in Tables 1 and 2 below:

Table 1. Average relative percentage deviation from the lower bound in data family 1

Table 2. Average relative percentage deviation from the lower bound in data family 2 Column LBA corresponds to the cost of the original problem (1 ), computed using the solution obtained from the lower bounding algorithm. LBA is only considered to demonstrate the tightness of the lower bounds and is not compared with the other methods, as it is not of polynomial complexity.

For data family 1 the most effective algorithms were found to be the network flow approaches MCFmin and MCFrnn for all (\A\, \T |) pairs, which have almost the same efficiency and achieve OLB < 1 .3% in all cases. In addition, these algorithms outperform the LBA approach for the cases that \A \ \ T I < 1 . Additionally, MCFmax only performed well when \A\ \T | < 1 . For data family 2 the best overall performing algorithm was found to be RNN. RNN performed better than the other approaches for large problem instances when \A \ = \T I and 2\A\ = \ T | , while for the other problems its performance can be highly competitive. MCFrnn achieved better results than the MCFmin approach, especially for the problem sets with equal number of assets and tasks. The performance of the MMR approach was improved compared to data family 1 while the MCFmax was, again, found to be the least effective approach.