# Index of the first/last positive time-indexed variable

 3 1 I have a problem involving a time-indexed 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 209●8 accept rate: 0%

 3 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: [1]: s/$$A_i$$/$$R$$/g. [2]: s/$$t \cdot y_{it}$$/@Rob Pratt's comment below/g answered 29 Jan '14, 11:44 fbahr ♦ 4.6k●7●16 accept rate: 13% @fbahr: Thank you! suggestions for reformulation are really welcome. (29 Jan '14, 18:28) Libra 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
 5 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 ♦♦ 14.6k●4●12 accept rate: 19%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: