Best model for precedence constraints within scheduling problemSymmetry-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?
What's a good pattern to calculate a variable only when it is used the first time?
global variant of csname…endcsname
Trying to understand how Digital Certificates and CA are indeed secure
What does a comma signify in inorganic chemistry?
What happened after the end of the Truman Show?
Combinatorial Argument for Exponential and Logarithmic Function Being Inverse
What's the point of writing that I know will never be used or read?
Meaning and structure of headline "Hair it is: A List of ..."
Unconventional examples of mathematical modelling
Is this bar slide trick shown on Cheers real or a visual effect?
The anatomy of an organic infrared generator
What's the relationship betweeen MS-DOS and XENIX?
How could Tony Stark wield the Infinity Nano Gauntlet - at all?
Eric Andre had a dream
Airline power sockets shut down when I plug my computer in. How can I avoid that?
Why do aircraft leave cruising altitude long before landing just to circle?
Representing an indicator function: binary variables and "indicator constraints"
Do predators tend to have vertical slit pupils versus horizontal for prey animals?
Why is the battery jumpered to a resistor in this schematic?
Build a mob of suspiciously happy lenny faces ( ͡° ͜ʖ ͡°)
Adding things to bunches of things vs multiplication
Will some rockets really collapse under their own weight?
Quick destruction of a helium filled airship?
Why is su world executable?
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?
$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
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 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
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 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
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 bronze badges
$endgroup$
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
mixed-integer-programming modeling scheduling
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 bronze badges
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 bronze badges
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 bronze badges
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 bronze badges
asked 8 hours ago
JakobSJakobS
1,2363 silver badges18 bronze badges
1,2363 silver badges18 bronze badges
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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]).
answered 8 hours ago
BorelianBorelian
1916 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
8 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
8 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
8 hours ago
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.$$
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 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
);
);
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
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
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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]).
answered 8 hours ago
BorelianBorelian
1916 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
8 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
8 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
8 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]).
answered 8 hours ago
BorelianBorelian
1916 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
8 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
8 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
8 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]).
answered 8 hours ago
BorelianBorelian
1916 bronze badges
$endgroup$
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]).
answered 8 hours ago
BorelianBorelian
1916 bronze badges
edited 7 hours ago
answered 8 hours ago
BorelianBorelian
1916 bronze badges
answered 8 hours ago
BorelianBorelian
1916 bronze badges
answered 8 hours ago
BorelianBorelian
1916 bronze badges
1916 bronze badges
$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
8 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
8 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
8 hours ago
add a comment |
$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
8 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
8 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
8 hours ago
$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
8 hours ago
$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
8 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
8 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
8 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
8 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
8 hours ago
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.$$
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 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.$$
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 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.$$
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 bronze badges
$endgroup$
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.$$
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 bronze badges
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 bronze badges
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 bronze badges
answered 8 hours ago
Rob PrattRob Pratt
1,0221 silver badge10 bronze badges
1,0221 silver badge10 bronze badges
add a comment |
add a comment |
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
