A task/job scheduling problem

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.

Algorithms operating on input that is not known upfront but is coming in "as you go" are called on-line algorithms. They are only sub-optimal, naturally. They are measured by being worse than the optimal algorithm not more than by a constant factor (e.g. if the best solution (which is not on-line, i.e. has the whole input upfront) takes X steps, your on-line one should take not more than k*X steps, the smaller the k the better of course).

In your case the requirement is not clear - "minimum waiting time" compared to what?

One idea that may help you is to pick up an available worker with the smallest task list, saving the more "diverse" workers for future tasks.

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.