Question

Assume that you have a set of jobs where each has only a processing time that you need to schedule on a single machine.

Explain how you should schedule the jobs to minimize the sum of completion (finish) times. Write a proof that your schedule is optimal.

Answer 1

Given that we have all the process ready means there arrival time is same let's say 0 for simplicity now the algorithm that i will use to make sure that the sum of finish time is minimum is SHORTEST JOB FIRST . In Normal Cases this algorithm is impossible to use because we can't find the processing time of a process that is going to be scheduled in the future right,we cannot predict future ,thus we can't use this algorithm for scheduling in normal case but this is an ideal case we already have all the process with their processing time.

In SHORTEST JOB FIRST algorithm we schedule that process which has that minimum processing time of all the processes at that given time ,but in our case we have already have all the process ready so basically we find the minimum of all the process and schedule it and then remove the process from list and repeat till we have all our processes scheduled.

Now why this algorithm gives minimum sum of finish time,The key principle is how you schedule the process if you schedule a process then all the remaining process have to wait that long which in turn increase their finish time by that amount but if we schedule smaller process first then all the remaining process will have to wait for less time hence decrease in total finish time . The more our scheduling will be close to sorted (ascending) less will be our waiting time hence less finish time .If we schedule our processes in descending order then it give us maximum possible sum of finish time that's why this algorithm works.

If you have any doubt comment.

For test case , we take processes with processing time 2,4,5,1,1 now here we see that two process have same processing time
To break the tie we use first come first serve
But both arrive at Same time hence we can schedule any of the two.
Now sort the process in ascending order
1,1,2,4,5 now calculating the finish time of all the process one by one
1,2,4,8,13 respectively for each process
Now total finish time is 28 units. This is the minimum finish time obtainable for the above scheduling.

If we schedule in descending order then we get 49 unit which is the maximum possible sum of finish time.

If this answer helps you please like my answer,thank you.