A NEW SOLUTION APPROACH FOR ASSIGNMENT PROBLEM
Journal Name:
- İTÜ Dergisi
Key Words:
Keywords (Original Language):
| Author Name | University of Author | Faculty of Author |
|---|---|---|
Abstract (2. Language):
The purpose of this study is to present a new solution approach for the assignment problem. In assignment problem, there are (m) individuals are to be assigned to (m) jobs. If the individual (i) assigned to job (j), the cost incurred will be (cij), and accordingly the cost matrix is denoted by C. It is desired to find the minimal cost assignment or a one-to-one matching of individuals to jobs. There are many solution methods for this problem, but the simplicity and robutsness of the Hungarian method makes it the best known method among all others. The Hungarian method solves the problem by converting the cost matrix into a reduced matrix systematically at each iteration. A part of this process is finding fewest number of lines to cover all zero elements in the reduced matrix. When the size of the problem increases and reduced matrix contains many zeros, it is a tedious task to find minimum number of lines and the way of drawing them. The Hungarian method has an ambiguity at this point. A solution method is presented in this study to eliminate this ambiguity. A systematic and simple procedure is defined to find the fewest number of lines to cover all zero elements in the reduced matrix.
Bookmark/Search this post with
Abstract (Original Language):
Bu çalışmanın amacı klasik atama problemi için özgün bir çözüm yöntemini tanıtmaktır. Atama probleminin çözümünde en çok bilinen yöntem Macar yöntemidir. Bu yöntemde maliyet matrisi her seferinde sistematik bir şekilde yeni bir indirgenmiş matrise dönüştürülerek çözüme gidilmektedir. Yöntem gereği indirgenmiş maliyet matrisindeki sıfır elemanlar en az sayıda çizgi ile kapatılmakta ve buna göre matris üzerinde işlem yapılmaktadır. Ancak problemin büyüklüğü arttıkça ve indirgenmiş maliyet matrisinde sıfır eleman sayısı çoğaldıkça, matristeki sıfır elemanlarını kapatmak üzere gereken en az sayıda çizgi sayısı ve bu çizgilerin nasıl çizilmesi gerektiği sorunu ortaya çıkar. Bu çalışmada Macar yöntemindeki bu boşluğu doldurmak üzere özgün bir yöntem tanıtılmaktadır.
FULL TEXT (PDF):
- 1
73-79