04

Assignment Problems

Operations Research
Victor Vera Valdés
vverav@[Link]
The assignment problem is a special type of problem about
linear programming in which the assigned are resources that
destined for the performance of tasks.
For example, the assigned individuals can be employees who are known to have
to give work.
The assignment of people to jobs is a common application of
assignment problem.
However, the assigned onesThey don't have to be people.
They can also be machines, vehicles, or plants, or even periods.
to those who are assigned tasks.
The first of the following examples refers to machines assigned to
places, so the task in this case is only to have a
machine.
A later example refers to plants that are assigned products.
what they must manufacture.
To fit the definition of an assignment problem, it is necessary that
this type of applications are formulated in such a way that the following are met
assumptions.

The number of assignments is equal to the number of tasks. (This number is

denotes by n.)
Each assigned person is assigned only one area.
3. Each task must be performed by only one assigned person.

4. There is a costijassociated with the assigned i (i = 1, 2, . . . , n) that

carry out task j ( j = 1, 2, . . . , n).
5. The goal is to determine how the n assignments should be made for
minimize total costs.

Any problem that satisfies all these assumptions can be

solve very efficiently using the designed algorithms
special way for assignment problems.
 EXAMPLES
The first three assumptions are quite restrictive.
Many potential applicationsthey do not completely satisfy them.
•Con frecuencia es posible reformular el problema para hacerlo que se ajuste.
For example, many times they can be usedassigned fictitious tasks with
this end.
These formulation techniques are illustrated in the examples.
 Prototypical example

JOB SHOP COMPANY purchased three new machines of different types.

There are four available spots in the workshop where one could install a
machine.
Some of them are more suitable than others for certain particular machines.
due to its proximity to workplaces that would have an intense workflow
to and from these machines.
There will be no workflow between the new machines.
Therefore, the objective is to assign the new machines to the available locations.
in such a way that the total cost of material handling is minimized.
The following table provides the estimated cost per unit of time of the
handling of the materials in question, with each of the machines on site
respective.
The place 2 is not considered suitable for machine 2, so it does not
provide a cost for this case.
Material handling costs of Job Shop Co. ($)

To frame this as an assignment problem, a must be introduced.

fictional machine in the additional place.
Additionally, a very large cost must be [Link] the assignment of machine 2
in place 2 to avoid it in the optimal solution.
The following table shows the cost table that results for this problem.
of assignment.
This cost table contains all the necessary data to solve the problem.

The optimal solution is to assign machine 1 to location 4, machine 2 to location 3 and the
machine 3 to location 1 at a total cost of $29 per hour.
The fictitious machine is assigned to place 2, which makes this position available.
for some future real machine assignment.
Later, it will be discussed how this solution is obtained after formulating the
mathematical model for the general assignment problem.
 Assignment problem model
The mathematical model for addressing the assignment problem uses the
following decision variables:

for i = 1, 2, ..., n and j = 1, 2, ..., n.

So, every xijit is a binary variable (it takes values 0 or 1).
Binary variables are important in operations research for
represent the decisions of yes or no
In this case, the yes or no decisions are: should the assigned i perform task j?
If Z is the total cost, the model of the assignment problem is

If the restriction in parentheses that x is removedijbinary signals, it becomes clear that

