A task/job scheduling problem

14,706

Solution 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.

Solution 2

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.

Share:
14,706

Related videos on Youtube

yanjiang qian
Author by

yanjiang qian

a engineer from China ...

Updated on June 04, 2022

Comments

  • yanjiang qian
    yanjiang qian over 1 year

    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.

  • Christian Severin
    Christian Severin about 9 years
    Actually this isn't bin packing, this is a job shop scheduling problem: en.wikipedia.org/wiki/Job_Shop_Scheduling

Related