MP in Action‎ > ‎Software‎ > ‎

MIMI Brings OR Tools Together

This article is based on a talk given by Kirk Williams, Managing Director of Chesapeake Decision Sciences Europe Ltd to the Mathematical Programming Study Group.

Requirement for an OR Toolkit

Chesapeake Decision Sciences was founded in 1982 by Tom Baker, who had been OR Coordinator in Exxon International for many years. Its first focus was on the oil industry, and in particular on the problems of planning and scheduling oil refineries. This remains one of the company's main business areas, but it has also expanded into other continuous process industries and into discrete manufacturing.

Throughout this time it has been extending the capabilities of its product MIMI, an industrial-strength OR toolkit. This integrates technologies such as an LP optimiser (CPLEX), an expert system engine and scheduling algorithms as well as tools for building graphical user interfaces.

The toolkit approach has been driven by the requirement to solve clients' problems in general and those of planning and scheduling oil refineries in particular. This is a problem of enormous complexity where individual facets can be tackled using a single OR technology but the entire problem requires a multitude of technologies in combination.

The Refinery Business

Oil refining has become a commodity business: the products are the same from everyone. This is literally true: petrol stations are supplied from their local refinery irrespective of the label on the pump. In western Europe the market for oil products is saturated and margins are low. A cargo of crude costs perhaps $20 million and, after refining, the products will sell for $21 million. Out of the gross margin of $1 million, processing costs will be $200,000 and transport costs $100,000. The balance has to cover everything from marketing through to the capital costs of upgrading the plant so that products comply with new vehicle emission regulations.

Oil refining is dominated by large companies with vast reservoirs of accepted wisdom etched in the corporate psyche. This wisdom is almost always wrong. For instance, an oil company built a retail price management system which enabled it to increase its market share by 5%. But did it increase the company's profit? It couldn't tell. It was pursuing the accepted wisdom that it was good to sell more.

When Chesapeake builds applications its aim is to help the client change the way it approaches its business. In refining this means moving away from managing stocks to "added value management". Systems are designed to help people make decisions in terms of their economic consequences. Models exist within a framework of setting targets, taking actions, monitoring results and using those to reassess targets.

Planning and Scheduling

Planning and scheduling in refineries takes place over a hierarchy of time horizons. At the top level there is enterprise planning: this is concerned with a company's market position worldwide and allocating capital investment over a period of 5 years or more. Below this is operational planning over time horizons between 1 week and 6 months; this is concerned with deciding which crudes to buy, how to process them and which products to sell. At the bottom there is detailed scheduling within the refinery, which answers the question "What am I going to do next?". The cascade of models used in operational planning and scheduling is shown in Figure 1.

Figure 1: Planning and Scheduling Cascade in a Refinery

Linear and Integer Programming are heavily used in the longer-term planning models. With shorter time horizons the models have to be more detailed and accurate and this leads to the use of Successive Linear Programming. The greatest challenges lie with the transition from operational planning to detailed scheduling, where the assumptions implicit in LP-based models break down. These are that operations can be broken down into a series of time periods, during each of which it suffices to model activities as continuous (or average) flows.

Disaggregating an LP Plan

The shortest time horizon over which LP-based models are normally used is 1 - 2 weeks. Such a model might have 3 - 5 time periods with the first time period typically 1 - 2 days. The model will be "rolled forward" every 1 - 2 days, i.e. rerun with updated data to describe the problem which the refinery now faces.

Such a model provides useful guidance to how to run the main process units, but it does not address the logistical issues of what is happening on the tanks and how to sequence batch activities. Chesapeake has been tackling this problem with a combination of Mixed Integer Programming, expert system rules and a planning board. Mixed Integer Programming is used first to do some disaggregation; then expert system rules are used to extract a first-cut schedule. This is displayed on a graphical planning board (Figure 2) which highlights problems, e.g. stock over- or underflows.

Figure 2: MIMI Planning Board for Refinery Scheduling

Using his knowledge of the refinery, the operator then seeks to overcome the problems by manipulating the schedule on the planning board. As he does so, the planning board assists him by tracking the consequences of changes and displaying them in real time.

Man and Machine

Refinery scheduling staff sometimes say that they would like a completely automatic scheduling package which generated the best schedule. This is not a realistic goal with current technology, nor is it a good idea. What is needed is synergy between man and machine.

The machine should filter the enormous number of possible solutions and present a small number of good ones to the man. The man should then select the best given his understanding of what is really happening on the plant. For instance, at one refinery the loading bay tended to flood to a depth of a couple of inches after heavy rain. This wouldn't have been a problem if it hadn't been for the dog which lived there. The dog became grumpy and loading had to be suspended until the dog had been pacified.


Hard scheduling problems are never going to be solved completely. The aim should be to achieve 80-20 solutions, in which the machine does 80% of the work (and the donkey work at that) and the man 20%. In doing this it will always be necessary to mix and match solution techniques such as LP, scheduling algorithms and expert system rules. MIMI is an integrated set of tools which has been proved over the years in tackling some of the most demanding such applications.

Related articles include A Comparative Survey of Mathematical Programming Software and Planning and Scheduling in Oil Refineries. To find other articles, refer to the MP in Action page.