International Journal of Latest Research in Science and Technology ISSN (Online):2278-5299

Volume 3, Issue 2: Page No.136-138 ,March-April, 2014

https://www.mnkpublication.com/journal/ijlrst/index.php

A MODIFIED APPROACH FOR ASSIGNMENT

METHOD
Anju khandelwal
Asst. Prof. , Dept. of Mathematics
Shri Ram Murti Smarak College of Engg. & Tech., Bareilly (India)

Abstract- The Assignment Problem is one of the most-studied, well known and important problems in Mathematics. It is one of the
fundamental Combinatorial Optimization Problem in the field of Optimization or Operations Research in Mathematics. It is a particular
case of Transportation Problem where the objective is to assign the resources to the activities so as to minimize total cost or maximize total
profit of allocation.
In this paper we proposed Modified Assignment Approach for solution of Assignment problem. The algorithm of this approach is
presented, and explained briefly with numerical instance to show its efficiency. Also its comparison with Hungarian Algorithm is shown.

Keywords – Balanced Assignment Problem, Hungarian Method, Optimization

n n
I. INTRODUCTION Min. Z   C ij xij
The assignment problem is a special type of Linear i 1 j 1
Programming Problem in which our objective is to assign n Subject to
number of jobs to n number of persons at a minimum cost/ n
maximum profit. Assignment may be persons to jobs, classes
to rooms, operators to machines, drivers to trucks, trucks to
x
i 1
ij  1 , j  1,2,3,................, n

delivery routes, or problems to research teams, etc... There n

are various ways to solve assignment problem. A well known
solution of assignment problem is defined by Kuhn[1] named
x
j 1
ij  1 , i  1,2,3,................., n

as Hungarian method. To find solutions to assignment

xij  {0,1} for i, j  1,2,............., n
problem, various another algorithms such as Neural
Network[2], Genetic Algorithm[3] etc. have been developed.
Over the past 50 years many variations of the classical With an assumption that jth job will be completed by
assignment problems are proposed e.g. Generalized ith person and
Assignment Problem, Quadratic Assignment Problem, 1, if ith person is assigned to jth job
Bottleneck Assignment Problem etc. However, much of the xij  
0, otherwise
decision making in the real world takes place in an
In this conventional assignment problem, the cost
environment where the objectives, constraints or parameter
coefficients are precise value. However in real life the
are not precise. Therefore a decision is often made on the
parameters of assignment cost are not precise due to time/cost
basis of vague information or uncertain data. In 1970,
for doing job by a person/ machine might be vary due to
Belmann and Zadeh[4] introduced the concept of fuzzy set
different reason, such as assigning person to different work.
theory into the decision making problems involving
uncertainty and imprecision. Fuzzy Assignment Problems III. PROPOSED METHOD
have received great attention in recent years.
a. Algorithm for Mininization Case:
II. THE BASIC DEFINITION Let X 1 , X 2 , X 3 ,.............. denote resources and A, B,
In Everyday life corresponding to each physical structure
C, ………. denote the activities. Now we perform the
there is some mathematical phenomena. Here we describe
mathematical model of assignment problem. Assume that following steps for solving assignment problem.
there are n jobs and n persons. These n jobs must be
1. Construct the cost matrix of the assignment problem.
performed by n persons, where the cost depends on the
Consider row as a resource and column as a activity.
particular work assignment. Let C ij be the cost if the ith
2. Now form two columns, where column 1 represents
person is assigned to the jth job. The problem is to find an resource and column 2 represents an activity. Under
appropriate assignment i.e. which job should be assigned to column 1, write the resource, say,
which person, so that the total cost for performing all the jobs X 1 , X 2 , X 3 ,..............
should be minimum (profit maximum). The mathematical
model of assignment problem is then given by
Publication History
Manuscript Received : 21 April 2014 136
Manuscript Accepted : 24 April 2014
Revision Received : 28 April 2014
Manuscript Published : 30 April 2014
 International Journal of Latest Research in Science and Technology.
3. Find minimum unit cost for each row, whichever activities under column 2. Continue this process for all
minimum value is available in the respecting column, the rows and write in term of Activities.
select it and write it in term of activities under column 2.
Continue this process for all the rows and write in term Brands Setup s1 s2 s3 s4 s5
of Activities.
4. For each resource; if there is unique activity then B1 s1 B1 4 6 7 5 11
assigned that activity for the corresponding resource, B2 s2 B2 7 3 6 9 5
hence we get our optimal solution. B3 s3 B3 8 5 4 6 9
5. If there is no unique activity for corresponding resources
B4 s3 B4 9 12 7 11 10
then the assignment can be made using following steps:
a. Find at which of any one resource has unique B5 s2 B5 7 5 9 8 11
activity and then assign that activity for the
corresponding resource. Next delete that row and its (Since we get unique setup for brand B1, so assign it and
corresponding column for which resource has delete the corresponding row and column.)Again repeat
already been assigned. the process.
b. Again find the minimum unit cost for the remaining
rows. Check if it satisfy step 4 then perform it.
Brands Setup s2 s3 s4 s5
Otherwise, check which rows have only one same
activity. B2 s2 B2 3 6 9 5
c. Next find difference between minimum and next B3 s3 B3 5 4 6 9
minimum unit cost for all those rows which have
B4 s3 B4 12 7 11 10
same activity. Assign that activity which has
maximum difference. Delete those rows and B5 s2 B5 5 9 8 11
corresponding columns for which those resources
have been assigned. Since no unique setup is there so find the difference
d. However if there is tie in difference for two and between minimum to next minimum for setup s2 and
more than two activity then further take the then select the max. difference. Here B5 having max.
difference between minimum and next to next difference so assign this brand to setup s2 and delete the
minimum unit cost. Next check which activity has corresponding row and column. again repeat the process
maximum difference, assign that activity.
6. Repeat steps 4 to 5 till all resources are assigned
uniquely to the corresponding activity. Brands Setup s3 s4 s5
7. Once all the jobs are assigned then calculate the total B2 s5 B2 6 9 5
n n
B3 s3 B3 4 6 9
cost by Total Cost   Cij xij .
B4 s3 B4 7 11 10
i 1 j 1

