6.3 Version 3: with Setup Costs

Of course, several important aspects of a real problem have not been considered. For example, we did not take into account setup costs, that is, the costs (or time) to switch the production from one to another product on a particular machine. Suppose that the setup costs to switch production from one product to another on any machine are constant for all machines and all products: 7 units. What is now the optimal production plan?

To model this question we need to “count” the numbers of setups. In the last production plan, for example, we would have to add 3 times a setup cost of 7 for the first machine M1 in first factory F1, etc. However, the number of setups is itself a variable and we cannot count it “afterwards”. The best way is to introduce a “indicator” variable yf,p,m|qp,m ∈{0, 1} (which is zero or one) for each QQf,p,m|qp,m quantity that can be produced. Whenever QQf,p,m|qp,m is strictly greater than zero then yf,p,m|qp,m must be one. This can be formulated as follows:

QQf,p,m >  0   →    yf,p,m =  1
                                      forall  f ∈ F, p ∈ P,m  ∈ M    with (p,m ) ∈ qp,m

This is not a mathematical linear function and we need to reformulate it as a proper mathematical constraint in order to use standard general solvers. Fortunately, it is easy to translate this constraint into a linear now as follows (where U is a large number):

QQf,p,m ≤  U ⋅ yf,p,m

                                      forall  f ∈ F, p ∈ P,m  ∈ M    with (p,m ) ∈ qp,m

To see that these two constraints express the same condition, we only need to check that y is one if QQ is strictly positive. However, this is always the case, hence the two expressions express the same constraint.

We now have to add all setup costs to the objective function. This function now changed to:

            ∑
min                   (Hp,m ⋅ M cr ⋅ QQf,p,m + Setupp ⋅ yf,p,m)
    f∈F, p∈P, m∈M |q(p,m )

The formulation of this model in LPL is as following (The value of U has been fixed to 400 and the total machine occupation has slightly been increased to 337):

  .... 
  integer variable QQ{f,q}; 
  binary  variable y{f,q}; 
  constraint CA{p}: sum{f,m} QQ = sum{f,m} Q; 
             CB{m,f}: sum{p} H*QQ <= 337; 
             CC{f,q}: QQ <= 400*y; 
  minimize obj1: sum{f,p,m} H*Mc * QQ + Setup*y; 
  ....

The solution can be look up by running the model exercise2c.