An exact algorithm for constrained k-cardinality unbalanced assignment problem

Abstract: An assignment problem (AP) usually deals with how a set of persons/tasks can be assigned to a set of tasks/persons on a one-to-one basis in an optimal manner. It has been observed that balancing among the persons and jobs in several real-world situations is very hard, thus such scenarios can be seen as unbalanced assignment models (UAP) being a lack of workforce. The solution techniques presented in the literature for solving UAP’s depend on the assumption to allocate some of the tasks to fictitious persons; those tasks assigned to dummy persons are ignored at the end. However, some situations in which it is inevitable to assign more tasks to a single person. This paper addresses a practical variant of UAP called k-cardinality unbalanced assignment problem (k-UAP), in which only of persons are asked to perform jobs and all the persons should perform at least one and at most jobs. The k-UAP aims to determine the optimal assignment between persons and jobs. To tackle this problem optimally, an enumerative Lexi-search algorithm (LSA) is proposed. A comparative study is carried out to measure the efficiency of the proposed algorithm. The computational results indicate that the suggested LSA is having the great capability of solving the smaller and moderate instances optimally.

How to cite this paper

 Prakash, A., Balakrishna, U & Thenepalle, J. (2022). An exact algorithm for constrained k-cardinality unbalanced assignment problem.International Journal of Industrial Engineering Computations , 13(2), 267-276.

Refrences

Arora, S., & Puri, M. C. (1998). A variant of time minimizing assignment problem. European Journal of Operational Research, 110(2), 314-325.
Bai, G. Z. (2009, December). A new algorithm for k-cardinality assignment problem. In 2009 International Conference on Computational Intelligence and Software Engineering (pp. 1-4). IEEE.
Belik, I., & Jörnsten, K. (2016). A new Semi-Lagrangean Relaxation for the k-cardinality assignment problem. Journal of Information and Optimization Sciences, 37(1), 75-100.
Bhavani, V., & Murthy, M. S. (2006). Truncated M-travelling salesmen problem. Opsearch, 43(2), 152-177.
Bhunia, A. K., Biswas, A., & Samanta, S. S. (2017). A genetic algorithm-based approach for unbalanced assignment problem in interval environment. International Journal of Logistics Systems and Management, 27(1), 62-77.
Dell'Amico, M., & Martello, S. (1997). The k-cardinality assignment problem. Discrete Applied Mathematics, 76(1-3), 103-121.
Dell'Amico, M., Lodi, A., & Martello, S. (2001). Efficient algorithms and codes for k-cardinality assignment problems. Discrete Applied Mathematics, 110(1), 25-40.
Feng, Y., & Yang, L. (2006). A two-objective fuzzy k-cardinality assignment problem. Journal of Computational and Applied Mathematics, 197(1), 233-244.
Gabrovšek, B., Novak, T., Povh, J., Rupnik Poklukar, D., & Žerovnik, J. (2020). Multiple Hungarian Method for k-Assignment Problem. Mathematics, 8(11), 2050.
Iampang, A., Boonjing, V., & Chanvarasuth, P. (2010, December). A cost and space efficient method for unbalanced assignment problems. In 2010 IEEE International Conference on Industrial Engineering and Engineering Management (pp. 985-988). IEEE.
Votaw, D.F., & Orden, A. (1952) ‘The personnel assignment problem’, Symposium on Linear Inequalities and Programming, Scoop 10, US Air Force, pp.155–163.
Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1‐2), 83-97.
Kumar, A. (2006). A modified method for solving the unbalanced assignment problems. Applied Mathematics and Computation, 176(1), 76-82.
Kumar, T. J., & Purusotham, S. (2017). An exact algorithm for k-cardinality degree constrained clustered minimum spanning tree problem. In IOP Conf. Ser. Mater. Sci. Eng. (Vol. 263, p. 042112).
Kumar, T., & Purusotham, S. (2018). The degree constrained k-cardinality minimum spanning tree problem: a lexi-search algorithm. Decision Science Letters, 7(3), 301-310.
Majumdar, J., & Bhunia, A. K. (2012). An alternative approach for unbalanced assignment problem via genetic algorithm. Applied Mathematics and Computation, 218(12), 6934-6941.
Malhotra, R., & Bhatia, H. L. (1984). Variants of the time minimization assignment problem. Trab. Estad. Invest. Oper., 35(3), 331-338.
Sundara Murthy, M. (1976). A bulk transportation problem. Opsearch, 13(3-4), 143-155.
Thenepalle, J. K., & Singamsetty, P. (2018). Bi-criteria travelling salesman subtour problem with time threshold. The European Physical Journal Plus, 133(3), 1-15.
Thenepalle, J. K., & Singamsetty, P. (2019). Lexi-search algorithm for one to many multidimensional bi-criteria unbalanced assignment problem. International Journal of Bio-Inspired Computation, 14(3), 151-170.
Volgenant, A. (2004). Solving the k-cardinality assignment problem by transformation. European Journal of Operational Research, 157(2), 322-331.
Yadaiah, V., & Haragopal, V. V. (2016). A new approach of solving single objective unbalanced assignment problem. American Journal of Operations Research, 6(1), 81-89.