Solution of Assignment Problem Using Graph Theory

Articles in Press

Document Type : Original Article

Authors

1 First Year Engineering, Finolex Academy of Management & Technology, Ratnagiri, Maharashtra, India

2 First Year Engineering, Finolex Academy of Management & Technology, Ratnagiri, Maharshtra, India

10.22121/aotp.2021.292134.1071

Abstract

The aim of this research is to demonstrate the use of concept of stable matching in graph theory to solve assignment problem of operation research. In assignment problem, objective is to assign m resources or m persons to n activities or n jobs with taking values of m and n same on one to one basis at a minimum cost or time, or at maximum profit; whereas matching in a graph is set of edges where no two edges share a common vertex and stable matching in a graph is basically a collection of stable marriages of m men and n women with taking values of m and n as same, where men and women are vertices in a graph. This paper solves an assignment problem by Hungarian assignment method which is a method of operation research. And also it employs an existing algorithm of finding stable matching in graph theory in a new way namely, stable assignment method to solve assignment problem of operation research. Also the solutions by both the methods have been compared. So, this study proposes use of graph theory to solve assignment problem of operation research.

Keywords

Annals of Optimization Theory and Practice

Articles in Press, Accepted Manuscript
Available Online from 12 August 2021

Files

Share

How to cite

Statistics