The resulting MINLP problem is very complex and finding the global optimum is a challenging task. Solving this problem can use two methods, namely deterministic and metaheuristic. Deterministic method requires enough knowledge to determine areas that can provide global optimum solution. This method sometime provide unconvergen solution. Another method is metaheuristic method that simple and promising global optimum solution without introducing any approximations or simplifying assumptions. This method works without influenced by the previous optimization results. One of metaheuristic algorithms is Genetic Algorithm (GA). In this paper, the GA will be used to solve the optimization of cleaning schedule of Heat Exchanger Network (HEN) in a refinery Crude Preheat Train (CPT). The results showed that efficiency of HEN 23% increased which can be translated in IDR 14.1 Billion of fuel saving. Metaheuristic algorithm always provide a solution at the end of optimization’s iteration and it can be run continuesly in order to get more optimal solution.