Assignment Problems
An assignment problem determines the optimal one-to-one matching between a set of resources and a set of tasks. Each resource is assigned to exactly one task, and each task receives exactly one resource in the standard balanced formulation. The objective may be to minimize total cost or processing time, or maximize total profit or effectiveness. The problem is commonly represented by a cost matrix c_ij, where c_ij is the cost of assigning resource i to task j. Binary decision variables x_ij indicate whether that assignment is selected: x_ij = 1 if resource i is assigned to task j and x_ij = 0 otherwise. The standard minimization model is Minimize Z = Sum_i Sum_j c_ij x_ij, subject to Sum_j x_ij = 1 for every resource i, Sum_i x_ij = 1 for every task j, and x_ij ∈ {0,1}. The Hungarian algorithm provides an efficient exact solution for the classical assignment problem. If the numbers of resources and tasks are unequal, dummy rows or columns can be introduced to create a balanced matrix, with their costs representing the appropriate penalty or zero-cost convention. Practical models may also include forbidden assignments, qualification requirements, machine compatibility, shift restrictions, or other constraints. The classical assignment model assumes that the cost or performance associated with each assignment is known and that assignments are independent; these assumptions may need modification in more complex scheduling or routing problems.
Knowledge Check
1.What is the defining characteristic of a classical assignment problem?
2.What does the binary variable x_ij represent in an assignment model?
3.A balanced assignment problem has 4 workers and 4 jobs. What must the standard model enforce?
4.Suppose the assignment cost matrix is C = [[4, 9], [6, 3]]. Which assignment minimizes total cost?
5.For a minimization assignment problem, what does the objective function minimize?
6.What does the constraint Sum_j x_ij = 1 enforce for each resource i?
7.What does the constraint Sum_i x_ij = 1 enforce for each task j?
8.A company has 3 workers but 4 jobs that must be represented in an assignment matrix. What is a common modeling approach?
9.Why can an assignment problem be formulated as a binary integer optimization problem?
10.What is the main purpose of the Hungarian algorithm?
11.A cost matrix contains a very large value for assigning Worker 2 to Job 3. What can this represent in practice?
12.A particular worker is not qualified to perform a specific job. How can this restriction be represented in an assignment model?
13.Suppose a 3 × 3 assignment problem has the selected assignment costs 8, 5, and 7. What is the total objective value?
14.If an assignment problem is changed from cost minimization to effectiveness maximization, what must change in the mathematical formulation?
15.Which assumption of the classical assignment model may become problematic when assigning a worker to one task changes the cost of another assignment?