REVISED ONES ASSIGNMENT METHOD FOR SOLVING ASSIGNMENT PROBLEM

GHADLE K.P.¹*, MULEY Y.M.^2
1Department of Mathematics, Dr. Babasaheb Ambedkar Marathwada University, Aurangabad- 431 004, MS, India.
²Department of Mathematics, Dr. Babasaheb Ambedkar Marathwada University, Aurangabad- 431 004, MS, India.
* Corresponding Author : drkp.ghadle@gmail.com

Received : 18-04-2013     Accepted : 02-05-2013     Published : 05-09-2013
Volume : 4     Issue : 1       Pages : 147 - 150
J Stat Math 4.1 (2013):147-150

The assignment problem (AP) is a special case of the transportation problem, in which the objective is to assign a number of resources to the equal number of activities at a minimum cost (or maximum profit). It has great significance subject discussed in real physical world for e.g. production planning, particular job tasks, economic etc. We endeavor in this paper to introduce a new approach to assignment problem namely “Revised Ones Assignment Method (ROA)” for solving wide range of problem. In ROA method first we define assignment matrix, then reduced matrix till it has at least one in each row and column. The new method is based on creating some ones in the assignment matrix and to complete exact assignment to their ones, we have added new step to ROA algorithm can be utilized for all types of AP with maximize or minimize objective functions and at last we have illustrate some numerical examples.

Assignment problem, linear integer programming, Revised Ones Assignment Method (ROA).

Assignment problem (AP) is completely degenerate form of a transportation problem. It appears in some decision-making situations. Such as to assign tasks to machines, workers to jobs, salesmen to regions, requirements to suppliers etc. AP refers 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 maximum profit). Different methods have been presented for assignment problem and various articles have been published on the subject. See [7,8] and [5,6,9] for the history of these method.
So far in the literature, there are mainly four methods – Enumeration method, Simplex method, Transportation method and Hungarian method, which is one of the best methods available for solving an AP. For AP there is alternate method is available, which is Ones Assign Method which is already proved [1,2] .
In this paper we revised “Ones Assignment Method” to achieve exact optimal solution, which is same as that of Hungarian method.

Let AP of n resources to n activities so as to minimize the overall cost or time in such a way that each resources can associated with one and only one job. The cost matrix (C_ij) is given as below.

Activity






The cost matrix is same as that of a transportation problem except that availability at each of the resources and the requirement at each of the destinations is unity.
Let X_ij denote the assignment of i^th resources to j^th activity such that,



Then the mathematical formulation of the assignment problem is,

(1)

Subject to the constraints,



(2)

This section presents a new method to solve the assignment problem which is different from the preceding method. We call it “Revised Ones Assignment Method” because of making assignment in terms of ones.
The new method is based on creating some ones in the assignment matrix and then tries to find a complete assignment in terms of ones. By a complete assignment we mean an assignment plan containing exactly n assigned independent ones, one in each row and one in each column.
Now, consider the assignment matrix where C_ij is the cost or effectiveness of assigning i^th machine.





The new algorithm is as follows.
Let (1-2) be an assignment problem in which the objective function can be minimized or maximized.

In a minimization (maximization) case, find the minimum (maximum) element of each row in the assignment matrix (say a_i) and write it on the right hand side of the matrix.





Then divide each element of i^th row of the matrix by a_i. These operations create at least one ones in each rows.
In term of ones for each row and column do assignment. Otherwise go to step 2.

Find the minimum (maximum) element of each column in assignment matrix (say b_j), and write it below j^th column. Then divide each element of j^th column of the matrix by b_j.
These operations create at least one ones in each columns. Make assignment in terms of ones. If no feasible assignment can be achieved from step (1) and (2) then go to step 3.





Note: In a maximization case, the end of step 2 we have a fuzzy matrix. Which all elements are belong to [0,1] and the greatest is one [4] .

Draw the minimum number of lines to cover all the ones of the matrix. If the number of drawn lines less than n, then the complete assignment is not possible, while if the number of lines is exactly equal to n, then the complete assignment is obtained.

If a complete assignment program is not possible in step 3, then select the smallest (largest) element (say d_ij) out of those which do not lie on any of the lines in the above matrix. Then divide by d_ij each element of the uncovered rows or columns, which d_ij lies on it. This operation creates some new ones to this row or column.
If still a complete optimal assignment is not achieved in this new matrix, then use step 4 and 3 iteratively. By repeating the same procedure the optimal assignment will be obtained.
(To assign one we have add Step 5 which is mentioned below.)

