Advertisements
Advertisements
Question
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 |
Advertisements
Solution
Since the number of columns is less than the number of rows, the given assignment problem is unbalanced one.
To balance it, introduce two dummy columns with all the entries zeros.
The revised assignment problem is
| Trucks | |||||
| 1 | 2 | 3 | 4 | ||
| A | 4 | 7 | 3 | 7 | |
| B | 8 | 2 | 5 | 5 | |
| Vacant Spaces | C | 4 | 9 | 6 | 9 |
| D | 7 | 5 | 4 | 8 | |
| E | 6 | 3 | 5 | 4 | |
| F | 6 | 8 | 7 | 3 | |
Here only 4 tasks can be assigned to 4 vacant spaces.
Step 1: It is not necessary, since each row contains zero entry. Go to step 2.
| Trucks | |||||||
| 1 | 2 | 3 | 4 | d1 | d2 | ||
| A | 0 | 5 | 0 | 4 | 0 | 0 | |
| B | 4 | 0 | 2 | 2 | 0 | 0 | |
| Vacant Spaces | C | 0 | 7 | 3 | 6 | 0 | 0 |
| D | 3 | 3 | 1 | 5 | 0 | 0 | |
| E | 2 | 1 | 2 | 1 | 0 | 0 | |
| F | 2 | 6 | 4 | 0 | 0 | 0 | |
Step 3: (Assignment)
Since each row contains more than one zeros. Go to step 4.
Step 4: Examine the columns with exactly one zero, mark the zero by □ Mark other zeros in its rows by X.
| Trucks | |||||||
| 1 | 2 | 3 | 4 | d1 | d2 | ||
| A | 0 | 5 | 0 | 4 | 0 | 0 | |
| B | 4 | 0 | 2 | 2 | 0 | 0 | |
| Vacant Spaces | C | 0 | 7 | 3 | 6 | 0 | 0 |
| D | 3 | 3 | 1 | 5 | 0 | 0 | |
| E | 2 | 1 | 2 | 1 | 0 | 0 | |
| F | 2 | 6 | 4 | 0 | 0 | 0 | |
| Trucks | |||||||
| 1 | 2 | 3 | 4 | d1 | d2 | ||
| A | 0 | 5 | 0 | 4 | 0 | 0 | |
| B | 4 | 0 | 2 | 2 | 0 | 0 | |
| Vacant Spaces | C | 0 | 7 | 3 | 6 | 0 | 0 |
| D | 3 | 3 | 1 | 5 | 0 | 0 | |
| E | 2 | 1 | 2 | 1 | 0 | 0 | |
| F | 2 | 6 | 4 | 0 | 0 | 0 | |
Step 5: Here all the four assignments have been made we can assign d1 for D then we will get d2 for E.
| Trucks | |||||||
| 1 | 2 | 3 | 4 | d1 | d2 | ||
| A | 0 | 5 | 0 | 4 | 0 | 0 | |
| B | 4 | 0 | 2 | 2 | 0 | 0 | |
| Vacant Spaces | C | 0 | 7 | 3 | 6 | 0 | 0 |
| D | 3 | 3 | 1 | 5 | 0 | 0 | |
| E | 2 | 1 | 2 | 1 | 0 | 0 | |
| F | 2 | 6 | 4 | 0 | 0 | 0 | |
The optimal assignment schedule and total distance is
| Vacant | Trucks | Total distances |
| A | 3 | 3 |
| B | 2 | 2 |
| C | 1 | 4 |
| D | d1 | 0 |
| E | d2 | 0 |
| F | 4 | 3 |
| Total | 12 | |
∴ The Optimum Distant (minimum) = 12 units.
APPEARS IN
RELATED QUESTIONS
Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`
In a factory there are six jobs to be performed each of which should go through two machines A and B in the order A - B. The processing timing (in hours) for the jobs arc given here. You are required to determine the sequence for performing the jobs that would minimize the total elapsed time T. What is the value of T? Also find the idle time for machines · A and B.
| Jobs | J1 | J2 | J3 | J4 | J5 | J6 |
| Machine A | 1 | 3 | 8 | 5 | 6 | 3 |
| MAchine B | 5 | 6 | 3 | 2 | 2 | 10 |
The assignment problem is said to be balanced if ______.
State whether the following is True or False :
In assignment problem, each facility is capable of performing each task.
State whether the following is True or False :
It is not necessary to express an assignment problem into n x n matrix.
In an assignment problem if number of rows is greater than number of columns, then dummy ______ is added
State whether the following statement is True or False:
The objective of an assignment problem is to assign number of jobs to equal number of persons at maximum cost
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?
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 | 7 | 2 | 4 | 4 | 5 |
| 4 | 18 | 9 | 12 | 17 | 15 |
| 5 | 11 | 6 | 14 | 19 | 10 |
A plant manager has four subordinates and four tasks to perform. The subordinates differ in efficiency and task differ in their intrinsic difficulty. Estimates of the time subordinate would take to perform tasks are given in the following table:
| I | II | III | IV | |
| A | 3 | 11 | 10 | 8 |
| B | 13 | 2 | 12 | 2 |
| C | 3 | 4 | 6 | 1 |
| D | 4 | 15 | 4 | 9 |
Complete the following activity to allocate tasks to subordinates to minimize total time.
Solution:
Step I: Subtract the smallest element of each row from every element of that row:
| I | II | III | IV | |
| A | 0 | 8 | 7 | 5 |
| B | 11 | 0 | 10 | 0 |
| C | 2 | 3 | 5 | 0 |
| D | 0 | 11 | 0 | 5 |
Step II: Since all column minimums are zero, no need to subtract anything from columns.
Step III: Draw the minimum number of lines to cover all zeros.
| I | II | III | IV | |
| A | 0 | 8 | 7 | 5 |
| B | 11 | 0 | 10 | 0 |
| C | 2 | 3 | 5 | 0 |
| D | 0 | 11 | 0 | 5 |
Since minimum number of lines = order of matrix, optimal solution has been reached
Optimal assignment is A →`square` B →`square`
C →IV D →`square`
Total minimum time = `square` hours.
