A mine workshop needs to assign 4 jobs to 4 service engineers. The cost for performing a job by an individual service engineer is given. A typical job can be assigned to only one service engineer. If the service engineer S1 cannot perform the job J3, and S3 cannot perform the job J4, the optimal cost for completion of jobs is . (answer in integer)

Service Engineer J1 J2 J3 J4
S1 50 50 --- 20
S2 70 40 20 70
S3 90 30 50 ---
S4 70 20 60 30

Question

The primary purpose of mine ventilation is to:

Answer 1

With only 4 jobs and 4 engineers, and just two combinations ruled out, it is faster here to reason directly about the cheapest way to cover all four jobs than to run the full Hungarian tableau. The goal is one engineer per job, every job covered, lowest total cost.

Look for the standout cheap cells. Scanning the table, J2 is cheapest for S4 (20) and for S3 (30). J1 is cheapest for S1 (50). J3 is cheapest for S2 (20). J4 is cheapest for S1 (20) and S4 (30).
Give S2 to J3. S2's cost of 20 on J3 is the lowest value S2 offers anywhere, and the only engineer who could beat it on J3, S1, is blocked from that job. So S2-J3 = 20 is locked in.
Check the branch where S4 takes J2. S4-J2 = 20 is the single lowest number left in the table once J3 is taken. But S3 cannot do J4, so with J2 gone S3 must take J1 at 90, leaving S1 to take J4 at 20. Total: 20+20+90+20 = 150.
Check the branch where S3 takes J2 instead. S3-J2 = 30. That frees up J4 for S4 at 30, and leaves S1 to take J1 at 50. Total: 30+30+50+20 = 130.
Compare the two branches. 130 is lower than 150, so S3 taking J2 (not S4) is the better choice.

Checking every other feasible pairing given the two forbidden cells, none beats 130. The winning combination is S1-J1 (50), S2-J3 (20), S3-J2 (30), S4-J4 (30).

Let's summarize:

S2 must take J3, since that is by far its cheapest option and S1 cannot use J3 to compete for it.
Testing S1, S3 and S4 against J1, J2 and J4 shows S1-J1, S3-J2, S4-J4 beats every other pairing.
The minimum total cost works out to 130.

So the optimal cost for completing all four jobs is 130.

Answer 2

With only 4 jobs and 4 engineers, and just two combinations ruled out, it is faster here to reason directly about the cheapest way to cover all four jobs than to run the full Hungarian tableau. The goal is one engineer per job, every job covered, lowest total cost.

Look for the standout cheap cells. Scanning the table, J2 is cheapest for S4 (20) and for S3 (30). J1 is cheapest for S1 (50). J3 is cheapest for S2 (20). J4 is cheapest for S1 (20) and S4 (30).
Give S2 to J3. S2's cost of 20 on J3 is the lowest value S2 offers anywhere, and the only engineer who could beat it on J3, S1, is blocked from that job. So S2-J3 = 20 is locked in.
Check the branch where S4 takes J2. S4-J2 = 20 is the single lowest number left in the table once J3 is taken. But S3 cannot do J4, so with J2 gone S3 must take J1 at 90, leaving S1 to take J4 at 20. Total: 20+20+90+20 = 150.
Check the branch where S3 takes J2 instead. S3-J2 = 30. That frees up J4 for S4 at 30, and leaves S1 to take J1 at 50. Total: 30+30+50+20 = 130.
Compare the two branches. 130 is lower than 150, so S3 taking J2 (not S4) is the better choice.

Checking every other feasible pairing given the two forbidden cells, none beats 130. The winning combination is S1-J1 (50), S2-J3 (20), S3-J2 (30), S4-J4 (30).

Let's summarize:

S2 must take J3, since that is by far its cheapest option and S1 cannot use J3 to compete for it.
Testing S1, S3 and S4 against J1, J2 and J4 shows S1-J1, S3-J2, S4-J4 beats every other pairing.
The minimum total cost works out to 130.

So the optimal cost for completing all four jobs is 130.

Show Hint

Correct Answer: 130

Solution and Explanation

Top Questions on Assignment Problem

Questions Asked in GATE MN exam