Optimally assigning tasks to workers

Question

I've been working on a comprehensive build system that performs distributed builds on multiple machines for quite some time now. It correctly handles dependencies and seemed to scale reasonably well, so we've added more projects and more machines, but it looks like it could perform better.

The problem I have is one of resource allocation. I have a list of available machines and a list of projects I'd like to build, also each machine lists what software, OS, compiler version, etc... is installed and each project lists what it requires. When work needs to be assigned, I can run a database query that lists the possible assignments. Now I need to perform those assignments as effectively as possible.

The smallest example is two projects 1 and 2 with two machines A and B. Machine A can build either project but machine B can only build project 1. So I end up with a list of pairs (A,1), (A,2), (B,1). If I process the assignments in order, machine A builds project 1 and I have to wait until it finishes before I can build project 2. It perhaps would have been better to assign machine A to project 2 and machine B to project 1. But... machine A may be much faster than machine B, and not using machine B at all may be the right answer.

I'm sure this is the sort of 'operational research' problem that's been addressed many times before. I don't necessarily need an optimal solution... just an attempt at something better than I have - it seems I often end up with tasks queued and machines idle which a better allocation could have avoided. Any suggestions most welcome.

Answer 1

The problem you are trying to solve is equivalent to the classic Job Shop Scheduling problem. Finding an optimal schedule is NP-hard.

People have invented lots of heuristics to generate schedules, but which ones are good is highly problem-dependent.

A couple of common heuristics are:

• Schedule the shortest task first.
• Schedule the most highly constrained task first, e.g., pick the task that can run on the fewest machines first.