INDUSTRIAL MANAGEMENT II

Laboratory 5

ASSIGNMENT PROBLEM
 ASSIGNMENT PROBLEM

I. OBJETIVOS:

1. Use of SOLVER EXCEL software to solve allocation models through the

Hungarian method, this for improving decision-making in the solution of
problems of the productive sector.
[Link] of their overall results for decision-making in an activity
productive.

II. THEORETICAL INTRODUCTION:

The assignment problem is a variation of the original transportation problem, variation

in which the decision variables X (i,j) can only take binary values, that is to say be
zero (0) or one (1) in the optimal solution, which assumes that supply and demand are
perfectly aligned, in fact, both are equal to one (1).
There are multiple cases in which we can make use of the assignment problem to
to resolve various situations, among which the assignment is included
from personnel to machines, tools or job positions, schedules to teachers,
candidates to vacancies, guests to rooms, diners to tables, sellers to
territorial zones etc...
In the allocation model, the fundamental idea of resolution is what source satisfies
better the destination?, and given that we have associated the model with a great diversity of
Circumstances this question can be raised in multiple contexts, such as what
Is the candidate suitable for the position?, or what staff is the right one for the line?
productive? Or what personnel is best to carry out a certain task? One
a particular feature of the assignment model is that it is not solved
it is necessary that the number of sources be equal to the number of destinations, which is very
common in real life considering its application, since generally the amount
the number of applicants is excessively higher than the number of vacancies (logically making
reference to the application of the model to the context of labor supply and demand.

HUNGARIAN METHOD

El método Húngaro es un método de optimización de problemas de asignación, conocido

Thanks to the fact that the initial contributions to the definitive classical method were from Dénes.
König and Jenő Egerváry are Hungarian mathematicians.

HUNGARIAN ALGORITHM, STEP 1

First of all, it is worth remembering that 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
number of columns n = m), once it is built, the most important element must be found
small in each row of the matrix.

HUNGARIAN ALGORITHM, STEP 2

Once the previous procedure is completed, a new n*m matrix must be constructed,
which will record the resulting values of the difference between each cost and the value
minimum of the row to which each cost corresponds (minimum value found in the first
step).

HUNGARIAN ALGORITHM, STEP 3

 This step consists of performing the same procedure as the previous two steps.
