figure schedule # (optimal(time units) in in and in the average completion time is better schedulewhich yields mean completion time of is shown in figure the schedule given in figure is arranged by shortest job first we can show that this will always yield an optimal schedule let the jobs in the schedule be ji ji jin the first job finishes in time ti the second job finishes after ti ti and the third job finishes after ti ti ti from thiswe see that the total costcof the schedule is cn ( )tik ( = ( = tik tik ( = notice that in equation ( )the first sum is independent of the job orderingso only the second sum affects the total cost suppose that in an ordering there exists some such that tix tiy then calculation shows that by swapping jix and jiy the second sum increasesdecreasing the total cost thusany schedule of jobs in which the times are not monotonically nondecreasing must be suboptimal the only schedules left are those in which the jobs are arranged by smallest running time firstbreaking ties arbitrarily this result indicates the reason the operating system scheduler generally gives precedence to shorter jobs multiprocessor case we can extend this problem to the case of several processors again we have jobs jn with associated running times tn and number of processors we will assume without loss of generality that the jobs are orderedshortest running time first as an examplesuppose and the jobs are as shown in figure figure shows an optimal arrangement to minimize mean completion time jobs and are run on processor processor handles and and processor runs the remaining jobs the total time to completion is for an average of the algorithm to solve the multiprocessor case is to start jobs in ordercycling through processors it is not hard to show that no other ordering can do betteralthough if the number of processorspevenly divides the number of jobsnthere are many optimal orderings this is obtained byfor each < /pplacing each of the jobs jip+ through ( + ) on different processor in our casefigure shows second optimal solution even if does not divide exactlythere can still be many optimal solutionseven if all the job times are distinct we leave further investigation of this as an exercise