Four automobiles have entered Bubba’s Repair Shop for various types of work, ran

Question

Four automobiles have entered Bubba’s Repair Shop for various types of work, ranging from a transmission overhaul to a brake job. The experience level of the mechanics is quite varied, and Bubba would like to minimize the time required to complete all of the jobs. He has estimated the time in minutes for each mechanic to complete each job. Billy can complete job 1 in 400 minutes, job 2 in 90 minutes, job 3 in 60 minutes, and job 4 in 120 minutes. Taylor will finish job 1 in 650 minutes, job 2 in 120 minutes, job 3 in 90 minutes, and job 4 in 140 minutes. Mark will finish job 1 in 480 minutes, job 2 in 120 minutes, job 3 in 80 minutes, and job 4 in 180 minutes. John will complete job 1 in 500 minutes, job 2 in 110 minutes, job 3 in 90 minutes, and job 4 in 150 minutes. Each mechanic should be assigned to just one of these jobs. What is the minimum total time required to finish the four jobs? Who should be assigned to each job?

Explanation / Answer

This can be solved using Assignment model:

Using the Hungarian Method,

Step 1. Subtract the smallest entry in each row from all the entries of its row.

Step 2. Subtract the smallest entry in each column from all the entries of its column.

Step 3. Draw lines through appropriate rows and columns so that all the zero entries of the cost matrix are covered and the minimum number of such lines is used.

Step 4. Test for Optimality: (i) If the minimum number of covering lines is n, an optimal assignment of zeros is possible and we are finished. (ii) If the minimum number of covering lines is less than n, an optimal assignment of zeros is not yet possible. In that case, proceed to

Step 5. Step 5. Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column.Return to step 3.

Now from above we can see that minimum number of lines covering all zeros are 4, and we are in position to assign the jobs to each worker.

Billy will be assigned job1(400 min),

Taylor will be assigned job4(140 min),

Mark will be assigned job3(80 min),

John will be assigned job2(110)

Hence minimum time of repair will be=400+140+80+110=730 Minutes

Job1 Job 2 job 3 job4 Billy 400 90 60 120 Taylor 650 120 90 140 Mark 480 120 80 180 john 500 110 90 150

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.