CODEWITHSUNDEEP
pythonvariable-assignmenthungarian-algorithm
Yannis
Yannis

Reputation: 205

Assignment/allocation of tasks in hosts

I have a set of hosts and a set of tasks.
Each host has cpu, mem and task capacities and each task has cpu, mem requirements.
Each host belongs to a latency class and may communicate with other hosts with a certain latency value.
Each task may require to communicate with another task with a latency equal or less to a certain value.
An example of my problem input is shown in the next image.Task and host graphs. where task t1 requires to communicate with tasks t2, t3 and t4 with a latency equal or less than 3, 3 and 5 respectively and host h1 belongs to a latency class 3 and communicates with h2, h3 and h4 with latencies 2, 5, and 3 respectively.
I was thinking to solve this problem using the Hungarian/munkres algorithm but how can i set a cost function properly? Is there a better assignment algorithm to solve this?
Thanks.

Upvotes: 1

Views: 541

Answers (2)

trinchet
trinchet

Reputation: 6933

As you should know, this problem is a case of the QAP (Quadratic Assignment Problem) and this is NP complete, which means in few words: there isn't exist the best algorithm for solving it, at least in polynomial time. More details here

Though, there are several approachs to deal with, I've tried some simple methods from the AI like Genetic Algorithms (GA) and ACO with great results. I would recommend you GA for.

Upvotes: 1

ZZY
ZZY

Reputation: 3937

There is a Python package for Munkres: http://software.clapper.org/munkres/. You may refer to their implementation: https://github.com/bmc/munkres/blob/master/munkres.py

Upvotes: 1

Related Questions