Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking

摘要

The Many to Many (M-M) assignment problem is an important open problem where one task is assigned to many, but different, agents and one agent may undertake many, but different, tasks. The Kuhn-Munkres (K-M) algorithm is a famous and traditional process used in dealing with assignment problems. In this paper, we propose a solution to the M-M assignment problem by improving the K-M algorithm with backtracking (KMB). To demonstrate the solution's suitability, we prove that the proposed KMB algorithm is valid and that the worst time complexity of the KMB algorithm is O ((Sigma L-a[i])(3)), where L-a[i] denotes the maximum number of tasks that can be assigned to agent i. After that, we discuss several critical problems related to the algorithm and provide the necessary and sufficient conditions of solving the M-M assignment problem. Finally, we demonstrate, through experimentation, the validity, practicality and efficiency of the KMB algorithm. (C) 2016 Elsevier B.V. All rights reserved.