A task/job scheduling problem

Question

I have a task/job scheduling problem and I would like to find preferably efficient algorithms to solve it.

Let's say there are some workers. Every worker is able to do a different set of tasks/jobs. The following example may make it clear:

  Worker A (can do): T2, T3
  Worker B         : T1, T3, T4
  Worker C         : T3, T5

Now we have a list of tasks which must be done. For example, the list is something like: T1, T3, T5

There's some constraints:

1. Each task must be taken by one worker
2. Several tasks can be taken concurrently
3. But a worker can do only one task at the same time. (He/she is not available until finish the task)

For the above example, we may have a schedule like this:

  T1 --> Worker B
  T3 --> Worker C   T5 --> Worker C

As you may noticed, the above schedule is not optimal. Because T5 has to wait worker C to finish T3. The following solution is better:

  T1 --> Worker B
  T3 --> Worker A
  T5 --> Worker C

Because there's no wait.

Now suppose that I know the the worker-tasks matrix (what worker can do what tasks). The tasks will come one by one, but don't know what it will be. I am asked to design a scheduler that automatically find an idle worker for every coming task. And when finally all the tasks are done, there's a minimum waiting time.

So I need an algorithm for this scheduler. I don't want to reinvent the wheel if the perfect wheel already exists. Can any one help?

Thanks.

Answer 1

It sounds like you're looking for a "Bin Packing" algorithm -

http://en.wikipedia.org/wiki/Bin_packing

The general bin packing problem, very similar to what you phrased, is NP-Hard so you can forget about an optimal solution if your input size is more than trivial.

What you can find is a solution that is guaranteed not to be too far from the optimal solution, usually my some factor. That wikipedia article is a good place to start.