Here is the question: Assuming a set of node n1,n2,...,nk, each node has some redundant resources represented by a set of numbers. For example, node n1 has resource {1,1,3,6,6,6,9}. And each node requires some resources. For example, node n1 requires {2,5,5}. If node ni get a number from node nj, there is a directed edge from nj to ni. How to allocate resource so that there is no circles in the graph and the count of edges is maximum.
Notes: 1. If node ni get multiple numbers from node nj,e.g. ni get {1,2,2}, there is 3 directed edges from nj to ni where each edge represents a number allocation. 2. The redundant resource( number set) of all node may not match the required resource ( number set ). 3. No circle in the directed graph means that no circular dependency. For example, node a gives 1 to b; b gives 2 to c; c give 3 to d; d gives 4 to a. This is not allowed.
The overall objective is: Maximum utilization of redundant resources and no circular dependency.
Any comments will be appreciated. Thank you in advance.
I'll reform this question as minimize external dependency in task scheduling:
Consider a set of tasks
$t_1,t_2,...,t_n$. Each requires some data dependencies and outputs some data. We represents data as numbers. For example, task$t_i$need dependencies{1,1,3,5}and the task outputs data{2,2,4}. For every task the dependent numbers and output numbers share an empty intersection.Considering the set of tasks, the total dependency and the total output may not match, which means that the tasks need external resources(numbers).
Given the task set and the dependency and output of each task, how to schedule the task to minimize external dependency(count of external numbers) under condition: 1. Each number has the same weight. 2. There is only one task execution host.
More deeply, what about different weights of different numbers? The sum of weight of external numbers? What about multiple task execution hosts?