I wonder how good random placement would work.
IE :
Create a number of compositions where you put everything in random locations.
Discard any compositions with overlaps.
Keep the ones with the smallest wasted space or whatever.
Also, this might be a good application for AI.