Job queue optimization algorithms

Question

We have an application that requires assignment of jobs to resources. The resources have a number of attributes that define their suitability to a particular job -- some are preferences, some are hard constraints (all of the membership variety, e.g. "resource A is suited to jobs with color X, Y, or Z".

Resources have a cost associated with them (the duration they spend on-line). We have the ability to recruit resources -- this takes a variable amount of time. We can recruit for a fixed interval of time.

To give an idea of scale: There will be about 20 resources at any given time, 100 outstanding jobs. Completion of jobs takes 5-15 seconds. Recruiting a resource takes about 1-2 minutes, and we can recruit from 1-30 minutes of time (rerecruiting is allowed). We don't have much heads-up on jobs being submitted, maybe a few seconds.

The goal is completion of jobs with lowest cost (resource usage) for a given average latency (job completion time).

I'd appreciate pointers to algorithms, software libraries, or approaches to solving this problem.

Answer 1

Might want to look into the knapsack problem or the bin packing problem as those are similar in principle to what you are trying to do here.

In your problem description you mention that the goal is the completion of jobs with the lowest latency. If that is actually your only goal, then the solution is simple - hire all available resources. Many of them will be idle much of the time, but it pretty much guarantees the lowest possible latency.

I suspect that your real goal though is to minimize both latency and idle resources as much as possible, so there will always be some tradeoff between latency and wasted resources in play here.