Unbalanced Assignment Problems
Unbalanced Assignment Problems
Unbalanced assignment problems occur when the number of sources (e.g., machines) differs from the number of destinations (e.g., jobs), resulting in a non-square cost matrix. To solve these problems, dummy rows or columns are introduced to balance the matrix. Here's a step-by-step explanation of the process:
1. Problem Formulation
An unbalanced assignment problem involves:
- More sources than destinations or vice versa.
- A cost matrix that is not square.
Example Problem: A company has five machines (sources) and four jobs (destinations). The cost matrix is as follows:
| Machines/Jobs | Job 1 | Job 2 | Job 3 | Job 4 |
|---|---|---|---|---|
| Machine 1 | 2 | 3 | 1 | 5 |
| Machine 2 | 4 | 2 | 2 | 3 |
| Machine 3 | 3 | 4 | 5 | 6 |
| Machine 4 | 5 | 1 | 4 | 2 |
| Machine 5 | 2 | 4 | 3 | 3 |
Here, the matrix is 5x4. To balance it, add a dummy row with zero costs:
| Machines/Jobs | Job 1 | Job 2 | Job 3 | Job 4 | Dummy |
|---|---|---|---|---|---|
| Machine 1 | 2 | 3 | 1 | 5 | 0 |
| Machine 2 | 4 | 2 | 2 | 3 | 0 |
| Machine 3 | 3 | 4 | 5 | 6 | 0 |
| Machine 4 | 5 | 1 | 4 | 2 | 0 |
| Machine 5 | 2 | 4 | 3 | 3 | 0 |
| Dummy | 0 | 0 | 0 | 0 | 0 |
2. Row and Column Reduction
- Row Reduction:
- Subtract the smallest value in each row from every element in that row.
- This step ensures that each row has at least one zero.
- Column Reduction:
- Subtract the smallest value in each column from every element in that column.
- This step ensures that each column has at least one zero.
Example Row Reduction: Subtract the smallest value in each row:
| Machines/Jobs | Job 1 | Job 2 | Job 3 | Job 4 | Dummy |
|---|---|---|---|---|---|
| Machine 1 | 1 | 2 | 0 | 4 | 0 |
| Machine 2 | 2 | 0 | 0 | 1 | 0 |
| Machine 3 | 0 | 1 | 2 | 3 | 0 |
| Machine 4 | 3 | 0 | 3 | 1 | 0 |
| Machine 5 | 0 | 2 | 1 | 1 | 0 |
| Dummy | 0 | 0 | 0 | 0 | 0 |
Column Reduction: Subtract the smallest value in each column:
| Machines/Jobs | Job 1 | Job 2 | Job 3 | Job 4 | Dummy |
|---|---|---|---|---|---|
| Machine 1 | 1 | 2 | 0 | 3 | 0 |
| Machine 2 | 2 | 0 | 0 | 0 | 0 |
| Machine 3 | 0 | 1 | 2 | 2 | 0 |
| Machine 4 | 3 | 0 | 3 | 0 | 0 |
| Machine 5 | 0 | 2 | 1 | 1 | 0 |
| Dummy | 0 | 0 | 0 | 0 | 0 |
3. Optimal Assignment Using the Hungarian Algorithm
- Cover Zeros:
- Draw the minimum number of lines (horizontal and vertical) required to cover all zeros in the matrix.
- If the number of lines equals the number of rows or columns (matrix order), the solution is optimal.
- Adjust Matrix:
- If not optimal, find the smallest uncovered element, subtract it from all uncovered elements, and add it to the elements at intersections of lines.
- Repeat the process until the number of lines drawn equals the matrix order.
Example Final Adjustment:
After adjustments:
| Machines/Jobs | Job 1 | Job 2 | Job 3 | Job 4 | Dummy |
|---|---|---|---|---|---|
| Machine 1 | 0 | 1 | 0 | 2 | 0 |
| Machine 2 | 1 | 0 | 0 | 0 | 0 |
| Machine 3 | 0 | 0 | 1 | 1 | 0 |
| Machine 4 | 1 | 0 | 2 | 0 | 0 |
| Machine 5 | 0 | 1 | 0 | 0 | 0 |
| Dummy | 0 | 0 | 0 | 0 | 0 |
Optimal Assignment: The assignments will be made based on the optimal zero locations, considering the dummy row is only used if necessary.
4. Special Cases
- High Cost Assignments:
- Assign very high costs to infeasible assignments to avoid them during the reduction steps.
Example with Restrictions:
If Machine M2 cannot be assigned to Area C, and Machine M4 cannot be assigned to Area A, set these costs to a high value and exclude them during the optimization process.
By using these steps, the unbalanced assignment problem can be efficiently solved to achieve the optimal allocation of resources or tasks.