Advertisements
Advertisements
Question
Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:
| Job | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 30 | 37 | 40 | 28 | 40 |
| 2 | 40 | 24 | 27 | 21 | 36 |
| 3 | 40 | 32 | 33 | 30 | 35 |
| 4 | 25 | 38 | 40 | 36 | 36 |
| 5 | 29 | 62 | 41 | 34 | 39 |
Find the optimal assignment schedule.
Advertisements
Solution
Step 1:
Since it is a maximization problem, subtract each of the elements in the table from the largest element, i.e., 62
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 32 | 25 | 22 | 34 | 22 |
| 2 | 22 | 38 | 35 | 41 | 26 |
| 3 | 22 | 30 | 29 | 32 | 27 |
| 4 | 37 | 24 | 22 | 26 | 26 |
| 5 | 33 | 0 | 21 | 28 | 23 |
Step 2:
Row minimum Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 10 | 3 | 0 | 12 | 0 |
| 2 | 0 | 16 | 13 | 19 | 4 |
| 3 | 0 | 8 | 7 | 10 | 5 |
| 4 | 15 | 2 | 0 | 4 | 4 |
| 5 | 33 | 0 | 21 | 28 | 23 |
Step 3:
Column minimum Subtract the smallest element in each column of assignment matrix obtained in step 2 from every element in its column.
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 10 | 3 | 0 | 8 | 0 |
| 2 | 0 | 16 | 13 | 15 | 4 |
| 3 | 0 | 8 | 7 | 6 | 5 |
| 4 | 15 | 2 | 0 | 0 | 4 |
| 5 | 33 | 0 | 21 | 24 | 23 |
Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 10 | 3 | 0 | 8 | 0 |
| 2 | 0 | 16 | 13 | 15 | 4 |
| 3 | 0 | 8 | 7 | 6 | 5 |
| 4 | 15 | 2 | 0 | 0 | 4 |
| 5 | 33 | 0 | 21 | 24 | 23 |
Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 4 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 14 | 3 | 0 | 8 | 0 |
| 2 | 0 | 12 | 9 | 11 | 0 |
| 3 | 0 | 4 | 3 | 2 | 1 |
| 4 | 19 | 2 | 0 | 0 | 4 |
| 5 | 37 | 0 | 21 | 24 | 23 |
Step 6:
Draw minimum number of vertical and horizontal lines to cover all zeros.
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 14 | 3 | 0 | 8 | 0 |
| 2 | 0 | 12 | 9 | 11 | 0 |
| 3 | 0 | 4 | 3 | 2 | 1 |
| 4 | 19 | 2 | 0 | 0 | 4 |
| 5 | 37 | 0 | 21 | 24 | 23 |
Step 7:
From step 6, minimum number of lines covering all the zeros are 5, which is equal to order of the matrix, i.e., 5.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:
| Jobs | Machines (Profit in ₹) | ||||
| A | B | C | D | E | |
| 1 | 14 | 3 | 0 | 8 | 0 |
| 2 | 0 | 12 | 9 | 11 | 0 |
| 3 | 0 | 4 | 3 | 2 | 1 |
| 4 | 19 | 2 | 0 | 0 | 4 |
| 5 | 37 | 0 | 21 | 24 | 23 |
Step 8:
The matrix obtained in step 7 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:
| Jobs | Machines | Profit (in ₹) |
| 1 | C | 40 |
| 2 | E | 36 |
| 3 | A | 40 |
| 4 | D | 36 |
| 5 | B | 62 |
∴ Total maximum profit = 40 + 36 + 40 + 36 + 62 = ₹ 214.
APPEARS IN
RELATED QUESTIONS
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 is given in the following table:
|
Jobs
|
Machines |
|||
|
P |
Q |
R |
S |
|
|
Processing Cost (Rs.)
|
||||
|
A |
31 |
25 |
33 |
29 |
|
B |
25 |
24 |
23 |
21 |
|
C |
19 |
21 |
23 |
24 |
|
D |
38 |
36 |
34 |
40 |
How should the jobs be assigned to the four machines so that the total processing cost is minimum?
Solve the following minimal assignment problem and hence find minimum time where '- ' indicates that job cannot be assigned to the machine :
| Machines | Processing time in hours | ||||
| A | B | C | D | E | |
| M1 | 9 | 11 | 15 | 10 | 11 |
| M2 | 12 | 9 | - | 10 | 9 |
| M3 | - | 11 | 14 | 11 | 7 |
| M4 | 14 | 8 | 12 | 7 | 8 |
Solve the following maximal assignment problem :
| Branch Manager | Monthly Business ( Rs. lakh) | |||
| A | B | C | D | |
| P | 11 | 11 | 9 | 9 |
| Q | 13 | 16 | 11 | 10 |
| R | 12 | 17 | 13 | 8 |
| S | 16 | 14 | 16 | 12 |
A departmental head has three jobs and four subordinates. The subordinates differ in their capabilities and the jobs differ in their work
contents. With the help of the performance matrix given below, find out which of the four subordinates should be assigned which jobs ?
| Subordinates | Jobs | ||
| I | II | III | |
| A | 7 | 3 | 5 |
| B | 2 | 7 | 4 |
| C | 6 | 5 | 3 |
| D | 3 | 4 | 7 |
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 unbalance if ______
Choose the correct alternative :
In an assignment problem if number of rows is greater than number of columns then
The objective of an assignment problem is to assign ______.
Fill in the blank :
When an assignment problem has more than one solution, then it is _______ optimal solution.
Fill in the blank :
An _______ is a special type of linear programming problem.
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?
Choose the correct alternative:
Assignment Problem is special case of ______
Choose the correct alternative:
The assignment problem is said to be balanced if ______
If the given matrix is ______ matrix, the assignment problem is called balanced problem
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:
In assignment problem, if number of columns is greater than number of rows, then a dummy row is added
State whether the following statement is True or False:
In assignment problem each worker or machine is assigned only one job
What is the Assignment problem?
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?
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 ______
Choose the correct alternative:
If number of sources is not equal to number of destinations, the assignment problem is called ______
A job production unit has four jobs P, Q, R, and 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 |
Find the optimal assignment to minimize the total processing cost.
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 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.
