The oil market in Taiwan is becoming very competitive nowadays than before, which is due to her recent entry into WTO and the liberalized Petroleum Management Law that allows international petroleum vendors to sell oil products in Taiwan market. For a competitor to become successful, the control of gas stations, pipelines， and storage tanks plays a key role, however, due to the space limitation and the residents' increasing awareness of environmental protection issues on the island, the construction of new storage tanks is being recognized as an issue next to impossible. Hence, any new vendors, undoubtedly, would have to rent tanks from existing oil companies for operation. Thus, tank owner must schedule tanks efficiently to satisfy the maintenance requirement， and, at the same time, meet the operation needs for itself and leaseholders. In this study, we examine the tank maintenance scheduling needs of an existing company, and investigate the performances of an evolutionary computing approach, which is based on genetic algorithm and simulated annealing. Experimental results with Integer Programming were used to highlight the problem with this conventional approach. We also conducted an extensive comparison with GA and GASA to confirm the superior performance of this hybrid approach in tank utilization and computation times.