b. Numerical Example: Now min. to next min. difference is 2 and 4 so we assign

1. A company is engaged in manufacturing 5 brands of on max. difference and hence brand B4 is assigned to s3
packed snacks. It is having five manufacturing setups, and then brand B3 is assigned to s4.
each capable of manufacturing any of its brands, one at a
time. The cost to make a brand on these setups vary Brands Setup s3 s4
according to the following table:
B3 s3 B3 4 6
s1 s2 s3 s 4 s5 B4 s3 B4 7 11
B1 4 6 7 5 11
B2 7 3 6 9 5 Hence the optimum assignment is:
Assign Brand To Set up Cost (Rs.)
B3 8 5 4 6 9
B1 s1 4
B4 9 12 7 11 10 B2 s5 5
B5 7 5 9 8 11 B3 s4 6
Assuming five setups are s1 , s 2 , s3 , s 4 and s5 and five B4 s3 7
B5 s2 5
brands are B1 , B2 , B3 , B4 and B5 . Find the optimum
assignment of products on these setups resulting in the
minimum cost. Minimum total Cost = Rs. 27

Sol. For the given cost matrix, Find minimum unit cost for 2. Five men are available to do five different jobs. From
each row, whichever minimum value is available in the past records, the time (in hours) that each man takes to
respecting column, select it and write it in term of do each job is known and given in the following table:

ISSN:2278-5299 137
 International Journal of Latest Research in Science and Technology.
Man Job I III
I II III IV V A I , III A 2 2
A 2 9 2 7 1 D I D 4 7
B 6 8 7 6 1
C 4 6 5 3 1 Hence the optimum assignment is:
D 4 2 7 3 1 Man Job Min. Time Taken (Hours)
E 5 3 5 9 1 A III 2
B V 1
Find the assignment of men to jobs that will minimize
the total time taken. C IV 3
D I 4
Sol. For the given cost matrix, Find minimum unit cost E II 3
for each row, whichever minimum value is available in
the respecting column, select it and write it in term of
activities under column 2. Continue this process for all Minimum time taken = 13 hours.
the rows and write in term of Activities.
IV. CONCLUSION
Man Job I II III IV V In the past, many practitioners as well as researchers
A V A 2 9 2 7 1 applied Hungarian method in order to solve assignment
B V B 6 8 7 6 1 problems. The goal is to find an optimal assignment of agents
to jobs without assigning an agent more than once and
C V C 4 6 5 3 1 ensuring that all tasks are completed. The proposed method
D V D 4 2 7 3 1 uses a new linear space solution to solve balanced assignment
E V E 5 3 5 9 1 problems. Based on an experiment our proposed method
provides same optimal cost than of the Hungarian method. It
has been found that although the resultant obtained via this
(Since we get unique Job for Man A, B, C, D and E , so method is same but the numbers of Iterations have been
we find the difference between the minimum to next reduced which consecutively saves time and easier to
minimum and assign the max. value from all and delete perform. This approach is also useful for solving
the corresponding row and column.) Again repeat the transportation problem network flow problem etc.
process.
REFERENCES
Man Job I II III IV
[1] Kuhn, H.W., “The Hungarian Method for the Assignment Problem”,
A I , III A 2 9 2 7 Naval Research Logistics Quarterly, 2:83-97, 1995.
C IV C 4 6 5 3 [2] S. P. Eberhardt, T. Duad, A. Kerns, T. X. Brown, A. P. Thakoor,
“Competitive Neural Architecture for Hardware Solution to the
D II D 4 2 7 3 Assignment Problem”, Neural Network, 4(4), 431-442, 1991.
E II E 5 3 9 5 [3] D. Avis, L. Devroye, “An Analysis of a Decomposition Heuristic for
the Assignment Problem”, Oper. Res. Lett., 3(6), 279-283, 1995.
[4] L. A. Zadeh, Quantitative fuzzy semantics, Inf. Sci. 3, 159-176, 1971.
Since man C perform unique job IV so assign this and
delete the corresponding row and column. again repeat [5] H.W. Kuhn, On the Origin of the Hungarian Method, in: History of
Mathematical Programming – A Collection of Personal eminescences
the process (J.K. Lenstra,A.H.G. Rinnooy Kan, A. Schrijver, Eds) CWI
Amsterdam and North-Holland,Amsterdam, 1991, pp. 77-81.
Man Job I II III [6] G. R. Burkard, M. Dell'Amico, and S. Martello,“Assignment
Problems”, Siam Society for Industrial and Applied Mathematics,
A I , III A 2 9 2 Philadelphia, 2009.
D II D 4 2 7
E II E 5 3 9

For Man D and E job are not unique and minimum

difference is tie so min. to next min. difference is 3 and 4
so we assign on max. difference and hence man E is
assigned to job II.

ISSN:2278-5299 138