Na literatura, há diversos trabalhos que investigam a otimização das paradas para limpeza dos trocadores de calor presentes nas unidades de destilação atmosférica de refinarias, visando minimizar o consumo de energia. Entretanto, estes trabalhos utilizam modelos de deposição simplificados, que não levam em conta a variação da taxa de deposição em função das condições operacionais. Buscando contornar esta limitação, o presente trabalho propõe uma abordagem de otimização baseada na solução de um sequência de problemas de programação linear inteira mista, onde a taxa de deposição é atualizada considerando o modelo de Ebert-Panchal. Cada um dos problemas indica quais trocadores devem ser limpos em um determinado instante de tempo, de tal forma que a combinação de seus resultados compõe a solução final da programação das limpezas. A aplicabilidade da metodologia proposta é ilustrada através de um exemplo típico de uma bateria de pré-aquecimento de uma refinaria.