I likewise won't post an actual answer.

However conceptually you need to separate out figuring out what goes where from displaying it. The best solution for the first part is probably going to be to walk through all possible allocations of jobs to machines and then pick the best one. (I suggest recursion.)

FWIW I have not thought hard about this, but I don't know of a sub-exponential solution. I can improve the base, but not the fact of it being exponential.