Scheduling of crude oil operations is a complex nonlinear problem, especially when tanks hold crude mixes. We present a new mixed-integer nonlinear programming (MINLP) formulation and a novel, mixed-integer linear programming (MILP)-based solution approach for optimizing crude oil unloading, storage, and processing operations in a multi-CDU (crude distillation unit) refinery receiving crude from multiparcel VLCCs (very large crude carriers) through a high-volume, single-buoy mooring (SBM) pipeline and/or single-parcel tankers through multiple jetties. Mimicking a continuous-time formulation, our primarily discrete-time model allows multiple sequential crude transfers to occur within a time slot. It incorporates several real-life operational features including brine settling and tank-to-tank transfers, and is superior to other reported models. Notably our algorithm avoids concentration discrepancy and MINLP solutions by identifying a part of the horizon, for which its linear relaxation is exact, and then solving this MILP repeatedly with progressively shorter horizons. By using 8 h time slots and a hybrid time representation, an attractive approach to this difficult problem is presented. (C) 2004 American Institute of Chemical Engineers.