With every passing month, a number of new virtual enterprises emerge on the internet. Many companies have responded to the idea of distributed manufacturing in which the value adding activities comprising a finished product are dispersed geographically in a remote place. This study suggests an idea for selecting partners in a distributed manufacturing environment, which enables machining companies to share their capacities. A mathematical model is constructed to show how to minimize the sum of the operation and transportation costs based on alternative process plans considering several kinds of operation characteristics in the real world. Four heuristic algorithms are developed to get an optimal or near-optimal solution using tabu search since the model is proven NP-hard. Example problems are tested to illustrate their procedure and performance.