Abstract: Network coding is a kind of novel network transmission technology, which can achieve the network multicast capacity. In this paper, an overhead optimization problem (OOS) is presented to minimize the sum cost of network coding and network link in networks with network coding. This optimization takes not only the link transmission overhead but also the coding overhead incurred by network coding into consideration. By using two different network information flow models, which are the receivers data flow mixture model and the data element flow model, the general forms of both kinds of overhead are presented separately. As this problem is NP-hard, only the approximately optimized solution can be got through heuristic algorithms. In the experiments, different genetic algorithms performance are evaluated under two different information flow models and different random generated topologies. Because it makes the optimization problem even more complex that takes the network coding overhead into consideration, the computed approximate solution may be poorer than only considering the network link cost. Simulation results show that only under the condition of the overhead coefficient γ＞1000, the joint optimization can get a better solution. This result may have considerable importance when network coding comes into practice in the future.