Advertisements
Advertisements
Question
A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the time each man would take to perform each task is given below:
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 8 | 26 | 17 | 11 |
| Q | 13 | 28 | 4 | 26 | |
| R | 38 | 19 | 18 | 15 | |
| S | 9 | 26 | 24 | 10 | |
How should the tasks be allocated to subordinates so as to minimize the total manhours?
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.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 18 | 9 | 3 |
| Q | 9 | 24 | 0 | 22 | |
| R | 23 | 4 | 3 | 0 | |
| S | 0 | 17 | 15 | 1 | |
Step 2: Select the smallest element in each column and subtract this from all the elements in its column.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 14 | 9 | 3 |
| Q | 9 | 20 | 0 | 22 | |
| R | 23 | 0 | 3 | 0 | |
| S | 0 | 13 | 15 | 1 | |
Step 3: (Assignment)
Examine the rows with exactly one zero Mark the zero by □. Mark other zeros in its row by X.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 14 | 9 | 3 |
| Q | 9 | 20 | 0 | 22 | |
| R | 23 | 0 | 3 | 0 | |
| S | 0 | 13 | 15 | 1 | |
Step 4: Now examine the columns with exactly one zero. Mark the zero by □. Mark other zeros in its row by X.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 14 | 9 | 3 |
| Q | 9 | 20 | 0 | 22 | |
| R | 23 | 0 | 3 | 0 | |
| S | 0 | 13 | 15 | 1 | |
Step 5: Cover all the zeros of table 4 with three lines, since three assignments were made check (✓) row S since it has no assignment.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 14 | 9 | 3 |
| Q | 9 | 20 | 0 | 22 | |
| R | 23 | 0 | 3 | 0 | |
| ✓ | S | 0 | 13 | 15 | 1 |
Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in table 5.
Take the smallest element.
This is 1 (one) our case.
By subtracting 1 from the uncovered cells.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 14 | 9 | 3 |
| Q | 10 | 20 | 0 | 22 | |
| R | 24 | 0 | 3 | 0 | |
| S | 0 | 12 | 14 | 0 | |
[Adding 1 to elements (Q, S, R) that line at the intersection of two lines]
Step 7: Go to step 3 and repeat the procedure until you arrive at an optimal assignment.
Step 8: Determine an assignment.
| Tasks | |||||
| 1 | 2 | 3 | 4 | ||
| Subordinates | P | 0 | 14 | 9 | 3 |
| Q | 10 | 20 | 0 | 22 | |
| R | 24 | 0 | 3 | 0 | |
| S | 0 | 12 | 14 | 0 | |
Thus all the four assignment have been made.
The optimal assignment schedule and total time is
| Subordinates | Tasks | Time |
| P | 1 | 8 |
| Q | 3 | 4 |
| R | 2 | 19 |
| S | 4 | 10 |
| Total | 41 | |
The optimum time (minimum) = 41 Hrs.
APPEARS IN
RELATED QUESTIONS
Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`
A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job for each machine is given in the following table:
| Jobs | Machines (Processing Cost in ₹) |
|||
| P | Q | R | S | |
| A | 31 | 25 | 33 | 29 |
| B | 25 | 24 | 23 | 21 |
| C | 19 | 21 | 23 | 24 |
| D | 38 | 36 | 34 | 40 |
Find the optimal assignment to minimize the total processing cost.
Five wagons are available at stations 1, 2, 3, 4, and 5. These are required at 5 stations I, II, III, IV, and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?
| I | II | III | IV | V | |
| 1 | 10 | 5 | 9 | 18 | 11 |
| 2 | 13 | 9 | 6 | 12 | 14 |
| 3 | 3 | 2 | 4 | 4 | 5 |
| 4 | 18 | 9 | 12 | 17 | 15 |
| 5 | 11 | 6 | 14 | 19 | 10 |
Choose the correct alternative :
In an assignment problem if number of rows is greater than number of columns then
In an assignment problem, if number of column is greater than number of rows, then a dummy column is added.
If the given matrix is ______ matrix, the assignment problem is called balanced problem
Give mathematical form of Assignment problem
Assign four trucks 1, 2, 3 and 4 to vacant spaces A, B, C, D, E and F so that distance travelled is minimized. The matrix below shows the distance.
| 1 | 2 | 3 | 4 | |
| A | 4 | 7 | 3 | 7 |
| B | 8 | 2 | 5 | 5 |
| C | 4 | 9 | 6 | 9 |
| D | 7 | 5 | 4 | 8 |
| E | 6 | 3 | 5 | 4 |
| F | 6 | 8 | 7 | 3 |
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 |
A job production unit has four jobs P, Q, R, S which can be manufactured on each of the four machines I, II, III and IV. The processing cost of each job for each machine is given in the following table :
| Job | Machines (Processing cost in ₹) |
|||
| I | II | III | IV | |
| P | 31 | 25 | 33 | 29 |
| Q | 25 | 24 | 23 | 21 |
| R | 19 | 21 | 23 | 24 |
| S | 38 | 36 | 34 | 40 |
Complete the following activity to find the optimal assignment to minimize the total processing cost.
Solution:
Step 1: Subtract the smallest element in each row from every element of it. New assignment matrix is obtained as follows :
| Job | Machines (Processing cost in ₹) |
|||
| I | II | III | IV | |
| P | 6 | 0 | 8 | 4 |
| Q | 4 | 3 | 2 | 0 |
| R | 0 | 2 | 4 | 5 |
| S | 4 | 2 | 0 | 6 |
Step 2: Subtract the smallest element in each column from every element of it. New assignment matrix is obtained as above, because each column in it contains one zero.
Step 3: Draw minimum number of vertical and horizontal lines to cover all zeros:
| Job | Machines (Processing cost in ₹) |
|||
| I | II | III | IV | |
| P | 6 | 0 | 8 | 4 |
| Q | 4 | 3 | 2 | 0 |
| R | 0 | 2 | 4 | 5 |
| S | 4 | 2 | 0 | 6 |
Step 4: From step 3, as the minimum number of straight lines required to cover all zeros in the assignment matrix equals the number of rows/columns. Optimal solution has reached.
Examine the rows one by one starting with the first row with exactly one zero is found. Mark the zero by enclosing it in (`square`), indicating assignment of the job. Cross all the zeros in the same column. This step is shown in the following table :
| Job | Machines (Processing cost in ₹) |
|||
| I | II | III | IV | |
| P | 6 | 0 | 8 | 4 |
| Q | 4 | 3 | 2 | 0 |
| R | 0 | 2 | 4 | 5 |
| S | 4 | 2 | 0 | 6 |
Step 5: It is observed that all the zeros are assigned and each row and each column contains exactly one assignment. Hence, the optimal (minimum) assignment schedule is :
| Job | Machine | Min.cost |
| P | II | `square` |
| Q | `square` | 21 |
| R | I | `square` |
| S | III | 34 |
Hence, total (minimum) processing cost = 25 + 21 + 19 + 34 = ₹`square`
