Brute forcing a bin packing problem
Join the DZone community and get the full member experience.
Join For FreeGiven a set of servers with different hardware (CPU, memory and network bandwidth)The brute force algorithm is simple: try every combination between processes where each process is assigned to each server. For example, if we have 6 processes (P0, P1, P2, P3, P4, P5) and 2 servers (S0, S1), we'd try these solutions:
and given a set of processes with different hardware requirements,
assign each process to 1 server
and minimize the total cost of the active servers.
- P0->S0, P1->S0, P2->S0, P3->S0, P4->S0, P5->S0
- P0->S0, P1->S0, P2->S0, P3->S0, P4->S0, P5->S1
- P0->S0, P1->S0, P2->S0, P3->S0, P4->S1, P5->S0
- P0->S0, P1->S0, P2->S0, P3->S0, P4->S1, P5->S1
- ...
- P0->S1, P1->S1, P2->S1, P3->S1, P4->S1, P5->S1
Notice that despite that the number of processes has not even doubled, the running time multiplied by 100! For comparison, I 've added the running time of the First Fit algorithm.
And it gets worse: for 12 processes and 4 servers, which are 4^12 combinations, it take more than 17 minutes:
What if we want to distribute 3000 processes over 1000 servers? With this kind of scalability, it will take too long. In fact, the brute force algorithm is useless.
Luckily, Drools Planner implements
several other optimization algorithms, which can handle such loads. If
you want to know more about them, take a look at the Drools Planner manual or come to my talk at JUDCon London (31 Oct - 1 Nov).
This article was originally posted on the Drools & jBPM blog.
Opinions expressed by DZone contributors are their own.
Comments