Reordered Mutation Operator in Evolutionary Programming: An Assignment Problem Application
by
Muzaffar A. Shaikh
Florida Institute of Technology, Florida
Coauthors: Teeranan Nandhakwang (Florida Institute of Technology, Florida)

In the traditional approach, the assignment problem can be solved by the Hungarian method.. The Hungarian method or the Greedy algorithm as it is termed, does not perform well for large-scale problems. The proposed method improves evolutionary programming (EP) with reordered mutation operator in handling a large-scale assignment problem. Under certain test scenarios the EP based algorithm outperforms the Hungarian method in computation time and in finding the minimum total cost.

The assignment problem is a particular class of transportation linear programming problems with the objective is to find a minimum-cost to assign jobs to workers. Here, resources are allocated to the activities on one-to-one basis. The assignment problem is particularly interesting because many seemingly different problems maybe solved as assignment problems. Moreover, it is an important example of a combinatorial optimization problem; that is, a problem that seeks the best possible arrangement of objects among a specified set of many possible arrangements. Typically, the best possible arrangement means an arrangement with the smallest total cost possible.

In the traditional approach, the assignment problem can be solved by the Hungarian method [1], which is named in honor of the Hungarian mathematician D. König who proved an essential theorem as part of the development of his method. However, this method does not perform well in term of computation time for large-scale problems [1, 2]. New methods need to be developed to overcome this problem. This paper proposes evolutionary programming with reordered mutation operator that provided better computation time results than the Hungarian method.

References [1] Winston, W. L. (1993). Operations Research: Applications and Algorithms 3rd ed: Wadsworth Publishing Company.

[2] Gillett, B. E. (1976). Introduction to Operations Research: A Computer-Oriented Algorithmic Approach: McGraw-Hill.

Date received: October 9, 2002