Till now, many methods and algorithms have been presented to solve linear sum assignment problem and each one has some advantages and disadvantages. For example Hungarian algorithm, that is one of the most well-known algorithms, has a good performance for many problems, but its solution time in some problems is too high. Considering that linear sum assignment problem is used in other problems such as the quadratic assignment problem, the traveling salesman problem, the vehicle routing problem, etc. a solution method with good execution time is highly desirable. The negative dual rectangle cancellation method is a new method for solving linear sum assignment problem. The main goal of this thesis is to introduce new algorithms and methods for finding Negative dual rectangles in the cost matrix of assignment problem. For this purpose, we first present some heuristics and an exact method based on mathematical modeling and then we examine and compare six methods of solving assignment problem, including our heuristics and exact method, Hungarian algorithm and also their combination. The results show very good performance of our heuristic methods that can be used in different linear sum assignment problem.
