Personnel assignment problem with hierarchical ordering constraints

In the standard assignment problem, there is no constraint on the partitions of the bipartite graph. The only objective is to maximize the summation of the weights of the matched edges. Any node in one partition can be matched with any node in the other partition without any restriction. In this paper, we study a variation of the standard assignment problem, having some ordering constraints on the partitions of the bipartite graph. We call this problem as 'assignment problem with hierarchical ordering constraint' (APHOC). As its name implies, hierarchical constraints are introduced on both partitions, and, the matching between the partitions should respect these hierarchical ordering constraints. A natural version of such constraints occurs in personnel assignment problem, where one of the partitions is a level graph representing the ranks of personnel, and the other one is a forest, representing the positions. We will first show that this problem is NP-complete. Then, we will investigate some heuristic and approximate solutions. Finally, we will study the performances of these solutions. (C) 2003 Elsevier Ltd. All rights reserved.