Task / task planning task

Question

I have a problem with a task / task, and I would like to find effective algorithms for solving it.

Say there are workers. Each employee can perform different tasks / tasks. The following example may be clear:

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

Now we have a list of tasks that need to be completed. For example, the list looks something like this: T1, T3, T5

There are some limitations:

• Each task should be performed by one worker.
• Several tasks can be performed simultaneously.
• But a worker can only perform one task at a time. (He / she is unavailable until the assignment is completed).

In the above example, we might have a schedule like this:

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

As you can see, the above schedule is not optimal. Because T5 has to wait for working C to complete T3. Better is the following solution:

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

Because there is no expectation.

Now suppose that I know the matrix of work tasks (which worker can perform which tasks). Tasks will be carried out one by one, but I don’t know what it will be. . I am invited to create a scheduler that will automatically find a loafer for each upcoming task. And when, finally, all tasks are completed, the minimum waiting time.

Therefore, I need an algorithm for this scheduler. I do not want to reinvent the wheel if the perfect wheel already exists. Can anyone help?

Thanks.

Answer 1

It looks like you are looking for the "Bin Packing" algorithm -

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

The general problem of container packaging, very similar to what you have formulated, is NP-Hard, so you can forget about the optimal solution if your input size is more than trivial.

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

Answer 2

Algorithms that work at the input, which are unknown in advance, but enter into "how you go," are called on-line algorithms . Naturally, they are suboptimal. They are measured in that worse than the optimal algorithm, no more than a constant factor (for example, if the best solution (which is not operational, i.e. has all the input up), takes steps X, your online one should not take more than k * X steps, the less k, the better, of course).

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

One idea that can help you is to assemble an affordable worker using the smallest list of tasks, while retaining more “diverse” workers for future tasks.