referred now to the columns, that is to say, the minimum value of each column is found, with
the difference that this is found from the resulting matrix in the second step, then we
will build a new matrix in which the resulting values will be recorded of the
difference between each cost and the minimum value of the column to which each cost belongs
corresponds to a 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 equals the number of rows
or columns, the optimal solution has been achieved (the best assignment according to
(optimization context), if the number of lines is less than the number of rows or columns
Step 5 must be followed.

HUNGARIAN ALGORITHM, STEP 5

This step involves finding the smallest element among those values that do not
they are covered by the lines of step 4, now it will be subtracted from the remaining elements
that are not covered by the lines; then this same value will be added
to the values found at the intersections of the horizontal and vertical lines,
Once this step is completed, you must return to step 4.

III. EQUIPMENT AND MATERIALS:

. Simulation software SOLVER EXCEL

. Computer.
. Laboratory guide.

IV. PROCEDURE:

4.1 Example Application with Solver

Assignment problems: In this case, the formulation is similar to the problem of

transport

Example: A company bought three new machines of different types. There are four sites.
available within the workshop where a machine could be installed. Some of them
are more suitable than others for certain machines in particular due to their proximity to the centers
of work that would have an intense flow of work to and from the machines. (There is no flow
of work between the machines). Therefore, the objective is to assign the new
Machines to the available locations in such a way as to minimize the total handling cost.
materials. Table 2 provides the estimated cost per unit of time for handling
of the materials in question, with each of the machines at their respective sites. The
Location 2 is not considered appropriate for machine 2, so no cost is given in this case.
Table 2. Material handling costs.

Cost ($/hour)
Location
1 2 3 4
1 $13 $16 $12 $11
Machine 2 $15 --- $13 $20
3 $5 $7 $10 $6

To formulate it as an assignment problem, an additional machine must be added.

fictional for the additional place. Furthermore, a very large cost M must be assigned to the
assignment of machine 2 to place 2 to avoid it in the optimal solution.

Resolution: In the Excel spreadsheet, we set up the parameters table, so that

we are left with the following screen:

Then, we will have to set up the solution table, just like in the problem of
transport. In this case, it should be noted that: Number of origins (m) = number of
destinations (n). Each resourcei= 1, Each demandi1.

In this way, we obtain:

 The solution when applying Solver is as follows:

The optimal solution is to assign machine 1 to place 4, machine 2 to place 3, and the
machine 3 to place 1 at a total cost of $29 per hour. The fictitious machine is assigned to the place.
2, so that location will be available for some future real assignment.
 4.1 Application Example with the Hungarian Method

Joe Klyne's four children, John, Karen, Joe, and Terri, want to win something for their
personal expenses during a school trip to the zoo. Mr. Klyne has allocated
four tasks for your children:
Mow the lawn, paint the garage, vacuum the house, and wash the family cars. For
to avoid discussions, he asks them to submit (secret) offers of what they believe is a payment
Just for each of the four tasks. It is understood that later the four will obey.
the decision of his dad about who does which task. The table summarizes the offers received

1. Choose the minimum value of each row and subtract it.

Choose the minimum value of each column and subtract

3. Mark all zeros with the best number of lines

4. Four lines must be used, but only three have been used, so the smaller one is taken.
number of unmarked boxes is subtracted.
5. Mark all zeros with the best number of lines

All zero (0) values represent resource allocations to tasks.

Costo: 21
V. DEVELOPMENT OF PRACTICAL ACTIVITY:

Four cargo ships must be used to transport goods from a port to

four other ports (numbered 1, 2, 3, and 4). Any ship can be used to
take any of the four trips. However, given some differences between
the ships and the cargo, the total cost of loading, transporting, and unloading goods from the
the different combinations of ships and ports vary considerably. These
costs are shown in the following table:

Port ($)
1 2 3 4
1 500 400 600 700
Boat 2 600 600 700 500
3 700 500 700 600
4 500 400 600 600

The objective is to assign the boats to the ports in a one-to-one correspondence.

manera que se minimice el costo total de los cuatro envíos.

2. Apply the Hungarian algorithm to solve the assignment problem that has the
next cost table:

Task
1 2 3 4
A 4 6 5 5
B 7 4 5 6
Assigned C 4 7 6 4
D 5 3 4 7

A swimming team coach must assign competitors to the event of

200 meters of combined relay that will go to the youth Olympics. Like many of
their best swimmers are fast in more than one style, it is not easy to decide which of
they will assign each of the 4 styles. The 5 best swimmers and their best
Times (in seconds) for each style are shown in the following table,
The coach wants to determine how to assign 4 swimmers to the 4 swimming styles.
to minimize the sum of the best corresponding times.

a) Formulate this problem as an assignment problem.

b) Obtain an optimal solution.

Type of
Carlos Christian David Tony
swimming
Back 37.7 32.9 33.8 37.0
Chest 43.4 33.1 42.2 34.7
Butterfly 33.3 28.5 38.9 30.4
Free 29.2 26.4 29.6 28.5

4. The production line manager of an electronics company must assign personnel.

five tasks. There are five available operators to assign them. The manager of
line has test data available that reflects a numerical classification

REGULAR TRAINING PROGRAM

TECSUP Industrial Management II

of productivity for each of the five workers in each of the jobs.

These data were obtained through an operation examination and test administered
by the industrial engineering department. Assuming that an operator can
execute a single job, propose a model that leads to optimal assignment
tasks.

Number Job Number

of
1 2 3 4 5
operador
1 12 16 24 8 2
2 6 8 20 14 6
3 10 6 16 18 12
4 2 4 2 24 20
5 7 10 6 6 18

Four cargo ships will be used to transport goods from one port to another four.
ports (labeled 1, 2, 3, 4). Any boat can be used to do any
of these four trips. However, as can be seen in the following table, due to the
differences in the boats and the cargo, the total cost of loading, transporting, and unloading
The goods vary considerably in the different ship-port combinations.

Ports
Ships
1 2 3 4
1 $500 $400 $600 $700
2 $600 $600 $700 $500
3 $700 $500 $700 600 dollars
4 $500 $400 $600 $600

The goal is to assign the four boats to the four different ports in such a way that
the total cost of the four shipments is minimized.
a. Describe how this problem fits into an assignment problem
b. Formulate and solve this problem using EXCEL SOLVER

REGULAR TRAINING PROGRAM 57

Industrial Management II TECSUP

NOTES:

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------

REGULAR TRAINING PROGRAM 58