Mfcttrf

Photoshop older default brushes

A reccomended structured approach to self studying music theory for songwriting

Does the Temple of the Gods spell nullify critical hits?

What's the relationship betweeen MS-DOS and XENIX?

Which basis does the wavefunction collapse to?

Why don't modern jet engines use forced exhaust mixing?

Compute the square root of a positive integer using binary search

Subgroup generated by a subgroup and a conjugate of it

Quick destruction of a helium filled airship?

Why do so many people play out of turn on the last lead?

May the tower use the runway while an emergency aircraft is inbound?

How do I answer an interview question about how to handle a hard deadline I won't be able to meet?

My new Acer Aspire 7 doesn't have a Legacy Boot option, what can I do to get it?

How to train a replacement without them knowing?

Heyawacky: Ace of Cups

How to change minor radius of a torus in blender 2.8

Why is the battery jumpered to a resistor in this schematic?

Why was ramjet fuel used as hydraulic fluid during Saturn V checkout?

Unconventional examples of mathematical modelling

Are unaudited server logs admissible in a court of law?

Do I need to start off my book by describing the character's "normal world"?

Would getting a natural 20 with a penalty still count as a critical hit?

How do the Durable and Dwarven Fortitude feats interact?

Earliest evidence of objects intended for future archaeologists?

Best model for precedence constraints within scheduling problem

Symmetry-breaking ILP constraints for square binary matrixDealing with non-overlapping constraintsConditional Controls in MIP ModelsAssignment Problem with Decreasing CostsHow to formulate this scheduling problem efficiently?How to reformulate (linearize/convexify) a budgeted assignment problem?What is this type of scheduling problem called?The rationale to improve MTZ?

8

$begingroup$

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to model some precedence constraints for certain jobs.

Due to the rest of the model I have to use binary variables $s_jt$ that are 1 if job $jin J$ starts in time bucket $tin T$. Suppose I furthermore have a set $P$ of tuples of jobs $(j_1, j_2)in Psubset Jtimes J$ for which the second has to start after the first is finished. Each job $j$ has duration $d_j$, i.e the number of time buckets that are needed to finish the job.

My question is how to model the precedence constraint using the above variables (plus maybe some additional ones) in the most efficient and/or effective way. Meaning I'm interested in the smallest formulation but also in the formulation that gives the tightest bound, respectively the fastest solving times when solved with a MIP solver.

mixed-integer-programming modeling scheduling

share|improve this question

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

$endgroup$

add a comment | 

8

$begingroup$

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to model some precedence constraints for certain jobs.

Due to the rest of the model I have to use binary variables $s_jt$ that are 1 if job $jin J$ starts in time bucket $tin T$. Suppose I furthermore have a set $P$ of tuples of jobs $(j_1, j_2)in Psubset Jtimes J$ for which the second has to start after the first is finished. Each job $j$ has duration $d_j$, i.e the number of time buckets that are needed to finish the job.

My question is how to model the precedence constraint using the above variables (plus maybe some additional ones) in the most efficient and/or effective way. Meaning I'm interested in the smallest formulation but also in the formulation that gives the tightest bound, respectively the fastest solving times when solved with a MIP solver.

mixed-integer-programming modeling scheduling

share|improve this question

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

$endgroup$

add a comment | 

$begingroup$

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to model some precedence constraints for certain jobs.

Due to the rest of the model I have to use binary variables $s_jt$ that are 1 if job $jin J$ starts in time bucket $tin T$. Suppose I furthermore have a set $P$ of tuples of jobs $(j_1, j_2)in Psubset Jtimes J$ for which the second has to start after the first is finished. Each job $j$ has duration $d_j$, i.e the number of time buckets that are needed to finish the job.

My question is how to model the precedence constraint using the above variables (plus maybe some additional ones) in the most efficient and/or effective way. Meaning I'm interested in the smallest formulation but also in the formulation that gives the tightest bound, respectively the fastest solving times when solved with a MIP solver.

mixed-integer-programming modeling scheduling

share|improve this question

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

$endgroup$

share|improve this question

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

share|improve this question

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

asked 8 hours ago

JakobSJakobS

1,23633 silver badges1818 bronze badges

2 Answers
2

active

oldest

votes

7

$begingroup$

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation.

Let $s'_jt$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or before). In that case, your precedence constraint can be formulated as
$$s'_j_2,t leq s'_j_1,t-d_1$$

