Tuesday, November 1, 2011

Multi-Processor Scheduling Problem

Problem: Give a multi-processor machine with n processors and m jobs, how to make a scheduling that has the shortest finish time. Each job may take different amount of time to process.

Solution: There are also some variants to this problem, like putting m integers to n buckets. The solution to this problem can be based on some heuristics and is called LPT algorithm. Attention: this is a greedy approach which is a sub-optimal solution, not an optimal solution.
  • Basically we first sort the job based on their process time.
  • Choose the job with the longest process time among the current unprocessed jobs and put it into a machine which has the earliest finish time so far.
  • Repeat the above steps until all jobs are assigned.
  • The complexity is O(m*logm+m*logn+n).

4 comments:

  1. why m*logn has been added to the complexity ??

    ReplyDelete
    Replies
    1. m*logm is for sorting all the jobs based on their process time.

      m*logn is for finding a machine which has the earliest finish time. In order to achieve this, we need a min-heap (or priority queue). Each round, we pick the machine that finishes earliest. This operation costs logn. Since there are m jobs, for each job, we need to do such operation. Thus the total is m*logn.

      Delete
    2. ok i got it .. but i guess you should also include time complexity for building min-heap for n processors which is n*logn ....right????

      Delete
    3. if you insert element one by one, the cost of building a heap is (O)nlogn. However, optimal approach takes only (o)n to build a heap. Please see http://en.wikipedia.org/wiki/Binary_heap.

      Delete