Palette re-ordering is a class of pre- processing methods aiming at finding a permutation of color palette such that the resulting image of indexes is more amenable for compression. The efficiency of lossless compression algorithms for fixed-palette images (indexed images) may change if a different indexing scheme is adopted. Obtaining an optimal re-indexing scheme is suspected to be a hard problem and only approximate solutions have been provided in literature. In this paper, we explore a heuristic method to improve the performances on compression ratio. The results indicate that the proposed approach is very effective, acceptable and proved.