The role of mathematical formulation in solving the unbalanced assignment problem - Vasko, Francis J.; Lu, Yun; Song, Myung Soon (Universitas Ahmad Dahlan, 2026)
In a 2019 paper, the authors claim to have developed a modified Hungarian method that performs better than a number of other solution methods for the unbalanced assignment problem (UAP) based on the solution of one UAP instance that has been discussed in the literature. The purpose of this short paper is to demonstrate that the math formulation used in the 2019 paper was not as restrictive as the standard one commonly used in the literature and therefore the comparison is not valid. The commonly used UAP math formulation not only tries to minimize cost, but also tries to level load the jobs onto the machines. The formulation from the 2019 paper allows many jobs to be assigned to a low-cost machine. Hence solutions (not even optimums) to the 2019 formulation can be better than the optimal solution using the standard UAP math formulation. Additionally, it will be shown that the Modified Hungarian method proposed in the 2019 paper does not generate guaranteed optimums to the math formulation used in that paper (let alone the standard UAP formulation). An 8-job and 5-machine assignment problem that appeared in the literature will be used to illustrate the points mentioned above.