Advertisements
Advertisements
Question
Three jobs A, B and C one to be assigned to three machines U, V and W. The processing cost for each job machine combination is shown in the matrix given below. Determine the allocation that minimizes the overall processing cost.
| Machine | ||||
| U | V | W | ||
| Jobs | A | 17 | 25 | 31 |
| B | 10 | 25 | 16 | |
| C | 12 | 14 | 11 | |
(cost is in ₹ per unit)
Advertisements
Solution
Here the number of rows and columns are equal.
∴ The given assignment problem is balanced.
Step 1: Select the smallest element in each row and subtract this from all the elements in its row.
| Machine | ||||
| Jobs | U | V | W | |
| A | 2 | 0 | 16 | |
| B | 0 | 15 | 6 | |
| C | 1 | 3 | 0 | |
Look for atleast one zero in each row and each column.
Here each and every row and columns having exactly one zero No need step 2 go to step 3.
Step 3:
| Machine | ||||
| Jobs | U | V | W | |
| A | 2 | 0 | 16 | |
| B | 0 | 15 | 6 | |
| C | 1 | 3 | 0 | |
Mark the zero by □ Mark other zeros in its column by X.
Since each row and each column contains exactly one assignment, all the three machine have been assigned a job.
| Job | Machine | Cost |
| A | V | 15 |
| B | U | 10 |
| C | W | 11 |
| Total Cost | 46 | |
The Optimal assignment (minimum) cost = 46
APPEARS IN
RELATED QUESTIONS
Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`
The assignment problem is said to be unbalance if ______
Fill in the blank :
When an assignment problem has more than one solution, then it is _______ optimal solution.
State whether the following is True or False :
It is not necessary to express an assignment problem into n x n matrix.
Solve the following problem :
A plant manager has four subordinates, and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. This estimate of the time each man would take to perform each task is given in the effectiveness matrix below.
| I | II | III | IV | |
| A | 7 | 25 | 26 | 10 |
| B | 12 | 27 | 3 | 25 |
| C | 37 | 18 | 17 | 14 |
| D | 18 | 25 | 23 | 9 |
How should the tasks be allocated, one to a man, as to minimize the total man hours?
State whether the following statement is True or False:
In assignment problem each worker or machine is assigned only one job
Choose the correct alternative:
Number of basic allocation in any row or column in an assignment problem can be
Choose the correct alternative:
North – West Corner refers to ______
A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers are given in the following distance matrix.
| a | b | c | d | e | |
| A | 160 | 130 | 175 | 190 | 200 |
| B | 135 | 120 | 130 | 160 | 175 |
| C | 140 | 110 | 155 | 170 | 185 |
| D | 50 | 50 | 80 | 80 | 110 |
| E | 55 | 35 | 70 | 80 | 105 |
How should the cars be assigned to the customers so as to minimize the distance travelled?
A department store has four workers to pack goods. The times (in minutes) required for each worker to complete the packings per item sold is given below. How should the manager of the store assign the jobs to the workers, so as to minimize the total time of packing?
| Workers | Packing of | |||
| Books | Toys | Crockery | Cutlery | |
| A | 3 | 11 | 10 | 8 |
| B | 13 | 2 | 12 | 12 |
| C | 3 | 4 | 6 | 1 |
| D | 4 | 15 | 4 | 9 |
