🔍

Understanding the Assignment Problem

May 31, 2025

Lecture on Assignment Problem and Its Solution

Introduction to Assignment Problem

  • Objective: Assign jobs to persons to minimize the total cost.
  • Scenario: Suppose there are n jobs and n people, each job can be performed by any person with varying efficiency.
  • Cost Representation: Cost of assigning the i-th person to the j-th job is given in a cost table.

Types of Assignment Problems

  • Balanced Assignment Problem: Equal number of jobs and persons (n x n matrix).
  • Unbalanced Assignment Problem: Unequal number of jobs and persons (m x n matrix).

Solving Assignment Problem

  • Hungarian Method: A preferred method used to solve assignment problems by minimizing cost.

Steps in Solving Using Hungarian Method

Step 1: Row Reduction

  • Subtract the minimum element from each row from all elements of that row.

Step 2: Column Reduction

  • Subtract the minimum element from each column from all elements of that column.

Step 3: Cover All Zeros

  • Draw the minimum number of lines (horizontal and/or vertical) to cover all zeros in the matrix.
  • Check if the number of lines is equal to the order of the matrix.
    • If yes, the solution is optimal.
    • If no, proceed to the next step.

Step 4: Adjust the Matrix

  • Determine the smallest uncovered element.
  • Subtract this element from all uncovered elements.
  • Add it to all elements covered twice (intersection points of lines).
  • Repeat Step 3.

Example

  • Example Details: Given a cost matrix, solve step by step using the Hungarian method.
  • Calculation: Follow the steps to reduce the matrix and draw lines until an optimal solution is reached.
  • Assignment: Assign jobs to machines to achieve the minimum cost.

Final Results

  • Optimal Assignment: Job 1 to Machine B, Job 2 to Machine E, Job 3 to Machine C, etc.
  • Minimum Total Cost: Calculate the minimum total cost of assignments using the final cost matrix.

Conclusion

  • Understanding the step-by-step process helps in efficiently solving assignment problems.
  • Encourage practice with different scenarios to master cost minimization in assignments.

Additional Notes

  • Further videos and explanations are available for more detailed understanding and practice.
  • Engage with additional resources for deeper learning.

Thank you for attending the lecture!

Full transcript