= Solution
Serve customers in \b[<nondecreasing> service time], with ties broken arbitrarily. The objective in the source includes each customer's own service time, so these are completion times, not only delays before service begins. If the order is $\sigma$, then
$$
T=\sum_{j=1}^{n}(n-j+1)t_{\sigma(j)}.
$$
To prove optimality, consider adjacent service times $a>b$ after an elapsed time $P$. Their contributions before an exchange are $(P+a)+(P+a+b)$; after the exchange they are $(P+b)+(P+b+a)$. The total decreases by $a-b>0$. Earlier customers are unaffected, and later customers begin after the same combined duration $a+b$ as before, so their completion times are unchanged.
Repeatedly exchanging adjacent inversions reaches a <nondecreasing> order without increasing the objective. Hence that order is optimal. Sorting takes \b[$O(n\log n)$] time in a <comparison model>, followed by a linear traversal to produce the order or compute the total. Equal service times give zero exchange difference and do not affect optimality. If waiting time were instead defined before service, subtracting the order-independent total service time would give the same optimal order.
Back to article page