the model is a special type of linear programming problem, so it
can resolve immediately.
Fortunately, for the reasons that will be explained shortly, it can be eliminated.
this restriction.
Now a comparison will be made of this model—without the binary restriction—
the model of the transportation problem that was presented earlier.
Note that their structures aresimilar. In fact, the assignment problem
it is just a special case of transportation problems where the origins are
now the assigned ones and the destinations are the assignments or tasks and where:
Number of Origins m = number of destinations n,
Each resource si= 1,
Each demand ofj = 1.
Due to the property ofinteger solutions of the transportation model, like now
alliy djare integers (= 1), this property means that every BF solution (even
the optimal) is an integer solution for an assignment problem.
The functional constraints of the allocation model prevent the variables
are greater than 1, and the non-negativity constraints prevent their existence.
values less than zero.
Therefore, if the binary restriction is removed in order to solve the problem of
assignment as a linear programming problem, the BF solutions that
they obtain (including the final optimal solution) will automatically satisfy the
binary constraint.
Generally, those who apply this technique to assignment problems
specifics do not take the trouble to write out the entire mathematical model.
It is much simpler to formulate it in a cost table., with the
identification of the assigned and the assignments, since it contains
all the essential data in a much more compact form.
Sometimes problems arise that do not entirely fit the model.
an assignment problem, because certain assigned will perform more than one
task.
In this case, the problem can bereformulate to fit the model
divide each of those assigned into separate new assignments (but
identical) where each new assigned will only perform one task.
Similarly, if a task is to be performed by multiple assignees, it
It can be divided into separate new tasks (but identical) where each
new task will be developed only by an assigned person according to the
reformulated model
EXAMPLES OF FORMULATION
 EXAMPLE: ASSIGNMENT OF PRODUCTS TO PLANTS

The BETTER PRODUCTS COMPANY has decided to start the production of four new
products in three plants that currently have excess production capacity.
Products require comparable productive effort per unit, so the
available production capacity in the plants is measured by the number of units of
any product that can be manufactured per day, as shown in the last column of
the following table.

The last line shows the daily production required to meet sales.
projected.
Each plant can produce any of these.
products, except for plant 2 which cannot manufacture the
product 3.
However, the variable cost per unit of each
product differs from one plant to another, as shown
in the main body of the table.
The administration needs to make the decision on how
divide the production among the plants.
You have two options:
Option 1:Allow the separation of products, in such a way
so that the same product can be manufactured in
more than one plant.
Option 2:Do not authorize the separation of products.

Each of these options implies aformulation

distinct.
The second option imposes a restriction that can only
increase the cost of an optimal solution, as
costs inevitably increase if the allocation does not
can be divided.
On the other hand, the key advantage of option 2 is that it eliminates
some hidden costs associated with the separation of
products that are not reflected in the table, which include costs
preparation, distribution, and administration additives.
For this reason, management wants both options to be analyzed.
before making the final decision.
Additionally, in the case of option 2, it has been specified that
At least one of the products must be assigned to each plant.
The model will be formulated and solved according to each
option, where option 1 leads to the transportation issue
and option 2 to the assignment problem.
Formulation as a transportation problem

Ideas?
 Formulation of option 1

By allowing the separation of products, the above table can be converted into
direct form in a parameter table for a transportation problem.
Plants become sources and products become destinations (or vice versa); of
In this way, resources are interpreted as production capacities and the
demands such as the production rates that are required.
Only two changes need to be made to the table.
First, since plant 2 cannot produce product 3, that assignment is avoided.
by giving it a very large unit cost, M.
Secondly, the total capacity (75 + 75 + 45 = 195) exceeds the total production that is
requires (20 + 30 + 30 + 40 = 120), therefore a fictitious destination is needed with
una demanda de 75 para balancear estas dos cantidades.
The resulting parameter table is shown in the following table.
The optimal solution to this transportation problem has basic variables (assignments) x.12
= 30, x13= 30, x15= 15, x24= 15, x25= 60, x3120 times x34= 25, de manera que:
Plant 1 produces all of products 2 and 3.
Plant 2 produces 37.5% of product 4.
Plant 3 produces 62.5% of product 4 and all of product 1.
The total cost is Z = $3,260 daily.
 Formulation of option 2.

If the products are not separated, each one of them must be assigned to a single plant.
So, the manufacturing of products can be interpreted as tasks in a problem.
of assignment and the plants as the assigned.
The administration has specified that at least one of the products must be assigned to each
plant.
More products (four) than plants (three) must be developed, so it will be necessary to assign.
two products to one of the plants.
Plant 3 barely has the additional capacity to manufacture a product, so it
plant 1 or plant 2 will manufacture the other product.
To make the allocation of this additional product possible within the formulation of a
assignment problem, plants 1 and 2 are divided into two assigned each.
shown in the following table.

