Restricted Assignment Problems¶

A Restricted Assignment Problem is a variation of the classic assignment problem in which certain tasks cannot be assigned to specific agents due to constraints or limitations. These restrictions may arise due to various factors such as skill incompatibilities, equipment limitations, or regulatory requirements. The objective is still to minimize the total cost (or maximize the total benefit), while respecting these restrictions.

Characteristics of Restricted Assignment Problems¶

Infeasibility Constraints
Certain task-agent combinations are not feasible. For example, a specific worker may not have the skills to perform a particular task, or a machine may not be able to handle a specific job. These infeasible assignments need to be avoided in the solution.
Modified Cost Matrix
In the cost matrix, infeasible assignments are represented by a very high cost (often indicated as infinity, ∞) to ensure that these assignments are not selected in the optimization process.
Balanced vs. Unbalanced
The problem can still be either balanced (equal number of tasks and agents) or unbalanced (unequal number of tasks and agents). Dummy rows or columns may be added to balance the matrix in case of an unbalanced problem.

Example of a Restricted Assignment Problem¶

Suppose a company has three workers (A, B, and C) and three tasks (1, 2, and 3). The cost of assigning each worker to each task is given in the matrix below. However, there are some restrictions: - Worker A cannot perform Task 2. - Worker B cannot perform Task 3.

The cost matrix, incorporating these restrictions, is as follows:

	Task 1	Task 2	Task 3
Worker A	8	∞	13
Worker B	10	12	∞
Worker C	14	8	11

Here, "∞" indicates that those assignments are not feasible.

Solving the Restricted Assignment Problem¶

To solve this problem, we will follow these steps:

Modify the Cost Matrix
We have already set the cost of restricted assignments to infinity (∞) to represent infeasibility.
Apply the Hungarian Method or Other Algorithms
Use the Hungarian Method to find the optimal assignment while considering the high costs of the restricted cells. The algorithm will avoid choosing cells marked as infinity.

Step-by-Step Solution Using the Hungarian Method¶

Step 1: Row Reduction¶

Subtract the smallest element in each row from all elements of that row.

Row 1: 8, ∞, 13 → Minimum is 8 → 0, ∞, 5
Row 2: 10, 12, ∞ → Minimum is 10 → 0, 2, ∞
Row 3: 14, 8, 11 → Minimum is 8 → 6, 0, 3

The resulting matrix after row reduction is:

	Task 1	Task 2	Task 3
Worker A	0	∞	5
Worker B	0	2	∞
Worker C	6	0	3

Step 2: Column Reduction¶

Subtract the smallest element in each column from all elements in that column.

Column 1: 0, 0, 6 → Minimum is 0 → 0, 0, 6
Column 2: ∞, 2, 0 → Minimum is 0 → ∞, 2, 0
Column 3: 5, ∞, 3 → Minimum is 3 → 2, ∞, 0

The resulting matrix after column reduction is:

	Task 1	Task 2	Task 3
Worker A	0	∞	2
Worker B	0	2	∞
Worker C	6	0	0

Step 3: Cover All Zeros with the Minimum Number of Lines¶

Cover all zeros in the matrix using the minimum number of horizontal and vertical lines. This matrix requires three lines to cover all zeros.

Step 4: Check for Optimality¶

Since the number of lines equals the number of rows (3), an optimal assignment can be made.

Step 5: Make the Optimal Assignment¶

Select zeros such that no two selected zeros are in the same row or column.

Assign Worker A to Task 3 (cost = 2).
Assign Worker B to Task 1 (cost = 0).
Assign Worker C to Task 2 (cost = 0).

Final Solution¶

The optimal assignment is:

Worker A → Task 3 (Cost = 13)
Worker B → Task 1 (Cost = 10)
Worker C → Task 2 (Cost = 8)

The total minimum cost is: 13 + 10 + 8 = 31.

Conclusion¶

In a Restricted Assignment Problem, certain task-agent combinations are infeasible due to restrictions, which are represented in the cost matrix as very high costs. The Hungarian Method or other assignment algorithms can be adapted to solve these problems while avoiding infeasible assignments. This approach is useful in practical scenarios where some resources cannot perform certain tasks due to skill limitations, equipment incompatibilities, or other constraints.

Hive Chat

Hi, I'm Hive Chat, an AI assistant created by CollegeHive.
How can I help you today?

🎶