Daily scheduling for a brewery.  The brewing process begins with malting of barley, milling into "grist" and mashing in the brewhouse to create the sweet liquor "wort".  (The process has many steps but for planning purposes they can be treated as one.)  The wort is transferred into fermentation tanks, and brewing yeast is tipped in.  During fermentation, carbon dioxide is harvested for reinjection during bottling.  After a period of one to two weeks, yeast is cropped for re-tipping, and the "green" beer is racked into storage tanks.  After two to three weeks of conditioning, the mature beer is ready for filtering and dilution into bright beer tanks, then pasteurisation, bottling and packing.  Beer can remain in its storage tank almost indefinitely once it is mature.

There are several different brands of beer, each of which take different amounts of time in fermentation and storage, and which use specific yeast strains.  There are over 100 fermentation and storage vessels (some of which can do both jobs) divided into multiple groups of equally-sized vessels.

In most manufacturing scheduling problems, storage acts as a buffer between processing steps.  Time spent in storage is often unlimited either above or below (or there is an upper limit which can be disregarded because throughput is sufficiently high).  Storage is often not even a limiting factor.  In this situation, most of the processing is storage, and it is the availability of the tanks that constrains production.  The time spent in these processing stages is long compared to the granularity required for scheduling, which is at least daily.

The recycling of yeast provides another complexity.  Unlike most industrial catalysts, the amount cropped is larger (by a factor of two or three) than the amount tipped in, and can be used to start multiple later batches, so long as there is a minimal delay in re-tipping.  But yeast can only be recycled through a certain number of generations, after which it must be sold for food manufacture.

Fresh cultures of yeast are initially prepared in independent propagation tanks, but the final stage of preparation is a small but otherwise standard beer batch run through the main tankage, called a "prop" batch.  Capacity to prepare fresh cultures is constrained with a minimum time between prop batches.

Standard scheduling algorithms do not handle tankage well even in much simpler situations.  In order to generate a schedule which closely meets demand for beer brands while synchronising tank usage and yeast re-use, we must use mixed integer programming.

We cannot handle individual tanks over the two-month timespan required, so we work at the level of tank groups and their total capacity.

Batches of beer cannot be mixed, so we cannot treat the primary stages (brewhouse, fermentation, storage) as independent processes linked only by material balances.  Instead we recognise the concept of "batch" in the model.  In each day a finite (predetermined) number of batches of each beer brand may or may not start.  For each batch of a given brand on a given day we must decide:

The original model used these decisions to determine a collection of "route" variables, representing a complete path through the primary stages.  There are many restrictions on the physical links between the stages – for example, which brewhouses can feed which fermentation tank groups.  Even so, the number of route variables was very large and the problem became impractical.

Further analysis showed that three subsets of the four decisions above were sufficient to determine all interactions with the rest of the model:

The quantities of fermenting and maturing beer are not represented in the model – all we are concerned with is tank usage.  Even if a tank is not full, its capacity is fully used by one batch, and we can accurately represent that situation by consuming a whole tank-worth of capacity out of the tank group's total over the appropriate time span.

However, once the beer is mature, it may be removed from the storage tank at any time, possibly in a series of separate filtering operations as required to meet demand.  So we must treat it in the conventional manner as a material in inventory, which consumes storage capacity.  We can make the capacity used a multiple (for example 1.1) of the quantity held to recognise the average fill percentage (for example 91%).

The model solves in a few minutes.  The results are passed to the scheduling module, where specific fermentation and storage tanks are allocated on a first-come first-served basis.  The complete schedule is displayed in the planning board as activities on tank facilities (and packaging lines), with material flow links connecting the stages of each batch.