In this paper we investigate the performance of simulated annealing (SA) and genetic algorithm (GA) in preventive part replacement for minimum downtime maintenance planning. Therefore some evaluation criteria are explained in order to analyze the performance of the algorithms. So it can be decided which algorithm is more suitable to apply in preventive part replacement.