With rapid advances of computing technologies and high speed networks, various high volume multimedia services have become popular in the Internet. Private Internet broadcasting is a typical way to support these services and overlay multicast technology is known to be a promisin g solution to support this method. In an overlay multicast network, members are dynamically joining or leaving their multicast group. To reduce frequent updates of multicast members and provide a reliable multicast route, overlay multicast trees are investiuated. The problem is formulated as a binary integer programming which maximizes the minimum link reliability for all multicast sessions. Tabu search heuristic is developed with repeated intensification and diversification. Robust computational result is obtained that is comparable to the optimal solution and applicable in real time. (c) 2005 Elsevier Ltd. All rights reserved.