I have a (classical) scheduling problem using completion date variables, with a constraint like

$$ c_j = s_j + p_j $$

where \(s_j\) and \(c_j\) are variables representing the start date and the completion date of job \(j\), respectively, and \(p_j\) is a parameter representing the duration of job \(j\) (I skip the other constraints).

Although I understand this may not be the ideal formulation, I am trying to understand - for the sake of experimentation - whether it is possible to detect if a job \(j\) is running during a generic period \(t\) where

$$ \min\left(s_j\right) \leq t \leq \max\left(c_j\right). $$

I was thinking (so far with no success) about a binary variable \(u_{jt}\) equal to 1 if job \(j\) is being worked in period \(t\) and 0 otherwise. The rough idea is that I can use the variable \(u\) to represent the status of a resource over time, like a machine or a worker.

Is that possible, keeping the model linear?

asked 03 Mar '15, 12:15

Libra's gravatar image

Libra
2097
accept rate: 0%

edited 03 Mar '15, 12:17

1

you could use many binary "start time" variables t * x_jt to replace s_j

(03 Mar '15, 12:30) Marco Luebbecke ♦

@mluebbecke yes, I can do that, but in this way I can represent when the job starts (I assume the sum_t x_jt = 1 ) and I don't get the connection with the variable u I would like to introduce. u should be equal to 1 in t, t+1,...,t+p_j. Am I missing something from your comment?

(03 Mar '15, 12:53) Libra

@Marco posted in a comment that you could replace \(s_j\) with \(\sum_t t * x_{jt}\) where \(x_{jt}\) is 1 if job \(j\) starts at time \(t\), 0 otherwise. You would also want the constraint \(\sum_t x_{jt}=1 \ \forall j\). Your \(u_{jt}\) variable would then be defined by \(u_{jt}=\sum_{\tau=t-p_j+1}^t x_{j\tau}\).

You could also do this with the original \(s_j\) variables by introducing two binary variables for each job at each time, say \(u_{jt}\) and \(u'_{jt}\), where the former is 1 if job \(j\) completes before time \(t\), the latter is 1 if job \(j\) ends after time \(t\), and both are 0 if job \(j\) is running at time \(t\). Marco's approach has the advantage of using half as many binary variables. (Note that, in Marco's approach, you can declare \(u\) to be continuous; the constraint that defines it will force it to be binary.)

link

answered 03 Mar '15, 15:57

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 03 Mar '15, 15:58

I am too used to twitter these days, forgot that we have 140+ chars here ;-)

(05 Mar '15, 07:58) Marco Luebbecke ♦

@Marco: If you post wisdom in comments, a scavenger like me will swoop in and steal the karma credit for the official answer. :-)

(05 Mar '15, 10:51) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×190
×127
×29

Asked: 03 Mar '15, 12:15

Seen: 608 times

Last updated: 05 Mar '15, 10:51

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