This paper studies and compares the results of a simple and fast heuristic method, genetic algorithm (GA), and the exhaustive search method (ES) concerning the minimization of fuel consumption of a natural gas compressor station (CS). The results, obtained for an input data set [natural gas flow rate of 150 million standard cubic meters per day (MMSCMD), suction pressure of 5.45MPa, and discharge pressure of 6.9MPa], showed that for a CS with similar turbo-compressor (TC) units, all of the applied methods achieved the same solution (fuel consumption rate of 3.620 kg/s). By contrast, for a CS with dissimilar TC units, the GA and ES methods attained a lower fuel consumption rate (3.738 kg/s) than that obtained by the heuristic method (3.753 kg/s). The effect of changing the CS flow rate, suction, and discharge pressures on optimal fuel consumption rate was also investigated. In the first case study, a 100 MMSCMD (or 100%) increase in the flow rate, 8.3bar (or 13%) increase in discharge pressure, and 8.3bar (or 14%) reduction in the suction pressure of the CS caused the optimal fuel consumption rate to increase by 2.41 kg/s (or 99%), 1.02 kg/s (or 33%), and 1.72 kg/s (or 60%), respectively. In the second case study, for the same changes of flow rate, discharge, and suction pressures mentioned previously, the optimal fuel consumption rate increased by 2.72 kg/s (or 112%), 1.03 kg/s (or 32%), and 1. 71 kg/s (or 58%), respectively.