Assignment problem on fuzzy graphs

The assignment problem is the earliest combinatorial optimization problem, in which the decision maker has to assign some agents to some tasks in a way that the total cost is minimized. From the vision of graph theory, the problem is the same matching problem defined on a bipartite graph. This paper addresses a natural extension of the problem, in which the underlying graph is a fuzzy graph. This extension is meaningful in some applicable situations that there are one expert’s opinions about the relative importance of any agent (task) and the relative satisfactory of any imputation. The goal of the decision maker is to make a decision not only regrading the costs, but also the expert’s opinions. This paper concentrates on solving this problem. It first models the problem as a triobjective optimization. Then, the -constraint method is applied to propose an efficient algorithm for finding a compromise solution.

کلیدواژه ها:

Assignment problem ، fuzzy graphs ، satisfactory solution