Resource Allocation Problem 

The resource allocation problem seeks to find an optimal allocation of a fixed amount of resources to activities so as to minimize the cost incurred by the allocation.

The amount of resources to be allocated to each activity is treated as a continuous or integer variable, depending on the cases. 

Resource Allocation or Resource Management is the scheduling of activities and the resources required by those activities while taking into consideration both the resource availability and the project time.

Resource allocation may be decided by using computer programs applied to a specific domain to automatically and dynamically distribute resources to applicants.

There are two types of dynamic resource allocation: 

• Overflow
  • Here all resources are pre-provisioned and ready
  • We have a standby computer resource ready for on-demand access.
• Tiering 
  • Here all resources are pre-provisioned and ready
  • We dynamically reprioritise an application’s access to the computer resources.

Using Multistage Graph 

A multistage graph G = (V, E) is a directed graph where vertices are partitioned into k (where k > 1) number of disjoint subsets S = {s1,s2,…,sk} such that edge (u, v) is in E, then u Є si and v Є s1 + 1 for some subsets in the partition and |s1| = |sk| = 1.

The vertex s Є s1 is called the source and the vertex t Є sk is called sink.

Resource Allocation Problem  using Multistage Graph 

• The resource allocation problem can be described as a multistage graph.​
• (i, j) : i resources allocated to projects 1, 2, …, j​

Example:

node H=(3, 2) : 3 resources allocated to projects 1, 2.​

Find the longest path from S to T : ​

(S, C, H, L, T),  8+5+0+0=13​

2 resources allocated to project 1.​

1 resource allocated to project 2.​

0 resource allocated to projects 3, 4.​

Find the optimal solution for a give graph 

Solution: