In this paper we propose a hybrid heuristic solution procedure for fuel cost minimization on gas transmission systems with a cyclic network topology, that is, networks with at least one cycle containing two or more compressor station arcs. Our heuristic solution methodology is based on a two-stage iterative procedure. In a particular iteration, at a first stage, gas flow variables are fixed in each network arc and optimal pressure variables in each network node are found via non-sequential dynamic programming. At a second stage, pressure variables are fixed and a short-term memory Tabu Search procedure is used for guiding the search in the flow variable space. Empirical evidence supports the effectiviness of the proposed procedure outperforming the best existing approach to the best of our knowledge.