This paper deals with the multi-objective single-machine scheduling problem in agro-food industry. To solve this problem, a new hybrid algorithm is proposed. This new algorithm named SHGA/SA is composed of two well-known metaheuristics: genetic algorithms and simulated annealing. The results show that our new approach can be used to solve the single-machine scheduling problem efficiently and in a short computational time. Also, the results show that the hybrid algorithm outperforms both the GA and SA.