It is believed that agile manufacturing is the twenty-?rst century manufacturing enterprise strategy and should be realized by agile virtual enterprise (AVE) which is dynamically con?gured for the manufacturing of one or more products. Agile manufacturing creates a signi?cant challenge for the partner selection in con?guring an AVE. This paper presents a brief introduction to the task decomposition for the manufacturing of a product in multisite environment. A bidding process should be carried out for each task so as to get the information necessary for the con?guration of AVE. To minimize the manufacturing cost, an integer programming (IP) formulation is presented for the partner selection problem. The IP formulation is then transformed into a graph-theoretical formulation by taking the advantage of the precedence relationship between the tasks. The graph obtained turns out to be a directed multipartite graph. Based on the graph-theoretical formulation, an ef?cient solution algorithm is proposed for the problem. It is shown that the algorithm is polynomial bounded. Therefore, it is applicable to large practical problems.