Brute force approach?

Question

A service engineer is given three machines to repair. Machine A requires 2 hours, Machine B requires 3 hours while Machine C requires 1 hour. He has been given strict instructions to minimise the "down time" summed over all the machines. The "down time" is defined to be the amount of time the machine remains unrepaired.

i) Using the brute force approach, find the best order of doing the repairs.

ii) If the number of machines to repair is generalised to N, state the time complexity of the brute force method.

iii) Propose a greedy method to solve the problem. State and justify whether the greedy method is reliable.

Answer 1

i)

order | hours

ABC | 2 + (2 + 3) + (2 + 3 + 1) = 13 hrs

ACB | 2 + (2 + 1) + (2 + 1 + 3) = 11 hrs

BAC | 3 + (3 + 2) + (3 + 2 + 1) = 14 hrs

BCA | 3 + (3 + 1) + (3 + 1 + 2) = 13 hrs

CAB | 1 + (1 + 2) + (1 + 2 + 3) = 10 hrs

CBA | 1 + (1 + 3) + (1 + 3 + 2) = 11 hrs

ii) The solution time complexity for N machines by brute force is proportional to (N!)^3 if the repair time increases by 1 hr with each machine.  If there are duplicate repair times the solution time complexity is reduced considerably, but estimating it is not possible without knowing the times and number of units involved at each time.

iii) The "greedy" solution is to repair the machines in the order of their repair times.  This solution is reliable because it can be shown to be unique.