TERM – a very simple and efficient method to solve assignment problems

摘要

An assignment problem (AP) is a particular case of a transportation problem, in which the objective is to assign (or allocate) a number of resources (say facilities) to an equal number of activities (say jobs) at an overall minimum total cost, distance, time (or maximum total profit). It occupies a very significant role in the real physical world for e.g. production planning, particular job tasks, economic etc. The most common method used to solve the APs is the Hungarian assignment method (HAM). In this paper, we make an effort to introduce a new approach to APs namely TERM for solving a wide range of APs with minimum effort of mathematical calculations. The proposed TERM method is based on the principle of reducing the given cost matrix to a matrix of opportunity costs (MOC) having at least one zero in each row and column and making assignments to the selected zero-entry cells of MOC which ensures best solution for a given AP. To verify the performance of the TERM method, 30 classical benchmark instances from the literature have been tested. Simulation results authenticate that the proposed TERM method is the most efficient method which produces optimal solution directly to 24 instances (i.e. 80% cases) next to the HAM.