Loading [MathJax]/jax/output/CommonHTML/jax.js

Monday, November 23, 2020

Machine scheduling: Maintenance and maximum runlength

In [1] a problem is posed that deals with a maximum run-length (6 days) before the machine needs to be taken off-line for maintenance (1 day).  Consider the binary decision variable:

yt={1if machine is online at period t0otherwise


In [1] a scheme is proposed as follows. Introduce an integer variable zt that has the cumulative days the machine is running. Then apply the rule: 

if z>6 then y:=0,z:=0




This approach needs a bit of repair to make it work for a MIP model. A MIP model can not contain assignments, and decision variables are part of a system of linear equations. I.e., all decision variables are essentially calculated at the same time (a notion which can be foreign for computer programmers who think in sequential assignment statements). We can write:yt=1zt=zt1+1yt=0zt=0zt{0,,6} This is in the form of implications that can be used directly with (advanced) solvers that support indicator constraints (i.e., a binary variable on the left and a linear constraint on the right). Note that we don't do anything special when zt becomes 7. We just forbid that from happening by setting an upper bound of 6. The initial value z0 is the number of periods the machine is already online at the beginning of the planning period. 


If your solver or modeling tool does not have support for indicator constraints, we can rewrite things as: zupt:=6ztytzuptztzt1+1ztzt1+1(1yt)(zupt+1)zt{0,,zupt} Here zupt=6 is the upper bound on zt. This formulation requires a little bit of thinking. Finally, I want to mention that zt can be declared as a continuous variable: it will be integer automatically. 


A simpler alternative formulation is to just forbid any sequence of 7 consecutive 1's for y. I.e. yt+yt+1+yt+2+yt+3+yt+4+yt+5+yt+66 It may be easier to look backward: yt+yt1+yt2+yt3+yt4+yt5+yt66 The terms ytk can have a non-positive index tk which means this is historic data, from before our planning period. In other words y0,y1,y2, is data.


Conclusion


This is a good example where we can achieve the same result using two very different approaches. It may make sense to choose the simplest formulation.

References


  1. Linear Programming - Re-setting a variable based on it's cumulative count, https://stackoverflow.com/questions/64930027/linear-programming-re-setting-a-variable-based-on-its-cumulative-count


No comments:

Post a Comment