Notice that you can do a change of variables ($s_j,1=s'_j,1$ and $s_j,t =s'_j,t-s'_j,t-1$) to write the remaining constraints with these new variables. You also need to add constraints $s'_j,tleq s'_j,t+1$.

This usually provide a very tight bound, specially if the number of precedence constraints is very large and the additional constraints are just a few (see [1]).

share|improve this answer

edited 7 hours ago

answered 7 hours ago

BorelianBorelian

19166 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hi @Borelian, unfortunately this will not work due to the other constraints that I have. But nice to know nonetheless... Might be helpful for other similar problems.
  $endgroup$
  – JakobS
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes @jakobs, but note that you can do a change of variables $s_j,t =s'_j,t-s'_j,t-1$ and use the same original constraints but with more terms..
  $endgroup$
  – Borelian
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ah nice! Did not see that. Can you add this to your answer? It would make it more self-contained...
  $endgroup$
  – JakobS
  7 hours ago
  

  
  
  
  

add a comment | 

5

$begingroup$

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_j_1,t_1+s_j_2,t_2le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$sum_tge t_1s_j_1,t+sum_tle t_2s_j_2,tle 1.$$

share|improve this answer

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f1319%2fbest-model-for-precedence-constraints-within-scheduling-problem%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

7

$begingroup$

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation.

Let $s'_jt$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or before). In that case, your precedence constraint can be formulated as
$$s'_j_2,t leq s'_j_1,t-d_1$$

Notice that you can do a change of variables ($s_j,1=s'_j,1$ and $s_j,t =s'_j,t-s'_j,t-1$) to write the remaining constraints with these new variables. You also need to add constraints $s'_j,tleq s'_j,t+1$.

This usually provide a very tight bound, specially if the number of precedence constraints is very large and the additional constraints are just a few (see [1]).

share|improve this answer

edited 7 hours ago

answered 7 hours ago

BorelianBorelian

19166 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hi @Borelian, unfortunately this will not work due to the other constraints that I have. But nice to know nonetheless... Might be helpful for other similar problems.
  $endgroup$
  – JakobS
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes @jakobs, but note that you can do a change of variables $s_j,t =s'_j,t-s'_j,t-1$ and use the same original constraints but with more terms..
  $endgroup$
  – Borelian
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ah nice! Did not see that. Can you add this to your answer? It would make it more self-contained...
  $endgroup$
  – JakobS
  7 hours ago
  

  
  
  
  

add a comment | 

7

$begingroup$

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation.

Let $s'_jt$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or before). In that case, your precedence constraint can be formulated as
$$s'_j_2,t leq s'_j_1,t-d_1$$

Notice that you can do a change of variables ($s_j,1=s'_j,1$ and $s_j,t =s'_j,t-s'_j,t-1$) to write the remaining constraints with these new variables. You also need to add constraints $s'_j,tleq s'_j,t+1$.

This usually provide a very tight bound, specially if the number of precedence constraints is very large and the additional constraints are just a few (see [1]).

share|improve this answer

edited 7 hours ago

answered 7 hours ago

BorelianBorelian

19166 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hi @Borelian, unfortunately this will not work due to the other constraints that I have. But nice to know nonetheless... Might be helpful for other similar problems.
  $endgroup$
  – JakobS
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes @jakobs, but note that you can do a change of variables $s_j,t =s'_j,t-s'_j,t-1$ and use the same original constraints but with more terms..
  $endgroup$
  – Borelian
  7 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ah nice! Did not see that. Can you add this to your answer? It would make it more self-contained...
  $endgroup$
  – JakobS
  7 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation.

Let $s'_jt$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or before). In that case, your precedence constraint can be formulated as
$$s'_j_2,t leq s'_j_1,t-d_1$$

Notice that you can do a change of variables ($s_j,1=s'_j,1$ and $s_j,t =s'_j,t-s'_j,t-1$) to write the remaining constraints with these new variables. You also need to add constraints $s'_j,tleq s'_j,t+1$.

This usually provide a very tight bound, specially if the number of precedence constraints is very large and the additional constraints are just a few (see [1]).

share|improve this answer

edited 7 hours ago

answered 7 hours ago

BorelianBorelian

19166 bronze badges

$endgroup$

share|improve this answer

edited 7 hours ago

answered 7 hours ago

BorelianBorelian

19166 bronze badges

answered 7 hours ago

BorelianBorelian

19166 bronze badges

answered 7 hours ago

BorelianBorelian

19166 bronze badges

5

$begingroup$

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_j_1,t_1+s_j_2,t_2le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$sum_tge t_1s_j_1,t+sum_tle t_2s_j_2,tle 1.$$

share|improve this answer

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges

$endgroup$

add a comment | 

5

$begingroup$

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_j_1,t_1+s_j_2,t_2le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$sum_tge t_1s_j_1,t+sum_tle t_2s_j_2,tle 1.$$

share|improve this answer

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges

$endgroup$

add a comment | 

$begingroup$

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_j_1,t_1+s_j_2,t_2le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$sum_tge t_1s_j_1,t+sum_tle t_2s_j_2,tle 1.$$

share|improve this answer

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges

$endgroup$

share|improve this answer

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges

answered 8 hours ago

Rob PrattRob Pratt

1,02211 silver badge1010 bronze badges