Assignment Model
Uploaded by
ScribdTranslationsAssignment Model
Uploaded by
ScribdTranslationsASSIGNMENT MODEL
The classic assignment model deals with pairing workers (with
various skills) with the jobs. Presumably, the variation of the skill
it affects the cost of completing a job. The goal is to determine the cost allocation
minimum of the workers to the jobs. The general assignment model with n
workers and n jobs are represented in table 5.31. The element cij represents
the cost of assigning worker i to job j (i,j = 1,2,…,n). Generality is not lost.
assuming that the number of workers and the number of jobs are the same, because
we can always add workers or fictional jobs to satisfy this
assumption.
The assignment model is a special case of the transportation model, where the
workers represent the origins and the jobs represent the destinations. The offer
(demand) at each origin (destination) is equal to 1. The cost of 'transporting' the worker
At work j is cij. In fact, the assignment model can be solved directly.
as a transport model (or as a regular PL). However, the fact that
the supply and demand being equal to 1 leads to the development of a solution algorithm
simple called Hungarian method. Although the new solution method seems
completely foreign to the transport model, in reality the algorithm has its origin in the
simplex method, just like the transportation model.
Hungarian method
The Hungarian method is an optimization method for assignment problems, known
thanks to the fact that the first contributions to the definitive classical method were made by Dénes
König and Jenő Egerváry are Hungarian mathematicians. The algorithm as will be detailed in
continuation is designed for the resolution of problems
of minimization only, it will then be a matter of adding an additional step to
address maximization exercises.
Steps
Hungarian Algorithm, Step 1
The Hungarian method works on a cost matrix n*m (in this case known as
matrix m*m, given that the number of rows is equal to the number of columns n = m), a
Once built, the smallest element in each row must be found.
matrix.
Hungarian Algorithm, Step 2
Once the previous procedure is completed, a new n*m matrix must be constructed,
in which the resulting values of the difference between each cost and the
minimum value of the row to which each cost corresponds (minimum value found in the
first step).
Hungarian Algorithm, Step 3
This step involves performing the same procedure as the previous two steps.
referring now to the columns, that is, the minimum value of each column is found, with
the difference that this is in the resulting matrix in the second step, then it
will build a new matrix in which the resulting values will be recorded
difference between each cost and the minimum value of the column to which each cost corresponds
corresponds, matrix called "Reduced Cost Matrix".
Hungarian Algorithm, Step 4
Next, horizontal or vertical lines or both must be drawn (only
of those types) with the aim of covering all the zeros of the reduced cost matrix.
with the smallest number of lines possible, if the number of lines is equal to the number of
rows or columns have been achieved to obtain the optimal solution (the best assignment according to
(optimization context), if the number of lines is less than the number of rows or
Columns should proceed with step 5.
Hungarian Algorithm, Step 5
This step involves finding the smallest element among those values that are not
they are covered by the lines of step 4, now it will be subtracted from the remainder of
elements that are not covered by the lines; below, this same
value will be added to the values found at the intersections of the lines
horizontal and vertical, once this step is completed, one must return to step 4.
We will use two examples to present the mechanics of the new algorithm. The following
This section provides an explanation of the procedure based on simplex.
Example 1
Joe Klyne's three children, John, Karen, and Terri, want to earn some money for their
personal expenses. Mr. Klyne chose three tasks for his children: mowing the lawn,
paint the garage door and wash the family cars. To avoid the
early competition among the siblings, asks them to submit bids
individuals (secret) for what they consider a payment.
Like the transportation method, the classic Hungarian method (primarily designed
for manual calculations) is something of the past, and it is presented here for historical reasons.
Currently, that type of calculations is not required, since the problem can
to be resolved using highly efficient PL computer codes. Perhaps the
The benefit of studying these classic techniques is that they are based on a theory.
complex that reduces the solution steps to simple rules suitable for calculations
manuals.
Resolution
. Step 1. Determine pi, the minimum cost element in row i of the cost matrix
original, and subtract it from all the elements of row i, i 5 1,2,3.
. Step 2. For the matrix created in step 1, determine q j, the cost element.
minimum of column j, and subtract it from all elements of column j, j 5 1,2,3.
. Step 3. Based on the matrix from step 2, try to determine a feasible allocation.
among all the resulting zero entries. 3a. If that assignment can be found, it is
optimal. 3b. Otherwise, more calculations are required (as will be explained in the
example 5.4-2).
Table 5.33 demonstrates the application of the two steps to the current problem. The cells
with zero underline entries in step 3 gives the optimal (feasible) solution: John
Karen gets the job of painting, Karen the lawn mowing, and Terri gets the job of washing the
family cars. The total cost for Mr. Klyne is $27.
quantity will always be equal (p1 1 p2 1 p3) 1 (q1 1 q2 1 q3) 5 (9 1 9 1 8) 1 (0 1 1 1 0) 5
$27. (A justification for this result is provided in the following section.)
As indicated in step 3 of the Hungarian method, the zeros created by steps 1 and 2
they may not provide a feasible solution directly. In this case, more are needed
steps to determine the optimal (feasible) allocation. The following example demonstrates
this situation.
Example 2
The previous problem adds a child, expanding it to four children and four
tasks. Table 5.34 summarizes the cost elements of the problem.
Resolution
The application of steps 1 and 2 to the matrix of table 5.34 (with p1 = 5, p2 = 7, p3 = 4,
p4 5 5, q1 5 0, q2 5 0, q3 5 3 and q4 5 0) results in the reduced matrix of the table
5.35.
The locations of the zero entries do not allow for unique tasks to be assigned to all.
children. For example, if we assign child 1 task 1, then the column will be removed
1, and child three will not have a zero entry in the remaining three columns. This
obstacles can be overcome by adding the next step to the given procedure in the
example 5.4-1.
3b. If zero element feasible assignments cannot be found
(i) Trace the minimum number of horizontal and vertical lines in the last matrix.
reduced to cover all zero entries.
(ii) Select the minimum uncovered entry and subtract it from each uncovered entry.
cover it, and then add it to each entry at the intersection of two lines.
(iii) If it cannot determine a feasible assignment among the zero inputs
resulting, repeat step 3a.
The application of step 3b to the last matrix produces the shaded cells in the table.
5.36. The minimum unshaded entry (shown underlined) is equal to 1. This
Entry is added to the intersection cell and subtracted from the shaded cells.
remaining to produce the matrix of table 5.37, and the optimal solution indicated by the
underlined zeros.
Source: Operations Research Ninth Edition Hamdy A. Taha
Example 3
The manufacturing company 'Jiménez y Asociados' wishes to hold an event
preventive maintenance on its three main machines A, B, and C. The time that
the demand to carry out maintenance on each machine is 1 day, however, the
maintenance work cannot last more than one day, taking into account that the
the company has three maintenance service providers
assign a maintenance team to each machine to be able to meet the
execution of preventive maintenance. Considering that according to the degree of
specialization of each maintenance service provider team the cost of
The task varies for each particular machine, the correct equipment must be assigned to it.
machine indicated with the aim of minimizing the total cost of the day. The costs
associates can be observed in the following table:
Resolution
Reduced cost matrix
Therefore, the assignment that represents the lowest cost for the maintenance day
the estimate determines that Team 1 performs maintenance on Machine 1, the
Team 2 perform maintenance on Machine 3 and Team 3 perform maintenance
from Machine 2, a journey that will have a total cost of 17 monetary units.
