Assignment Problem
Chapter 6
Assignments Problem:
How this relates to business analysis:
Data analysis (timesheets) helps identify each
driver's strengths.
Optimization models identify the best solutions.
Decision-making here is based on numbers, not
intuition.
Using business analytics and intelligent
customization, the company made a decision that
saved time and effort, and directly improved
performance.
. تحليل البيانات (جدول الوقت) يساعد في معرفة نقاط القوة لكل سائق:عالقة هذا بتحليل األعمال
.نماذج التخصيص تحدد الحلول األفضل
. وليس على الحدس،اتخاذ القرار هنا مبني على أرقام
.سن األداء بشكل مباشر
ّ ويح،قرارا يوفر وقت وجهد
ً اتخذت الشركة،باستخدام تحليل األعمال والتخصيص الذكي
Assignment problem
The objective is to assign a number of jobs to the
equal number of persons at a minimum cost of
maximum profit.
Suppose there are n jobs to be performed and n
persons are available for doing these jobs.
Assume each person can do each job at a time with
a varying degree of efficiency.
Let cij be the cost of ith person assigned to jth job.
Then the problem is to find an assignment so that
the total cost for performing all jobs is minimum.
These problem may consist of assigning employee to
offices, classes to the rooms, problems to the
research teams, etc.
The assignment problem can be stated that in the form
of m x n matrix cij called a Cost Matrix (or)
Effectiveness Matrix where cij is the cost of assigning i
th machine to j th job
First check whether the number of rows is equal to
number of columns, if it is so, the assignment problem is
said to be balanced.
Then proceed to step 1. If it is not balanced, then it
should be balanced before applying the algorithm.
Step 1: Subtract the smallest cost element of each row
from all the elements in the row of the given cost
matrix. See that each row contains at least one zero.
Step 2: Subtract the smallest cost element of each
column from all the elements in the column of the
resulting cost matrix obtained by step 1 and make sure
each column contains at least one zero.
Step 3: (Assigning the zeros)
(a) Examine the rows successively until a row with
exactly one unmarked zero is found. Make an assignment
to this single unmarked zero by encircling it. Cross all
other zeros in the column of this encircled zero, as
these will not be considered for any future assignment.
Continue in this way until all the rows have been
examined.
(b) Examine the columns successively until a column with
exactly one unmarked zero is found. Make an assignment
to this single unmarked zero by encircling it and cross
any other zero in its row. Continue until all the columns
have been examined.
Step 4: (Apply Optimal Test)
If each row and each column contain exactly one
encircled zero, then the current assignment is optimal.
Assignment problem
1- Create the Cost Matrix:
Write a matrix that shows the cost of assigning each
worker to each job. If the matrix is not square (number
of workers ≠ number of jobs), add dummy rows or
columns with zero cost to make it square.
2- Row Reduction:
Subtract the smallest value in each row from every
element in that row. This step ensures that each row has
at least one zero.
3-Column Reduction:
After row reduction, subtract the smallest value in each
column from every element in that column. Now the
matrix will have as many zeros as possible.
4- Examine the rows successively until a row with
exactly one zero is found. Make an assignment to this
single unmarked zero by encircling it. Cross all other
values in the column and the row of this encircled zero.
5- Repeat step 4 after cross all others values in the
column and the rows of this encircled zero.
6- Make the Final Assignment:
Select encircled zeros in the first assignment matrix
(i.e., each worker gets only one job). This assignment
gives the optimal solution with the minimum total cost.
Example 1:
Solve the assignment problem:
A B C D
1 5 9 3 6
2 8 7 8 2
3 6 10 12 7
4 3 10 8 6
Since each row and each column contain exactly one
encircled zero, then the current assignment is optimal.
Where the optimal assignment is as 1 to C , 2 to D , 3 to
B , d to A .
The optimal solution is z = 3 + 2 + 10 + 3 = 16.
Example 2:
Solve the assignment problem:
A B C D
I 8 10 17 9
II 3 8 5 6
III 10 12 11 9
IV 6 13 9 7
Since each row and each column contain exactly one
encircled zero, then the current assignment is optimal.
Where the optimal assignment is as I to B , II to C , III
to D , IV to A .
The optimal solution is z = 10 + 5 + 9 + 6 = 30.
Example 3:
Solve the following assignment problem shown in Table
using Hungarian method. The matrix entries are
processing time of each man in hours.
Solution:
Since each row and each column contain exactly one
encircled zero, then the current assignment is optimal.
Where the optimal assignment is as 1 to II , 2 to IV , 3
to I , 4 to V and 5 to III.
The optimal z = 15 + 14 + 21 + 20 + 16 = 86 hours
