The problem discussed in this paper is short-term scheduling of distribution of petroleum derivatives from a single oil refinery to a number of depots through a tree-structure pipeline. Scheduling product batches in pipelines is a very complex task with many constraints to be considered. Batches of refined products and grades are pumped back-to-back in the pipeline, often with no separation device between batches. In this work a continuous-time, MILP problem representation for tree-structure pipelines is proposed. The approach is successfully applied to a number of pipeline scheduling problems, including a real-world problem. The data and experimental results are reported. (C) 2010 Elsevier Ltd. All rights reserved.