I have a problem involving a timeindexed variable \(x_{it}\) representing the amount of a resource allotted to a task \(i\) in time \(t\). The quantity of the (renewable) resource is constrained at a value \(R\) per period: $$ \sum_{i=1}^{I} x_{it}\leq R\,\,\,\forall t \in T $$ and I have to allott a given quantity \(A_i\) of \(R\) to each task over the time horizon \(1...T\): $$ \sum_{t=1}^{T} x_{it}\geq A_{i}\,\,\,\forall i \in I $$ My question is: is it possible with this formulation to get the highest and lowest \(t\)s such as \(x_{it}\) is not zero, keeping the problem linear? $$ t_{i}^{MIN}=\{ \tau \;\; x_{i\tau}>0 \wedge x_{it}=0\;\forall t<\tau\} $$ $$ t_{i}^{MAX}=\{ \tau \;\; x_{i\tau}>0 \wedge x_{it}=0\;\forall t>\tau\} $$ What I am trying to get is the starting time (\(t_{i}^{MIN}\)) and the completion time (\(t_{i}^{MAX}\)) of each task. The objective function could be to minimize the maximum of the \(t_{i}^{MAX}\), or to minimize the difference between the maximum \(t_{i}^{MAX}\) and the minimum \(t_{i}^{MIN}\) (that is the makespan). I think this formulation is not the ideal one, but I can't figure out a suitable, simple alternative. The fact is that the duration of the task is dependent upon the amount of resources allotted in each period, so a formulation using variables representing the starting time and the completion time seems not ok either. asked 29 Jan '14, 06:12 Libra 
Technically, \[ \left. \begin{align} x_{it} & \leq R \cdot y_{it} & \scriptstyle{// ~[1]}\\ t \cdot y_{it} & \leq t_i^{MAX} & \\ T + ( T + t ) \cdot y_{it} & \geq t_i^{MIN} & \scriptstyle{// ~[2]}\\ y_{it} & \in \{0,1\} & \\ t_{i}^{\{MIN, MAX\}} & \in \mathrm{Z} & \\ \end{align} \quad \right\} \quad \forall ~i = 1 \ldots I, ~t = 1 \ldots T \] should suffice your needs ...but, of course, at the cost of introducing \(I \times (T + 2)\) integer/binary variables and even \(3 \times I \times T\) additional constraints. While I'm not sure whether integer variables can be completely avoided, I'm almost certain that "we" have a more compact [re]formulation for this. I. e.: come forward, schedulers! Corrections: answered 29 Jan '14, 11:44 fbahr ♦ 2
It seems to me that the third constraint does not behave properly (is not redundant) when \(y_{it} = 0\). I think the following does the job: \[t \cdot y_{it} + T (1  y_{it}) \ge t_i^\text{MIN},\] where \(T\) is the latest time period. Similarly, the second constraint can be tightened as: \[t \cdot y_{it} + 1 (1  y_{it}) \le t_i^\text{MAX},\] since 1 is the earliest time period.
(01 Feb '14, 21:55)
Rob Pratt

I think I can reduce the number of binaries in @Florian's approach by noting that you don't really care about individual end times, just the cumulative end time (which equals makespan if you assume that operations start at time 0  nothing in what you described indicates any reason for a "dead time" at the outset). Let \(Z_t\in\{0,1\}\) be 1 if production terminates at the end of time epoch \(t\in T\) (making \(t\) the makespan), 0 otherwise. That introduces just \(T\) new binary variables. The additional constraints are that \(x_{it} \le \min(A_i,R)(1  \sum_{\tau \lt t}Z_\tau)\) for all \(i\in I,t \in T\), along with an SOS1 constraint \(\sum_{t\in T}Z_t = 1\). To minimize end time, the objective is \(\min \sum_{t \in T}t Z_t\). answered 29 Jan '14, 19:15 Paul Rubin ♦♦ 