We present an effective scheduling heuristic for realistic production planning in a petrochemical blending plant. The considered model takes into account orders spanning a multi-product portfolio with multiple bills of materials per product, that need to be scheduled on shared production facilities including a complex pipeline network. Capacity constraints, intermediate storage restrictions, due dates, and the dedication of resources to specific product families have to be respected. The primary objective of the heuristic is to minimize the total order tardiness. Secondary objectives include the minimization of pipeline cleaning operations, the minimization of lead times, and the balanced utilization of filling units. The developed algorithm is based on a dynamic prioritization-based greedy search that schedules the orders sequentially. The proposed method can schedule short to mid-term operations and evaluate different plant configurations or production policies on a tactical level. We demonstrate its performance on various real-world inspired scenarios for different scheduling strategies. Our heuristic was used during the construction phase of a new blending plant and was instrumental in the optimal design of the plant. (C) 2015 Elsevier Ltd. All rights reserved.