A New Method for Finding an Optimal Solution of Assignment Problem

Abstract

In this paper a new method is proposed for finding an optimal solution of a wide range of assignment problems, directly. A numerical illustration is established and the optimality of the result yielded by this method is also checked. The most attractive feature of this method is that it requires very simple arithmetical and logical calculations. The method is illustrated through an example.

Introduction

I. INTRODUCTION

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

II. DEFINITION OF ASSIGNMENT PROBLEM

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let cij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

III. BALANCED ASSIGNMENT

Balanced Assignment Problem is an assignment problem where the number of facilities is equal to the number of jobs. Unbalanced Assignment Problem: Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs.

IV. UNBALANCED ASSIGNMENT

Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one, a dummy facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time.

V. FORMULATION OF ASSIGNMENT PROBLEM

Consider the problem of assigning n jobs to n machines (one job to one machine). Let Cij be the cost of assigning ith job to the jth machine and xij represents the assignment of ith job to the jth machine.

VIII. OPTIMALITY CHECK

To find whether the solution obtained is optimal or not we apply Hungarian Method for the above problem. And after applying the Hungarian method the total cost of the problem is Rs 29. It can be seen that value of objective function obtained by our method is same as that of Hungarian Method.

Hence the solution obtained by our method is also optimal.

IX. ACKNOWLEDGEMENT

Thank you to P.Devi Abirami, Assistant Professor, Department of Mathematics, Dr. SNS Rajalakshmi College of Arts and Science, Coimbatore,Tamil Nadu, India for giving full support to this research.

Conclusion

Thus it can be concluded that our method provides an optimal solution in fewer iterations, for the solution of an Assignment Problem. As this method consumes less time and is very easy to understand and apply, so it will be very helpful for decision makers who are dealing with logistic and supply chain problems. The future research work may be considered to introduce the mathematical formulation of the proposed method and algorithm.

References

[1] Maximin Zero Suffix Method for Solving Assignment Problems. https://www.elixirpublishers.com/articles/1480602780_ELIXIR2016095356C.pdf [2] https://ijisrt.com/wp-content/uploads/2019/10/New-Approach-to-Solve-Assignment-Problem.pdf [3] https://www.researchgate.net/publication/325223720_An_Assignment_Problem_and_Its_Application_in_Education_Domain. [4] https://www.iosrjournals.org/iosr-jm/papers/Vol13-issue2/Version-4/M1302048488.pdf [5] https://www.researchgate.net/publication/344559969_Development_of_an_accelerating_hungarian_method_for_assignment_problems. [6] https://en.wikipedia.org/wiki/Assignment_problem.

Copyright

Copyright © 2022 Priyadharshini L S, P Devi Abirami. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.