Five men are available to do five different jobs. From past records, the time…
2014
Five men are available to do five different jobs. From past records, the time (in hours) that each man takes to do each job is known and is given in the following table :
Find out the minimum time required to complete all the jobs.
- A.
5
- B.
11
- C.
13
- D.
15
Attempted by 8 students.
Show answer & explanation
Correct answer: C
Solution overview: find an assignment of men to jobs that minimizes the total time.
Observation:
Each man can do only one job and each job must be done by one man.
A quick lower bound is the sum of the smallest time in each job column: 2 (Job I) + 2 (Job II) + 2 (Job III) + 3 (Job IV) + 1 (Job V) = 10. The true minimal total cannot be less than 10.
Constructing a feasible minimal assignment (inspection/Hungarian method):
Assign P to Job III: time = 2.
Assign S to Job II: time = 2.
Assign R to Job IV: time = 3.
Assign T to Job I: time = 5.
Assign Q to Job V: time = 1.
Total time = 2 + 2 + 3 + 5 + 1 = 13.
Why this is minimal (brief justification):
Although the sum of column minima is 10, several of those minima come from the same person (for example, the minima for Job I and Job III are both from the same man), so they cannot all be used simultaneously.
Testing feasible assignments or applying the Hungarian method shows that no assignment gives a total less than 13, and the example above achieves 13, so it is optimal.