Jobs’ temperature will decrease as their starting times delay in heat treating flow shop. In order to process the jobs normally, the worker has to reheat them or keep them in holding furnace. In response to this situation, this study considers a parallel machine scheduling problem with step-deteriorating jobs for minimizing the total tardiness and energy consumption. Firstly, a mixed integer programming model is proposed for the problem under study. Due to the intractability of the problem, a genetic -variable neighborhood search hybrid algorithm is designed to solve it. The algorithm use genetic operations to generate the solution, and then use the variable neighborhood search to improve the solution. The numerical tests show the proposed algorithm can efficiently reduce the total tardiness and energy consumption compared with standard genetic algorithm and mathematical model with standard solver Gurobi.