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

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.