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's gravatar image

accept rate: 0%

edited 29 Jan '14, 06:16


\[ \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!

[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's gravatar image

fbahr ♦
accept rate: 13%

edited 02 Feb '14, 04:16

@fbahr: Thank you! suggestions for reformulation are really welcome.

(29 Jan '14, 18:28) Libra

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 29 Jan '14, 19:16

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 29 Jan '14, 06:12

Seen: 1,000 times

Last updated: 02 Feb '14, 04:16

OR-Exchange! Your site for questions, answers, and announcements about operations research.