DOI : 10.17577/IJERTCONV5IS04013
- Open Access
- Total Downloads : 40
- Authors : G. Jothi, P. Saravanan
- Paper ID : IJERTCONV5IS04013
- Volume & Issue : NCETCPM – 2017 (Volume 5 – Issue 04)
- Published (First Online): 24-04-2018
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
A New Algorithm to Find the Optimal Feasible Assignment for an Assignment Problem
G. Jothi1
Department of Mathematics Kongunadu College of Engineering and Technology
Tiruchirappalli-621 215, Tamilnadu, India
P. Saravanan2
Department of Mathematics Kongunadu Polytechnic College
Tiruchirappalli-621 215, Tamilnadu, India
Abstract- The time minimizing assignment problem dealing with the allocation of n jobs to n persons is considered in this paper. One job is to be allotted to One person and each person does at least one job. All the persons start working on the jobs simultaneously. The aim of the present study is to find that feasible assignment which minimizes the total time for completing all the jobs. In this paper, we proposed a new algorithm to find the optimal feasible assignment. The proposed algorithm is very easy to understand and apply.
Keywords-Assignment problem, Proposed algorithm, Optimal feasible assignment.
-
INTRODUCTION
The Hungarian method is combinatorial Optimization Algorithm which solves the Assignment problem in polynomial time and which anticipated lateral prime-dual methods. It was developed and published by Harold W. Kuhn (1995), who gave the name Hungarian Method because the algorithm was largely based on the earlier works of two Hungarian Mathematicians: D Konig and Egarvary. Assignment problem is completely degenerated form of Transportation problem. It appears in
In this paper a new algorithm is proposed to find the optimal feasible assignment for Assignment problem within few steps. The solution obtained by this method is equal to that of Hungarian method.
-
ASSIGNMENT PROBLEM
Consider an assignment problem of n resources to n activities so as to minimize the overall cost or time in such a way that each resources can associate with one and only one job. The cost matrix is same as that of a Transportation problem except that availability at each resources and the requirement at each of the destinations is unity.
Let xij denote the assignment of i th resource to
j th activity such that,
x
1;if resource i is assigned to activity j.
ij 0; Otherwise
Then the mathematical formation of the Assignment problem is,
some decision making situations. Such as to assign tasks to
machines, workers to jobs, salesman to regions, requirements to suppliers etc. Assignment problem refers
n
M inZ
i1
n
Cij xij
j 1
to another special class of linear Programming problem in which the objective is to assign a number of resources to the equal number of activities at a minimum cost (or
n
Subject to
j 1
xij
1, for
i 1, 2,….., n
maximum profit). Different methods have been presented and various articles have been published on the subject
n
i1
xij
1,
for
j 1, 2,….., n
(Bertsekas, 1981; Basirzadeh, 2012; Balinski et al, 1964; Wright, 1990; Hung et al, 1980; Jonker et al, 1986) and for the history of these method (Frank, 2004; Pentico, 2007; Kuhn, 1955; Burkard, 1978).
xij
0or1for all i 1,2,…n and j 1,2,…n.
Mathematical formation of Assignment table
TABLE I
A1
A2
An
Available ai
R1
C11
C12
C1n
1
R2
C21
C22
C2n
1
Rm
Cm1
Cm2
Cmn
1
Requirement
b j
1
1
1
-
PROPOSED ALGORITHM TO FIND OPTIMAL FEASIBLE ASSIGNMENT FOR AN ASSIGNMENT
PROBLEM
Step: 1 Construct the Assignment table for the given Assignment problem. If it is unbalanced, convert into balanced.
Step: 2 Subtract the minimum element of each row from all the entries of the respective row. In the resulting Assignment table, subtract minimum element of each column from all the entries of the respective column. Now there will be at least one zero in each row and in each column in the reduced cost matrix.
Step: 3 Find the difference between first minimum and second minimum for each and every rows and columns.
Step: 4 Choose a row or column which has the maximum difference and assign to the cell having zero cost in that row or column.
If tie occurs in the maximum difference then select all these rows and columns and find the difference between the first minimum and third minimum. Now select a row or column which has the maximum difference and assign to the cell having zero cost in that row or column.
Step: 5 After performing step 4, delete the row and column for further calculation.
Step: 6 Check whether the resultant matrix possesses at least one zero in each row and in each column. If not, repeat step 2, otherwise go to step 7.
Step: 7 Repeat steps 3 to step 6 till only one value remains at last.
-
NUMERICAL EXAMPLES
Example: 1
A company has six machines which can process six different jobs. The processing time (minutes) of different jobs by different machines is presented in the following table. Our aim is to find the optimal feasible assignment of the jobs to the machines such that the total processing time is minimized.
A
B
C
D
E
F
1
10
15
12
18
14
13
2
17
14
22
16
19
20
3
12
15
13
8
12
9
4
11
16
15
22
21
18
5
13
10
17
19
15
10
6
15
8
14
25
16
18
Since the number of rows is equal to the number of columns, it is balanced. By using step 2, we obtain the following table.
A
B
C
D
E
F
1
0
5
0
8
0
3
2
3
0
6
2
1
6
3
4
7
3
0
0
1
4
0
5
2
11
6
7
5
3
0
5
9
1
0
6
7
0
4
17
4
10
A
B
C
D
E
F
Difference
1
0
5
0
8
0
3
0
2
3
0
6
2
1
6
1
3
4
7
3
0
0
1
0
4
0
5
2
11
6
7
2
5
3
0
5
9
1
0
0
6
7
0
4
17
4
10
4*
Difference
0
0
2
2
0
1
By using steps 3 to 4, we obtain the following table.
Here, row 6 has the maximum difference. So the cell (6, B) is selected for the assignment. Now delete the row 6 and column B.
Then by using steps 2 to 4, we obtain the following table
A
C
D
E
F
Difference
1
0
0
8
0
3
0
2
2
5
1
0
5
1
3
4
3
0
0
1
0
4
0
2
11
6
7
2/6*
5
3
5
9
1
0
1
Difference
0
2/3
1
0
1
Here, Tie occurs in the maximum difference for the row 4 and column C. We have to find the difference between first and third minimum in these rows and columns as shown in the above table. Now row 4 has maximum difference. So the cell (4, A) is selected for the assignment. Now delete the row 4 and column A.
Then by using steps 2 to 4, we obtain the following table
C
D
E
F
Difference
1
0
8
0
3
0
2
5
1
0
5
1
3
3
0
0
1
0
5
5
9
1
0
1
Difference
3*
1
0
1
Here, column C has maximum difference. So the cell (1, C) is selected for the assignment. Now delete the row 1 and column C.
Then by using steps 2 to 4, we obtain the following table
D
E
F
Difference
2
1
0
5
1/5
3
0
0
1
0
5
9
1
0
1/9
Difference
1/9*
0
1/5
Here, Tie occurs in the maximum difference for the rows 2 and 5, columns D and F. We have to find the difference between first and third minimum in these rows and columns as shown in the above table. Now row 5 and column D are having maximum difference. We can choose any one of these rows and columns. So the cell (3, D) is selected for the assignment. Now delete the row 3 and column D.
Then by using steps 2 to 4, we obtain the following table
E
F
Difference
2
0
5
5*
5
1
0
1
Difference
1
5
Here, Tie occurs in the maximum difference for the row 2 and column F. Now we can choose any one of these row and column. So the cell (2, E) is selected for the
assignment. Now, After deleting the row 2 and column E the assignment will be given to the cell (5, F) as shown in the above table.
Solution table:
A
B
C
D
E
F
1
10
15
12
18
14
13
2
17
14
22
16
19
20
3
12
15
13
8
12
9
4
11
16
15
22
21
18
5
13
10
17
19
15
10
6
15
8
14
25
16
18
So we can assign the jobs to the machines as shown in the following table:
Job
Machine
Time (in minutes)
1
C
12
2
E
19
3
D
8
4
A
11
5
F
10
6
B
8
The minimum time
68
Example: 2
A construction company has six crews. The skills of the crews differ from one another because of the difference in the composition of the crews. The company has five different projects on hand. The times (in days) taken by different crews to complete different projects are summarized as shown in the following table. Our aim is to find the best assignment of the crews to different projects such that the total time taken to complete all the projects is minimized.
A
B
C
D
E
1
30
39
31
38
40
2
43
37
32
35
38
3
34
41
33
41
34
4
39
36
43
32
36
5
32
49
35
40
37
6
36
42
35
44
42
Since the number of rows is not equal to the number of columns, it is unbalanced problem. After converting this problem from unbalanced into balanced by using our new algorithm, we will obtain the solution table as follows.
A
B
C
D
E
F
1
30
39
31
38
40
0
2
43
37
32
35
38
0
3
34
41
33
41
34
0
4
39
36
43
32
36
0
5
32
49
35
40
37
0
6
36
42
35
44
42
0
Solution table:
So we can assign the crews to the projects as shown in the following table;
Crew
Project
Time (Days)
1
C
31
2
B
37
3
E
34
4
D
32
5
A
32
6
F
0
The minimum time
166
-
CONCLUSION
In this paper a new algorithm is proposed to find the optimal feasible assignment for Assignment problems. We can apply this algorithm for any Assignment problem whether it is balanced or unbalanced. Two numerical examples are solved to illustrate our Proposed Algorithm.
The solution obtained by this Algorithm is equal to Hungarian Method. Therefore, we can reach the optimal feasible solution in less number of iterations by using our Proposed Algorithm.
The Proposed Algorithm is very easy to understand and to apply. This Algorithm can be used for solving the Assignment problems occurring in real life situations.
REFERENCES
-
Andras Frank., On Kuhns Hungarian Method- A tribute from Hungary,Wiley Inter Science Published Online ( 2004), 199-206.
-
Balinski. M.L, Gomory. R.E., A Primal Method for the Assignment and Transportation Problems, Management Science, 3 vol. 10 (1964).
-
David W. Pentico.,Assignment Problem: A Golden Anniversary Survey,European Journal of Operation Research 176 (2007), 774-793.
-
Dimitri. P. Bertsekas., A New Algorithm for the Assignment Problem, Mathematical Programming 21 (1981), 152- 171.Hadi Basirzadeh., Ones Assignment Method for solving Assignment Problems, Applied Mathematical Science, 47 vol.6 (2012), 2345-2355.
-
Harald W. Kuhn., The Hungarian Method for Assignment Problem, Naval Research Logistics Quarterly 2(1955), 83- 97.
-
Marcel Turkensteen. Diptesh Ghosh, Boris Goldengorin,
Gerald Sierksma., Tolerance- baced Branch and Bound
-
Algorithm for the ATSP, European Journal of Operational Research 189 (2008), 775-788.
-
Mings.S, Hung, Walter. O. Rom., Solving Assignment Problem by Relaxation, Operation Research, 4 vol. 28(1780), 969-982.
-
ainer E. Burkard., A General Hungarian Method for the Algebraic Transportation Problem, Discrete Mathematics, 22 (1978), 219-232.
-
Roy Jonker, Ton Volgenant., Improving the Hungarian Assignment Algorithm, Operation Research Letters, 4 vol. 5(1986). Shweta singh, Dubey.G.C, Rajesh Shrivastava., A Comparative Analysis of Assignment Problem, IOSR Journal of Engineering, Vol.2 Issue. 8 (2012), 01-15.
-
Wright.M.B, Speeding up the Hungarian Algorithm, Computers Operations Research, 1 vol. 17(1990), 95-96