Agility is the competitive advantage in the global manufacturing environment. It is believed that the agility can be realized by dynamically reconfigurable virtual enterprise. However, the configuration of virtual enterprises is a challenge to us. In selecting the partners for the reconfiguration of virtualenterprise, many factors should be taken into consideration. However, the manufacturing cost and time to market are the most important factors. In this paper, in considering the completion time as a constraint we model the partner selection problem by an integer programming formulation to minimize the manufacturing cost. The formulation is then transformed into a graph-theoretical formulation and a 2-phase algorithm is developed to solve the problem. In the first phase, a polynomial bounded algorithm is proposed to find the earliest completion time, so we obtained a feasible solution. In phase 2, we improve the solution by exchanging the candidate partners in keeping the solution in the feasible region. Although we may not find the optimal solution for the problem by the improvement algorithm, the objective is reduced iteration by iteration. Thus, the algorithm is efficient and can be applicable to practical problems. An illustrative example is presented to show the application of the proposed algorithm.