Advertisements
Advertisements
Question
Give mathematical form of Assignment problem
Advertisements
Solution
Consider the problem of assigning n jobs to n machines (one job to one machine).
Let Cij be the cost of assigning ith job to the jth machine and xij represents the assignment of ith job to the jth machine.
Then, xij = `{{:(1",", "if" "i"^"th" "job is assigned to" "j"^"th" "machine"),(0",", "if" "i"^"th" "job is assigned to" "j"^"th" "machine"):}`
| Machines | ||||||
| 1 | 2 | … | n | Supply | ||
| 1 | `""^((x_11))"C"_11` | `""^((x_12))"C"_12` | … | `""^((x_(1n)))("C"_(1n))` | 1 | |
| 2 | `""^((x_21))"C"_21` | `""^((x_22))"C"_22` | … | `""^((x_(2n)))("C"_(2n))` | 1 | |
| Jobs | : | : | : | : | 1 | |
| m | `""^((x_"ij"))"C"_("n"1)` | `""^((x_(m2)))"C"_("n"1)` | … | `""^((x_"ij"))("C"_"nn")` | 1 | |
| Demand | b1 | b2 | … | bn | ||
xij is missing in any cell means that no assignment is made between the pair of job and machine.
i.e xij = 0.
xij is presents in any cell means that an assignment is made their.
In such cases xij = 1
The assignment model can written in LPP as follows:
Minimize Z = `sum_("i" = 1)^"m", sum_("j" = 1)^"n" "C"_"ij" "X"_"ij"`
Subject to the constrains
`sum_("i" = 1)^"n" "X"_"ij"` = 1, j = 1, 2, …. n
`sum_("i" = 1)^"n" "X"_"ij"` = 1, i = 1, 2, …. n and xij =0 or 1 for all i, j
APPEARS IN
RELATED QUESTIONS
Solve the following minimal assignment problem :
| Machines | A | B | C | D | E |
| M1 | 27 | 18 | ∞ | 20 | 21 |
| M2 | 31 | 24 | 21 | 12 | 17 |
| M3 | 20 | 17 | 20 | ∞ | 16 |
| M4 | 21 | 28 | 20 | 16 | 27 |
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 |
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.
Choose the correct alternative :
The assignment problem is said to be balanced if it is a ______.
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
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)
Choose the correct alternative:
In an assignment problem involving four workers and three jobs, total number of assignments possible are
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`
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.
