This paper presents a new heuristic method for solving constrained redundancy optimization problems in complex systems. The proposed method allows excursions over a bounded infeasible region, which can alleviate the risks of being trapped at a local optimum. Computational results show that our method performs consistently better than other heuristic methods (Shi, Kohda & Inoue, simulated annealing) in terms of solution quality. In terms of computing time, the Shi method is best while simulated annealing is the slowest. Comparing our and the Kohda & Inoue methods, we observe moderate increase in computing time for the former. In summary, if computing time is of primary concern, then we recommend the Shi method among the heuristic methods we considered. If, however, solution quality is of more concern and if one is willing to accept moderate increase in computing time for better solutions, then we believe that our method is an attractive alternative to other heuristic methods.