Thursday, May 19, 2016

Strange scheduling problem

A somewhat strange scheduling model was presented to me. We operate a machine in one of several operating modes \(i\). We have time periods \(t\) and the operating cost \(c^{op}_{i,t}\) changes over time. Obviously, the best schedule would be to pick in each period \(t\) the cheapest operating mode. Now we add a changeover cost: when we change from mode \(i\) to mode \(j\) we pay some cost \(c^{ch}_{i,j}\). This would require a real optimization model to find the optimal operating sequence.

Here is a simple model to handle this:

image

We have used some random data here, which looks like:

----     12 PARAMETER opcost  operating cost

          period1     period2     period3     period4     period5     period6     period7

mode1       0.172       0.843       0.550       0.301       0.292       0.224       0.350
mode2       0.856       0.067       0.500       0.998       0.579       0.991       0.762
mode3       0.131       0.640       0.160       0.250       0.669       0.435       0.360
mode4       0.351       0.131       0.150       0.589       0.831       0.231       0.666
mode5       0.776       0.304       0.110       0.502       0.160       0.872       0.265


----     12 PARAMETER chcost  changeover cost

            mode1       mode2       mode3       mode4       mode5

mode1                   0.572       1.188       1.445       1.256
mode2       0.928                   0.827       0.235       0.628
mode3       0.093       0.677                   0.364       1.291
mode4       1.121       1.540       0.596                   1.322
mode5       1.512       1.255       0.568       0.173

The solution looks like:

----     34 VARIABLE x.L  operating schedule

          period1     period2     period3     period4     period5     period6     period7

mode1                                                           1           1           1
mode3           1           1           1           1


----     34 VARIABLE y.L  successor

                period4

mode3.mode1           1


----     34 VARIABLE cost.L                =        2.139 

We see one changeover between periods 4 and 5. Notice that \(y\) is defined in the model above as:
\[y_{i,j,t} = \begin{cases} 1 \> \text{if $x_{i,t}=1$ and $x_{i,t+1}=1$} \\
                                      0 \> \text{otherwise}\end{cases}\]

This can also be interpreted as a nonlinear constraint \(y_{i,j,t} = x_{i,t}x_{i,t+1}\). In the model we have linearized this. A refinement of the model would have us look at the operating mode just before we start scheduling (i.e. the operating mode in period 0). To handle that easily it is helpful to change the definition of \(y\) to:
\[y_{i,j,t} = \begin{cases} 1 \> \text{if $x_{i,t-1}=1$ and $x_{i,t}=1$} \\
                                      0 \> \text{otherwise}\end{cases}\]

Only equation order needs to change:

image

Note that \(x0\) is an extremely sparse matrix: it has only one element corresponding to the operating mode for the machine just before period 1. (We used here a GAMS feature: addressing lags outside the domain cause the symbol to be dropped; so \(x_{i,t-1}\) for \(t=period1\) will disappear; in that special case the parameter \(x0\) will kick in). The final results with this initial changeover cost is:

----     37 VARIABLE x.L  operating schedule

          period1     period2     period3     period4     period5     period6     period7

mode1                                                           1           1           1
mode3                                               1
mode4           1           1           1


----     37 VARIABLE y.L  successor

                period4     period5

mode3.mode1                       1
mode4.mode3           1


----     37 VARIABLE cost.L                =        2.438

Note that the initial mode in period 0 was 4, and now we keep operating using that mode for a little while.