Petroleum refinery production planning

Boddy and Johnson boddy describe a planning and scheduling problem arising in the management of petroleum refinement operations. The objects of this problem include materials, in the form of hydrocarbon mixtures and fractions, tanks and processing units. During the operation of the refinery the mixtures and fractions pass through a series of processing units including distillation units, desulphurisation units and cracking units. Inside these units they are converted and combined to produce desired materials and to remove waste products. Processes include the filling and emptying of tanks, which in some cases can happen simultaneously on the same tank, treatment of materials and their transfer between tanks. The continuous components of the problem include process unit control settings, flow volumes and rates, material properties and volumes and the time-dependent properties of materials being combined in tanks as a consequence of refinement operations.

An example demonstrating the utility of a continuous model arises in the construction of a gasoline blend. The success of a gasoline blend depends on the chemical balance of its constituents. Blending results from materials being pumped into and out of tanks and pipelines at rates which enable the exact quantities of the required chemical constituents to be controlled. For example, when diluting crude oil with a less sulphrous material the rate of in-flow of the diluting material, and its volume in the tank, have to be balanced by out-flow of the diluted crude oil and perhaps by other refinement operations.

Boddy and Johnson treat the problem of planning and scheduling refinery operations as an optimisation problem. Approximations based on discretisation lead to poor solutions, leading to a financial motivation for Boddy and Johnson's application. As they observe, a moderately large refinery can produce in the order of half a million barrels per day. They calculate that a $1\%$ decrease in efficiency, resulting from approximation, could result in the loss of a quarter of a million dollars per day. The more accurate the model of the continuous dynamics the more efficient and cost-effective the refinery.

Boddy and Johnson's planning and scheduling approach is based on dynamic constraint satisfaction involving continuous, and non-linear, constraints. A domain-specific solver was constructed, demonstrating that direct handling of continuous problem components can be realistic. Boddy and Johnson describe applying their solver to a real problem involving 18,000 continuous constraints including 2,700 quadratic constraints, 14,000 continuous variables and around 40 discrete decisions [Lamba, Dietz, Johnson, BoddyLamba et al.2003,Boddy JohnsonBoddy Johnson2002]. It is interesting to observe that this scale of problem is solvable, to optimality, with reasonable computational effort.