Scheduling: extend a model with completion date variables

 1 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 209●8 accept rate: 0% 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

 2 @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.) answered 03 Mar '15, 15:57 Paul Rubin ♦♦ 14.6k●4●12 accept rate: 19% 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 ♦♦
 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:

×190
×127
×29