Sunday, October 24, 2010

Planning problems in the cloud

Everybody is talking about the cloud these days, but it too suffers from planning problems.
So I created a new example this weekend for Drools Planner to deal with those planning problems: CloudBalance (available on trunk).

The problem is simple: there are a number of computers and a number of processes, which we want to run on the computers. Every computer should be able to handle the sum of the minimal hardware requirements of all its processes.

Here's part of an example with 100 computers and 200 processes. If I only use a deterministic algorithm, which plans the biggest processes first, I get this unfeasible planning after 1.6 seconds:



As you can see, some processes don't meet their minimal CPU requirements.
On the same example, if I continue planning with tabu search on that original solution, I get this feasible planning after 3.4 seconds:



All processes meet their minimal hardware requirements. And if we give it more time, it will try to shut down computers and save power costs, while still meeting the minimal hardware requirements of all processes.