Learn / Library / Brainteasers

Single machine job order

BrainteasersMedium

One machine must process $4$ jobs with durations $4$ , $1$ , $3$ and $2$ hours. It starts at time $0$ , runs without gaps and handles one job at a time. Choose the order that minimizes the sum of the completion times of the $4$ jobs. What is that minimum sum, in hours?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Early finishes count for every job waiting behind, so think about which job should go first.

Solution

Running the shortest jobs first minimizes the total waiting, because each job's duration is counted in the completion times of all later jobs.
The best order is therefore durations $1, 2, 3, 4$ .
The completion times are $1, 3, 6, 10$ .
Their sum is $1 + 3 + 6 + 10 = 20$ .
The answer is $20$ .

Answer: $20$

Next question Back to the library