We are given a list of jobs, along with the number of minutes it would take to c

Question

We are given a list of jobs, along with the number of minutes it would take to complete each job. Our goal is to schedule these jobs to minimize the average completion time. Example: Consider three jobs, job A that takes 50 minutes to complete, B that takes 20 minutes, and C that takes 35 minutes to complete. If we schedule the jobs in the order A, B, C, then job A completes at time 50, job B completes at time 70. and job C completes at time 105. Then average competition time is 50+70+105/3 = 75. Note that this ordering is not optimal. Give the pseudocode for a greedy algorithm that gives an optimal solution to this problem. Justify your answer. Analyze the running time of your algorithm.

Explanation / Answer

Pseudocode:

Step 1:We want to minimize average time.so sort all jobs according to minimum to maximum completion time.

Step 2:Let there are n task t1,t2,.......tn

   and c1,c2,.......cn be completion time.

Step 3:Find avearge compltion time cavg=(c1+c2....cn)/n

  c1 =t1, c2 = (t1 + t2),c3 = (t1 + t2+t3)....................................

Hence cavg = (t1 + (t1 + t2) + … + (t1 + t2 + … + tn)) / n

Hence we get minimum completion time as we have already sorted time.

Run time Complexity:

Best case will be O(nlogn) as sorting of processing time takes  O(nlogn) by merge sort.We can use other sort also but it will affect complexity.Best sorting is merge sort.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---