In the oil refinery industry, companies need to have a high utilization of production, storage, and transportation resources to be competitive. This can only be achieved by proper planning The purpose of this thesis is to contribute to the development of optimization models and solution methods that support the scheduling and planning at refinery companies. We identify various decision problems and focus on the scheduling of operation modes at a single refinery and on the shipment planning of products from several refineries to storage depots.

The problem of scheduling operation modes is a type of lot-sizing problem, in which the decisions concern which mode of operation to use in each time period. The objective is to minimize the costs of changing modes, of keeping inventories, and of production, while still satisfying demands for products. We formulate a mixed-integer linear programming model for this problem. Several types of valid inequalities are derived and it is shown how these can be used to improve the performance of a branch-and-bound solution procedure. Further, for the scheduling of operation modes, a tabu search heuristic is developed which uses variable neighborhood, dynamic penalty, and different types of tabu lists.

The shipment planning problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The problem is formulated using an optimization model including an aggregated representation of the scheduling of operation modes at the refineries. Hence, we integrate the shipment planning and the production scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching.

The solution methods are tested on data provided by the Nynas company. Solutions are obtained within reasonable CPU-times and they have shown to be of good quality. We illustrate how the models and their extensions can be used to support both operational and strategic decision making at the company.