Arguably, the natural gas transmission pipeline infrastructure in the U.S. represents one of the larges and most complex mechanical systems in the world. This system delivers about 0.623 tcm (22 tcf) of natural gas per year and is mad up of over 4.828x105 km (300,000 miles) of pipe driven by 8,000 engines and 1,000 gas turbines with 2.983x105 MW (40 million horsepower) of compression capacity. The system produces over 1.86x109 MW-hrs (250 billion hp-hrs) of compression power every year. One of the goals of operation of this huge system is to find the minimum fuel consumption while maintaining the desired throughput of natural gas. In this paper, we present a systematic approach for operation the units of a compressor station to meet a specified throughput profile. The first step in developing this approach is the derivation of a numerical method for analyzing the flow through the pipeline under transient on-isothermal conditions. We have developed and verified a fully implicit finite difference formulation that provides this analysis capability. Next the optimization of the compressor stations is formulated as a standard nonlinear programming problem (NLP). The minimum acceptable throughput is imposed as a constraint. This NLP is solved numerically by a sequential unconstrained minimization technique, using the mathematical model of the system for the required function evaluations. The results show that this approach is very effective in reducing the fuel consumption. An application of this methodology for selecting the number of compressors to be shutdown for most fuel-efficient operation is also presented. Our results further indicate that station level optimization produces results comparable to those obtained by network level optimization. This is very significant because it implies that the optimization can be done locally at the station level which is computationally much easier.