Wait, this is very simple:
Always pick the server with the most slots open.
Only when no server has enough space to accomodate the next machine, but together they have enough space, should you apply a packing algorithm.
Always pick the server with the most slots open.
Only when no server has enough space to accomodate the next machine, but together they have enough space, should you apply a packing algorithm.
Let us imagine the following configuration.
We have 3 servers each of 4 slots, below is the state of each server (the state of a server is a set of VMs it's running)
[3], [2, 1] and [2].
Say we need to place a new 3-slot VM to our system. We'll pick the third server as less-loaded and try to accomodate the second server. Together they have enough space, but we can't provision the VM withour using all 3 servers. The solution here is
1) migrate a 1-slot VM from server 2 to server 1
2) migrate a 2-slot VM from server 2 to server 3
3) place the new VM to server 2
What would you say is more important: minimizing the amount of slots to move or the number of VM's?
I can imagine that, when you have a perfect fit i.e. a machine that has l slots open and a VM that takes l slots, putting the VM on that machine might prove a good idea. At least when moving VMs is not too cheap compared to the advantages of a homogeneous load.
Algorithm A: Always choose the server with the most slots free spreads the load most equally without moving VM's. (Assuming servers are equal in capacity. Minimizing load-balance is defined as minimizing the difference between highest loaded server and lowest loaded server.)
Proof: Given a VM to be placed, v, and a set of servers S of which server s' is has most slots free. Say picking s' to place v does not give the most optimal load-balance. Then there must be server with with more slots free then s', contradiction.
Algorithm B: Let S be a series of servers ordered by load (lowest number of free slots first). Put a new VM v on the first server s, on which v fits. This maximizes the initial number of VM's you can place without moving VM's, without prior knowledge.
Proof: Because we always try to fit each VM in the first server possible, we maximize the amount of consecutive space on the last server. Thus, without prior knowledge, this maximizes the number of VM's we can place.
I take it you like neither of these solutions. You want to compromise between the two solutions. Doing that right (there is not optimal in that sense) would depend on the scale difference between servers slots and space required by VM's. If VM's are small and servers big, you can safely go for load balance. If VM's are big and servers relatively small, you may go for B.
However if you have more information about the probability distribution of the number of slots in a VM, you could in theory do better than that.