Title: An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
Conference (): Link
Journal (Information Processing Letters 2006): Link
This paper presents an approximation algorithm for minimizing makespan for weighted bipartite graph (each job has identical processing time on all machines). It can correspond to identical machine scheduling problem. The solution is based on modified Hungarian, with a complexity of O(U(U+V+E)).