I guess this is a problem solving question but I am out of ideas, don't really know where else I can resort for help, and I need to solve this problem.
Essentially we have a set of consumers and a set of resources, and the objective is to assign a resource to each consumer. Not every resource is eligible for every consumer: there are many different kind of rules that limit the choices.
Given these consumers and resources:
consumers = [C1, C2, C3, C4, C5]
resources = [R1, R2, R3, R4, R5, R6, R7, R8]
We can represent the eligible resources with a table (note that whether in this example grouping into resource sections may suggest a solution, in practice eligible resources would be more scattered and grouping would be hard or not possible at all):
C1 C2 C3 C4 C5
R1 x x x x
R2 x x x x
R3 x x
R4 x x
R5 x x
R6 x x
R7 x x
R8 x x
We try assigning a resource to every consumer:
while unsatisfied_consumers:
unassigned_resources = list(resources)
unsatisfied_consumers = list(consumers)
for c in unsatisfied_consumers:
for r in eligible_resources[c]:
if c.assign(r):
unsatisfied_consumers.remove(c)
unassigned_resources.remove(r)
break
If not all consumers could be satisfied, for each one of them we try finding eligible already assigned resources, and the consumer assigned to it is given an unassigned resource instead (if eligible). Essentially a reassignment. This would be right after the for loop:
for c in unsatisfied_consumers:
assigned_resources = [r for r in resources if r not in unassigned_resources]
c_eligible_resources = [r for r in eligible_resources[c] if r in assigned_resources]
for r in c_eligible_resources:
satisfied_consumer = r.assigned_consumer()
# try to find an alternative resrouce for the already satisfied consumer
# so that c can be assigned its resource instead
for unassigned_r in unassigned_resources:
if satisfied_consumer.assign(unassigned_r):
unassigned_resrouces.remove(unassigned_r)
unsatisfied_consumers.remove(c)
c.resource = r
As you can see, we are brute-forcing our way to finding the solution.
The problem is when not all consumers can be satisfied, simply due to the resource eligibility. No matter how many times reassigning resources is attempted, some consumers will never be assigned resources because there are not enough resources.
And there is where I am trying to get. I am trying to devise a way to be able to tell what consumers are exposed to resource exhaustion before even starting to assign resources, so that when unsatisfaction issues show up, we can safely assume their state and carry on with the consumers that can actually be assigned resources.
Using my table example, at first glance we can tell that consumers C1, C2 and C3 will rival for resources R1 and R2, therefore one of these consumers will simply be unsatisfied. What I am trying to do is to design a mechanism to acknowledge that [C1, C2, C3] are subject to resource exhaustion therefore if unsuccessful assignment occurs, we should not try again for these particular consumers.
We know what resources are elliglbe for each consumer, and inversely we know what consumers "fit" in each resource. Perhaps this information could be use in the solution?