The number of assigned (now five) must be equal to the number of tasks (now four), so
a fictitious assignment (product) is introduced as 5(D) in the previous table.
The role of this fictional assignment is to provide a second fictional product to anyone.
from plants 1 or 2, which receive only one actual product.
No costs are incurred for manufacturing a fictitious product, so, as always, the costs of
The fictional task is zero.
The exception is the cost M of the last line.
The reason is that a real product must be assigned to plant 3—chosen from the products.
1, 2, 3 or 4—and the big M method is needed to prevent the product from being assigned
fictional to this plant.
M is used in order to avoid the infeasible assignment of product 3 to plant 2.
The rest of the costs in the previous table are not the unit costs shown in the
original table or in the transport model version table.
For an assignment problem, the cost cijit is the total cost associated with the fact that the
assigned i and perform task j.
In the previous table, thetotal cost (per day) for plant i to manufacture product j is the
production cost multiplied by the number of units produced (per day), where
these two amounts that need to be multiplied are given separately in the original table.
For example, consider the assignment of plant 1 to product 1.
If the unit cost of $41 is used and the demand - number of units produced per day -
the same table (20) is obtained
Cost of manufacturing one unit of product 1 in plant 1 = $41
Required daily production of product 1 = 20 units
Total cost (daily) of assigning plant 1 to product 1 = 20 x ($41) = $820
The optimal solution to this assignment problem is the
next:
Plant 1 manufactures products 2 and 3.
Plant 2 manufactures product 1.
Plant 3 manufactures product 4.
In this case, the dummy allocation is given to plant 2.
The total cost is Z = $3,290 per day.
While this model could be solved through the
transport algorithm, there is actually a method
especially for these cases, which is even more efficient.
A special algorithm for the problem of
ASSIGNMENT
Next, a classic algorithm of this type will be described, calledHungarian algorithm
Hungarian method) because it was developed by mathematicians from Hungary.

Role of equivalent cost tables

The algorithm operates directly on the cost table of the problem.
More accurately, convert the original cost table into a series of cost tables.
equivalents until reaching one in which the optimal solution is obvious.
This equivalent cost table consists only of positive elements or those equal to zero where
All assignments can be made to the positions of the elements with a value of zero.
Since the total cost cannot be negative, it is clear that this set of assignments
with a total cost of zero, it is optimal.
The remaining question is how to convert the original cost table into this form.
The key to this conversion is the ability to add or subtract any constant from
any element of a row or column of the cost table without actually changing the
problem, that is, an optimal solution for the new cost table must also be
optimal for the ancient, and vice versa.
Therefore, the algorithm starts by subtracting the smallest number from each row of all.
the numbers of the line.
This line reduction process will create an equivalent cost table that has
elements equal to zero in all rows.
If this cost table has some columns without a zero element, the next step is
perform a column reduction process by subtracting the smallest number from each one
of such columns of the rest of the numbers in the column.
The new equivalent cost table will have a zero element in all rows and
columns.
If the zero elements provide a complete set of assignments, the latter
they constitute an optimal solution and the algorithm terminates.
As an illustration, consider the cost table of the Job Shop Co. problem:

To convert this cost table into an equivalent cost table, assume that you
the process of row reduction begins by subtracting 11 from each element of row 1, from
where it is obtained:
As any feasible solution must have exactly one assignment in row 1, the
The total cost of the new table will always be exactly 11 less than that of the old table.
Therefore, the solution that minimizes the total cost of a table must also minimize the
total cost of the other.
Notice that while the original cost table only had strictly elements
positives in the first three rows, the new table has a zero element in the row
1.
•Since the goal is to obtain zero elements placed in such a strategic way as to
produce a complete set of assignments, this process should continue in the others
rows and columns.
Negative elements should be avoided, so the constant that will be subtracted must
be the minimum element of the row or column.
If this procedure is applied to lines 2 and 3, the following cost table is obtained.
equivalent
This cost table has all the zero elements required from a set.
complete with assignments, as indicated by the four boxes, so that these four
Assignments constitute an optimal solution, as established for this problem.
The total cost of this optimal solution Z = 29, whichit is exactly the sum of the numbers
that have been subtracted from lines 1, 2, and 3.
Unfortunately, an optimal solution is not always obtained so easily, as
It is exemplified below with the formulation of the assignment problem for option 2
from Better Products Co.
Let us remember that:
Since this cost table of the problem has zero elements in all rows,
suppose that the process of converting it into equivalent cost tables begins through the
subtract the minimum element from each input column.
The result is shown below:

