07 Assignment Model
Special case of transportation model, where no of supply nodes always = no of demand nodes
Input is a \(n \times n\) matrix, where
- \(n\) workers are assigned to \(n\) jobs
- cells contain the value of cost associated with assignment
Objectives¶
is one of the following
- minimize the total time to complete a set of jobs
- minimize cost of assignments
- maximize the skill ratings
- maximize total satisfaction of customers
Assumptions¶
- Each machine/worker is assigned \(\le 1\) job
- Each job is assigned to exactly 1 machine/worker
Steps¶
-
Operations
-
Row operation \(R_i = R_i - \text{min} (R_i)\)
-
Col operation \(C_i = C_i - \text{min} (C_i)\)
or
-
Col operation \(C_i = C_i - \text{min} (C_i)\)
-
Row operation \(R_i = R_i - \text{min} (R_i)\)
-
Assign jobs to workers
-
Only cells with value = 0 can be assigned
-
Assignment of a cell must be unique
-
Cost of completion = Initial values of the assigned cells
Special Cases¶
| Case | Method |
|---|---|
| No Unique Solution found | 1. Draw minimum number of horizontal/vertical lines in the last reduced matrix, passing through all 0s 2. Select smallest uncovered element 3. Subtract it from every uncovered element 4. Add it to every element at the intersection 5. If no feasible solution, go to step 1 6. Else, determine the optimal solution |
| Unbalanced Assignment | Add rows/columns as required Fill empty rows/columns with 0s |
| Maximization Assignment Problem | Multiple all cells with -1 (only for first operation) Be careful of -ve sign Final value = -1 x Total Cost |
| Disallowed Assignment | If some cell is missing data, fill it in with \(M\) (a very large number) |