Two of the main performance criteria of a water distribution system are that it is inexpensive to construct, operate, and maintain and that it operates in a reliable manner. These two criteria are often conflicting, thus implying that the decision maker needs to reach a compromise in scheduling mains for replacement. One way to facilitate this decision is to generate a trade-off surface that represents the compromise between the two objectives. This paper demonstrates the use of genetic algorithms to generate trade-off curves between cost and reliability for pipe replacement decisions. Curves for two planning scenarios are generated. The first identifies the trade-offs necessary for the Current conditions. The second allows the water authority to determine the required levels of future expenditure, given funding constraints, to meet a specified level of service over the entire planning horizon. Alternatively, it provides an estimate of the impact on performance of delaying expenditure.