Ocean transportation is the workhorse for logistics in global chemical supply chains. Often, logistics cost can be as high as 20% of the purchasing cost. Efficient routing and scheduling of multi-parcel chemical tankers to reduce logistics expenditure is important for both chemical and shipping industry. We consider the maximum-profit scheduling of a fleet of multi-parcel tankers engaged in shipping bulk liquid chemicals. For this, we present a mixed-integer linear programming (MILP) formulation using variable-length slots and propose a heuristic decomposition algorithm that obtains the fleet schedule by repeatedly solving the base formulation for a single ship. The formulation is generally applicable to all kinds of carriers engaged in the transportation of multiple commodities, and to transportation systems where frequent schedule updates or a short-term planning horizon is required. We illustrate our approach on a real industrial case study involving 10 tankers, 36 ports and 79 cargos. Our approach showed an increase of 32.7% in profit as compared to the plan actually used by a major chemical shipping company. (C) 2003 Elsevier Ltd. All rights reserved.