To deal with the partner selection problem with fuzzy completion time and fuzzy due date in a virtual enterprise, a multi-objective optimization model was proposed. The objectives of the optimization model were to maximize the minimum customer satisfaction, the average customer satisfaction, and minimize the completion cost. And then, the deviation method of minimum subordinative degree was used to convert the multi-objective problem into several single-objective optimization problems that were solved by an adaptive genetic algorithm. By introducing fuzzy number processing methods into the fitness function, the partner selection problem with fuzzy numbers was solved. Finally, the simulation results indicate the feasibility and effectiveness of the proposed method.