Need help with Algorithm

[SONYFX]

I need help! Can anyone tell me in words?



Suppose you are given a set S ={a1, a2 ,.......an} of tasks,
Task ai requires Pi ( pi ={p1, p2,......pn} )units of processing time to complete, once it has started.

You have one computer on which to run these tasks, and the computer can run only one task at a time.

Let ci ( ci ={c1, c2,......cn} )be the completion time of task ai , that is, the time
at which task ai completes processing. Goal is to minimize the average completion time

For example, suppose there are two tasks, a1 and a2 , with p1 = 3 andp2 = 5,
and consider the schedule in which a2 runsfirst, followed by a1 .

Then c2 = 5, c1 = 8, and the average completion time is (5 + 8)=2 = 6.5

(a) Give an algorithm that schedules the tasks so as to minimize the average completion time. Each
task must run non-preemptively, that is, once task a i is started it must run continuously for p i
units of time.

 

[uart]

The solution is very simple. You just need to schedule the tasks in order of increasing exectution time. By doing the quickest tasks firsts you get more tasks completed earlier. This is pretty much self evident, (meaning it is so simple as to not require formal proof), though I'm sure I could make a formal proof if I really wanted to.

 

[Matthias99]

This is also not the place to get answers to your CS class homework. However, uart is correct.

 

[dnuggett]

Originally posted by: Matthias99
This is also not the place to get answers to your CS class homework. However, uart is correct.

Amen about the homework....