Now all the rows and columns have at least one zero element, but this time it is not
possible a complete set of assignments with elements of this type.
In reality, the maximum number of assignments that can be made in positions of
Zero elements is only 3.
Therefore, a more complex idea must be implemented to fully resolve this.
problem, which was not required in the first example.
 Creation of additional zero elements
This idea involves a new way to create additional positions with elements.
zero without creating any negative element.
Instead of subtracting a constant from a single row or column, it is now added or
subtract a constant from a combination of rows and columns.
This procedure beginsdrawing a set of lines through some
from the rows and columns in such a way that all the zeros are covered.
It is preferable that this procedure be done with theminimum number of lines,
as shown in the following cost table.
Notice that the minimum element that has not been crossed is 30, in both positions.
superiors of column 3.
Therefore, if 30 is subtracted from all elements of the entire table, that is, from each
Row and column, a new zero element will be created in these two positions.
Then, to restore the previous zero elements and eliminate negative elements, it is summed up.
30 to each row and column that is crossed by a line, that is, row 3 and column 2.
and 5(D).
From here, the following equivalent cost table is obtained.

A shortcut to obtain this cost table from the previous one is to subtract 30 only from the
elements that are not crossed by a line and then add 30 to each element that is
find at the intersection of two lines
Note that columns 1 and 4 of this new cost table have only one zero element and
both are on the same line (line 3).
As a result, it is now possible to make four assignments to positions of zero elements.
but still not to five.
Therefore, the previous procedure is repeated, where now the minimum number of lines for
covering all zeros is four: the same amount as the maximum number of assignments.
One way to do it is as shown below.

Again, the minimum element not covered by a line is 30, a number that now appears
in the first position of lines 2a and 2b.
Therefore, 30 is subtracted from all uncovered elements and 30 is added to all the covered ones.
elements covered twice—only the elements of M are overlooked—, which
provide the following equivalent cost table.
•En realidad, con esta tabla existen algunas formas de hacer un conjunto completo de
assignments to zero element positions (multiple optimal solutions), including those that
they indicate the five pictures.
The total resulting cost is Z = 810 + 840 + 800 + 0 + 840 = 3,290.
The complete algorithm that has just been exemplified is summarized below.
SUMMARY OF THE HUNGARIAN ALGORITHM
1. Subtract the smallest number from each row from every number in the row.
This is called line reduction.
Enter the results into a new table.

2. Subtract the smallest number from each column of the new table from each number in the
column.
This is called column reduction.
Enter the results in another table.

3. Test if an optimal assignment can be made.

•Do it by determining the minimum number of lines necessary to cover (it is
say, cross) all the zeros.
Since this minimum number of lines is equal to the maximum number of tasks that can
to be made in zero positions of elements, if the minimum number of lines is equal to the number
From lines, it is possible to have an optimal set of tasks.
If you find that a complete set of tasks is not possible, this means that
You did not reduce the number of lines covering all the zeros to the minimum number.
In that case, proceed to step 6.
Otherwise, proceed to step 4.
4. If the number of lines is less than the number of rows, modify the table of the
next form:
a) The smallest uncovered number of all the uncovered numbers of the
table.
b) Add the smallest uncovered number to the numbers that are found in the
intersections of the lines.
c) The crossed numbers but that are not found at the intersections of the lines
remain unchanged in the following table.

5. Repeat steps 3 and 4 until it is possible to have an optimal set of assignments.

6. Make the assignments one by one in the positions that have zero elements.
Start with the rows and columns that have only a zero.
As each row and each column needs to receive exactly one assignment, cross both
the row as the column involved after making each assignment.
Then continue with the rows and columns that have not yet been crossed out to
select the following assignment, and again give preference to some row or column that
have a single zero that has not been crossed.
Continue until all rows and columns have exactly one assignment and
therefore they may have already been crossed.
04

Assignment Problems

Operations Research
Victor Vera Valdés
vverav@[Link]