This paper presents a novel approach to aid the operational decision-making of scheduling activities in a real-world pipeline, transporting heavy oil derivatives, which are products of less aggregate value, such as fuel oils, e.g. marine fuel. These products present special characteristics that influence their transport as the impossibility of being transferred at room temperature, due to their viscosity, or the use of shared tanks for different products. Thus, during the transport of such products, the entire pipeline network (and the tanks) must be maintained heated during all the pumping process. Such characteristics imply that a specific model oriented to this type of problem must be developed. The approach proposed in this work develops a decomposition procedure that uses a sequence of mathematic programming models and heuristics to solve the problem in hand. The proposed approach is tested using a real-world scenario, composed of a pipeline tree system. (C) 2014 Elsevier Ltd. All rights reserved.