Unbalanced Assignment Problem | Non-Square Matrix Assignment | Hungarian Method | :-By Kauserwise

Summary

In this video, the unbalanced assignment problem is explained in detail. The process starts by converting an unbalanced problem into a balanced one by adding a dummy column. The Hungarian method is then applied in two phases: Row and column reductions are performed first to simplify the matrix. Following this, an optimization process is carried out using a series of steps, including scanning rows and columns, marking squares, and covering zeros. The video concludes by identifying the optimal assignment and calculating the minimum time required for completing jobs with operators, achieving an optimal solution for the problem.

Takeaways

• 😀 The assignment problem involves assigning jobs to workers (or tasks to agents) to minimize time or cost.
• 😀 There are two types of assignment problems: balanced (equal jobs and workers) and unbalanced (unequal jobs and workers).
• 😀 In the case of an unbalanced assignment problem, the first step is to convert it into a balanced one by adding a dummy column with zero entries.
• 😀 The Hungarian Method is applied in two phases: Phase 1 focuses on row and column reductions, while Phase 2 involves optimization.
• 😀 Row reduction involves subtracting the minimum value from each row's entries, helping simplify the matrix for further analysis.
• 😀 Column reduction is similar to row reduction, but it subtracts the minimum value in each column to further simplify the matrix.
• 😀 After row and column reductions, the next step is to cover all zeros in the matrix by drawing a minimum number of lines.
• 😀 In Phase 2, if the number of marked squares (zeros) equals the number of rows, the optimal solution is found.
• 😀 If the condition in Phase 2 isn't satisfied, the minimum value from the undeleted cells is found and adjusted in the matrix.
• 😀 After adjustments, the matrix is rescanned for zeros, and the process repeats until an optimal assignment is achieved.
• 😀 Once optimality is reached, the jobs are assigned to operators based on the matrix, and the total minimum time is calculated.

Q & A

What is an unbalanced assignment problem?

An unbalanced assignment problem occurs when the number of rows (jobs) is not equal to the number of columns (operators). In such a case, a dummy column or row is added to balance the matrix before proceeding with the solution.

How is an unbalanced assignment problem converted into a balanced one?

An unbalanced assignment problem is converted into a balanced one by adding a dummy column (or row) with zero entries to ensure that the matrix becomes square, i.e., the number of rows equals the number of columns.

What is the Hungarian method, and how does it apply to the assignment problem?

The Hungarian method is an optimization algorithm used to solve assignment problems. It involves two phases: Phase 1 (row and column reductions) and Phase 2 (optimization steps), which ultimately lead to finding the optimal assignment of jobs to operators to minimize the total cost or time.

What is the procedure for row reduction in the Hungarian method?

In row reduction, the minimum value in each row is subtracted from all the elements in that row, transforming the matrix to make the smallest value in each row zero.

How does column reduction differ from row reduction?

Column reduction is similar to row reduction, but it involves subtracting the minimum value of each column from all the elements in that column. This ensures the smallest value in each column becomes zero.

What is the purpose of drawing lines to cover the zeros in the matrix?

The purpose of drawing lines is to cover all the zeros in the matrix with the minimum number of lines. This step helps identify whether the current assignment can be optimized further and is a part of the process for finding the optimal solution.

How do you perform row scanning during the line drawing step?

In row scanning, for each row, you check if there is exactly one zero. If there is, you mark it with a square and draw a vertical line through it. If there are multiple zeros, you skip that row.

What does column scanning involve in the line drawing step?

Column scanning is similar to row scanning but applied to columns. You check each column for exactly one zero. If found, you mark it with a square and draw a horizontal line through it. If there are multiple zeros, you skip that column.

What happens if the number of squares marked is not equal to the number of rows?

If the number of squares marked is not equal to the number of rows, you proceed to the next step where you identify the minimum value of the undeleted cell values and perform additional operations to adjust the matrix and continue the optimization process.

How is the optimal solution determined in the Hungarian method?

The optimal solution is determined when the number of squares marked equals the number of rows. At this point, the assignment of jobs to operators is considered optimal, and the total minimum time or cost is calculated based on the assignments.