In the petroleum supply chain, oil refined products are often delivered to distribution centers by pipelines since they provide the most reliable and economical mode of transportation over large distances. This paper addresses the optimal scheduling of a complex pipeline network with multiple branching lines. The main challenge is to find the optimal sequence and time of product injections/deliveries at input /output nodes in order to satisfy product demands with minimum costs. We propose a mixed integer linear problem (MILP) approach that is capable of detecting the interface volumes in any pipeline and handling the simultaneous deliveries to distribution depots. Numerical examples are solved to validate the proposed model.