i) For minimization problem select max number from calculated matrix and write it on right hand side as well as bottom side.
• To assign one, start from min number of columns (bottom side) and select ones.
• If there are more than one ones in any column then ignore temporarily, and give last priority to that column.
• If still there are identical ones in column then give the priority to max number of rows (right hand side).
Or
ii) For maximization problem select min number from calculated matrix and write it on right hand side as well as bottom side.
• To assign one, start from max number of columns (bottom side) and select ones.
• If there are more than one ones in any column then ignore temporarily, and give last priority to that column.
• If still there are identical ones in column then give the priority to min number of rows (right hand side).

One question arises here. What to do with non square matrix? To make square, a non square matrix, we add one artificial row or column which all elements are one. Thus we solve the problem with the new matrix, by using the new method. The matrix after performing the steps reduces to a matrix which has ones in each rows and columns. So, the optimal assignment has been reached.

The following examples may be helpful to clarify the proposed method.
Example 1- Consider the following assignment problem. Assign the five jobs to the three machines so as to minimize the total cost





Find the minimum element of each row in the assignment matrix (say ai), and write it on RHS as follows





Then divide each element of i^th row of the matrix by a_i. Thus it create ones to each rows, and the matrix reduces to following matrix.





Now next to find the minimum element of each column in assignment matrix (say b_i), and write it below that column. Then divide each element of j^th column of the matrix by b_j.











The minimum number of lines required to pass through all the ones of the matrix is 5.



By using Step 5,
We select max number from matrix for minimization problem and write it to right as well as bottom side.
In column 2 contain more than one ones, so we will give it last priority.
To assign ones from matrix select min number from columns (bottom side). So 2.3 is min number from all other and assign ones.
After giving last priority to column 2, there is 5th column which has identical ones. At this stage give the max priority (right hand side) to select ones. (in 5^th column there are two ones, in which we select max number from right hand side which is 3.8)







And we can assign the ones and the solution is (1,5), (2,3), (3,4),(5,2) and minimum cost is 24.
Example 2- A Manager has 4 subordinates and 4 tasks. The subordinates differ in efficiency. His estimate of the production each would do is given in table. How the task should be allocated one to one man, so that total production is maximized.





Row Reduction:





Column Reduction:





The minimum number of lines required to pass through all the ones of the matrix is 4.





By using Step 5,
We select min number from matrix for maximization problem and write it to right as well as bottom side.
In column 2 contain more than one ones, so we will give it last priority.
To assign ones from matrix select max number from columns (bottom side). So 0.5 is max number, but 0.5 contain in identical ones column which has already given last priority, then select next max number which is 0.40 and start to assign ones.







And we can assign the ones and the solution is (1, II), (2, IV), (3, I), (4, III) and maximized production is 114.

Travelling Salesman Problem (TSP) as an AP.
Example 3- Consider an Eight city TSP for which the cost between the city pairs are as shown in the [Table-2] . Find the tour the salesman so that the cost of travel is minimal [3] .





Row Reduction





Column Reduction





The minimum number of lines required to pass through all the ones of the matrix is 8.





By using Step 5,
1. We select max number from matrix for minimization problem and write it to right as well as bottom side.
2. In column 7 contain more than one ones, so we will give it last priority.
3. To assign ones from matrix select min number from columns (bottom side). So 6.5 is min number from all other and assign ones.







And we can assign the ones and the solution consist in three cycle which are (1,2),(2,3),(3,1); (4,5),(5,6),(6,4); (7,8),(8,7) and minimum cost is 17.

In this paper, a new revised method was introduced to assign ones directly and for solving assignment problem. This method can be used for maximize as well as minimized objective functions of Assignment problem. The new method is based on creating some ones in the assignment matrix, and finds an assignment in terms of the ones.

[1] Hadi Basirzadeh (2012) Applied Mathematical Sciences, 6(47), 2345-2355.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Singh S., Dubey G.C., Shrivastava R. (2012) IOSR Journal of Engineering, 2(8), 01-15.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Turkensteen M., Ghosh D., Boris Goldengorin, Gerard Sierksma (2008) European Journal of Operational Research, 189, 775-788.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Zimmermann H.J. (1996) Fuzzy Set Theory and its Applications, 3rd ed., kluwer Academic, Boston.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Pentico D.W. (2007) European Journal of Operation Research, 176, 774-793.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Singh S. (2011) International Journal of Operation Research and Information System, 3(3), 87-97.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Bazarra M.S., Jarvis J.J., Sherali H.D. (2005) Linear Programming and Network Flows, John Wiley.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Goel B.S., Mittal S.K. (1982) Operations Research, 5th ed., 2405-2416.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Taha H.A. (2007) Operations Research, an Introduction, 8th ed., Pearson Education, Inc. Pearson.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Table 1- Estimate of the Production
	Table 2- Eight city TSP for which the cost between the city pairs