Application of k-person and k-task maximal efficiency assignment algorithm to water piping repair

摘要

Solving the absent assignment problern of the shortest time limit in a weighted bipartite graph with the minimal weighted k-matching algorithm is unsuitable for situations in which large numbers of problems need to be addressed by large numbers of parties. This paper simplifies the algorithm of searching for the even alternating path that contains a maximal element using the minimal weighted k-matching theorem and intercept graph. A program for solving the maximal efficiency assignment problem was compiled. As a case study, the program was used to solve the assignment problem of water piping repair in the case of a large number of companies and broken pipes, and the validity of the program was verified.