Wednesday, September 23, 2020

Limiting the number of changes in the operating mode of a machine

Limiting the number of changes in the operating mode of a machine in a scheduling problem can be seen as a direct extension of limiting the number of start-ups.

Limit number of start-ups

Suppose we have a machine scheduling problem, where we use the decision variable $x_t = \begin{cases} 1 & \text{if machine is operating at time slot t}\\ 0 & \text{if machine is idle at time slot t}\end{cases}$ To limit the number number of start-ups we introduce a binary variable $$\mathit{start}_t \in \{0,1\}$$ and write: \begin{align} & \mathit{start}_t \ge x_t - x_{t-1}\\ & \sum_t \mathit{start}_t \le U\end{align} The idea is as follows:

Actually we are only sure that $x_{t-1}=0, x_t = 1 \Rightarrow \mathit{start}_t =1$ so a better picture is:

as the $$\mathit{start}_t$$ is undetermined when we do not switch from 0 to 1.

Notes:
• This formulation works for $$\sum_t \mathit{start}_t \le U$$ or minimize $$\sum_t \mathit{start}_t$$
• It is not suited for  $$\sum_t \mathit{start}_t = U$$, $$\sum_t \mathit{start}_t \ge U$$ or maximize $$\sum_t \mathit{start}_t$$
• We can relax $$\mathit{start}_t$$ to $$\mathit{start}_t \in [0,1]$$, i.e. continuous between 0 and 1

Limit the number of mode changes

Let's now assume that the machine can operate in different modes. One could be inclined to use an integer variable: $$\mathit{mode}_t \in \{0,1,2,\dots,M\}$$. Easier is to use a binary variable $\mathit{mode}_{m,t} = \begin{cases} 1 & \text{if the machine is operating in mode $$m$$ in time slot $$t$$} \\ 0 & \text{otherwise}\end{cases}$ A mode switch from $$m1$$ to $$m2$$ means:

In other words, by just focusing on the mode that is being activated, limiting the number of mode switches can be interpreted as limiting the number start-ups for each mode: \begin{align} & \mathit{switch}_t \ge \mathit{mode}_{m,t} - \mathit{mode}_{m,t-1} && \forall m,t\\ & \sum_t \mathit{switch}_t \le U\end{align} Again, this works whether we have an upper limit on the number of mode changes or just minimize this number.

References

1. Maximizing number of consecutive days with the same operation mode for a scheduling problem,  https://stackoverflow.com/questions/64012796/maximizing-number-of-consecutive-days-with-the-same-operation-mode-for-a-schedul