Section 5.4.3: Mixed Integer Linear Programming (MILP) Problems

The previous batch equipment assignment problem (section 5.4.2) was treated as an LP, but since the number of batches must be an integer, it should really be an MILP problem with the variables restricted to integer values.

Example 1: Equipment assignment

Reposing the batch equipment assignment problem (section 5.4.2) as an MILP requires only restricting the decision variables to integer values, e.g. the model input becomes, using the same variables:

max: 20 x1 + 6 x2 + 8 x3;
0.8 x1 + 0.2 x2 + 0.3 x3 <=20;
0.4 x1 + 0.3 x2 <= 10 ;
0.2 x1 + 0.1 x3 <= 5 ;
int x1, x2, x3 ;

As noted earlier, this gives an optimum of 524 and 14, 14 and 20 batches of A, B and C respectively.

Suppose however we require to schedule on a daily rather than a weekly basis. The modified problem now has smaller values for the time constraints as shown in the model below. (The constraint of C production has also been removed.)

max: 20 x1 + 6 x2 + 8 x3;
0.8 x1 + 0.2 x2 + 0.3 x3 <=4;
0.4 x1 + 0.3 x2 <= 2 ;
0.2 x1 + 0.1 x3 <= 1 ;

For the MILP formulation the additional line is also required:

int x1, x2, x3 ;

The solution as an LP gives an optimum (for a day's production) of 111.111 with only B (6.667 batches) and C (8.889 batches) being made (i.e no A at all).

However, rounding neither up or down on either of these numbers gives the optimal integer solution which is no A, 5 batches of B and 10 of C, with an of of 110.

Equipment Scheduling

The production schedule corresponding to the assignment of the example above still has to be drawn up. This will involve fitting the utilisation of the the facilities (a) into the actual time periods when the equipment is available, and (b) so that processing steps are carried out in the correct order, i.e. so that reaction precedes either of the product separation operations.

It can be seen that the assignment involves full utilisation of both reactor (total 4 hours) and centrifuge (total 1 hour). Suppose that the period of operation is a 4 hour slot, with the reactor continuously available, and the centrifuge available `on demand' at any time so long as its total utilisation does not exceed 1 hour.

The schedule will then be determined by the availability of the crystalliser. If this is for 4 half hour slots every hour starting after the first half hour, then it is clear that 5 batches of B cannot be produced. Some reactor time may also be lost from the need to synchronise the end of reaction with the start of crystallisation.

Fitting all these constraints together is another MILP problem where the o.f. may be either profit maximisation or maximum equipment utilisation. Setting up such problems is substantially harder than those so far described, and so will be regarded as beyond the scope of this course!

Empirically determined, the following schedule seems to be the only feasible one, even assuming on demand availability of the centrifuge, which greatly simplifies the problem:
C1 B1 C2 C3 C4 B2 C5 C6 C7 B3 C8 C9 B4 C10 (0.2 hours slack on both reactor and crystalliser)

Return to Example Questions
Return to Section 5 Index