= Shortest-processing-time order
{title2=$\min_\sigma\sum_{j=1}^n(n-j+1)t_{\sigma(j)}$}
On one server with all jobs initially available, nonnegative fixed durations and no <sequence>-dependent setup, a <nondecreasing>-duration order minimizes the sum of completion times. Swapping adjacent durations $a>b$ reduces their combined contribution by $a-b$ and changes no later completion time, because their total duration is unchanged. Repeated adjacent exchanges remove every inversion. The sum of pre-service waiting times has the same optimum, differing by the fixed total duration.
Back to article page
