Linear Programming - Preventing Staff Scheduling Shift Overlap?
$begingroup$
I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc).
I've Googled for several hours looking at articles on this category of problem, but the documented problems are much more complicated than the one I am currently pondering, which I've contrived on my own as an exercise.
Here is the problem:
=======================
SCENARIO:
You have three drivers to make deliveries.
Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr
Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Only one worker can be working at a given time.
Operating day is 6:00 to 22:00, which must be fully covered.
Driver 2 cannot work after 11:00.
Create a schedule that minimizes the cost.
========================
Here is the work I have written out so far.
Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X
Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11
When I express these equations in my Kotlin code (which I can share if desired), I am getting shift overlaps. Here is the output:
OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]
It minimized the cost to $624, and it did correctly constrain to 16 hours worth of shifts. It also respected the max shift time allowed for each driver, and prevented Driver 2 from being scheduled beyond 11:00.
However, it scheduled the shifts to Driver 1 6:00-11:00, Driver 2 6:00-12:00, and Driver 3 6:00-11:00.
I've tried to research the solution to this problem, but I really cannot find a simple answer to my question. Can someone please share what mysterious linear functions I need to constrain to in order for my shifts to not overlap? I keep reading about binary constraints and I'm not sure how to use those to show a shift being "occupied".
linear-algebra linear-programming
asked Oct 19 '17 at 23:58
tmntmn
1396
$endgroup$
|
show 2 more comments
$begingroup$
I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc).
I've Googled for several hours looking at articles on this category of problem, but the documented problems are much more complicated than the one I am currently pondering, which I've contrived on my own as an exercise.
Here is the problem:
=======================
SCENARIO:
You have three drivers to make deliveries.
Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr
Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Only one worker can be working at a given time.
Operating day is 6:00 to 22:00, which must be fully covered.
Driver 2 cannot work after 11:00.
Create a schedule that minimizes the cost.
========================
Here is the work I have written out so far.
Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X
Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11
When I express these equations in my Kotlin code (which I can share if desired), I am getting shift overlaps. Here is the output:
OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]
It minimized the cost to $624, and it did correctly constrain to 16 hours worth of shifts. It also respected the max shift time allowed for each driver, and prevented Driver 2 from being scheduled beyond 11:00.
However, it scheduled the shifts to Driver 1 6:00-11:00, Driver 2 6:00-12:00, and Driver 3 6:00-11:00.
I've tried to research the solution to this problem, but I really cannot find a simple answer to my question. Can someone please share what mysterious linear functions I need to constrain to in order for my shifts to not overlap? I keep reading about binary constraints and I'm not sure how to use those to show a shift being "occupied".
linear-algebra linear-programming
asked Oct 19 '17 at 23:58
tmntmn
1396
$endgroup$
$begingroup$
You can add $infty(Te1-Ts2) + infty(Te2-Ts1) + infty(Te1-Ts3) + infty(Te3-Ts1) + infty(Te2-Ts3) + infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 0:17
$begingroup$
How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try usingInteger.MAX_VALUEalthough I'm not sure that would have the same effect.
$endgroup$
– tmn
Oct 20 '17 at 0:29
$begingroup$
Here is what I originally posted on SO. stackoverflow.com/questions/46823121/…
$endgroup$
– tmn
Oct 20 '17 at 0:30
$begingroup$
It doesn't have to be infinity! It can just be a ridiculously large number like 99999999.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 1:00
$begingroup$
That would be a numerical disaster.
$endgroup$
– copper.hat
Oct 20 '17 at 1:37
|
show 2 more comments
$begingroup$
I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc).
I've Googled for several hours looking at articles on this category of problem, but the documented problems are much more complicated than the one I am currently pondering, which I've contrived on my own as an exercise.
Here is the problem:
=======================
SCENARIO:
You have three drivers to make deliveries.
Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr
Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Only one worker can be working at a given time.
Operating day is 6:00 to 22:00, which must be fully covered.
Driver 2 cannot work after 11:00.
Create a schedule that minimizes the cost.
========================
Here is the work I have written out so far.
Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X
Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11
When I express these equations in my Kotlin code (which I can share if desired), I am getting shift overlaps. Here is the output:
OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]
It minimized the cost to $624, and it did correctly constrain to 16 hours worth of shifts. It also respected the max shift time allowed for each driver, and prevented Driver 2 from being scheduled beyond 11:00.
However, it scheduled the shifts to Driver 1 6:00-11:00, Driver 2 6:00-12:00, and Driver 3 6:00-11:00.
I've tried to research the solution to this problem, but I really cannot find a simple answer to my question. Can someone please share what mysterious linear functions I need to constrain to in order for my shifts to not overlap? I keep reading about binary constraints and I'm not sure how to use those to show a shift being "occupied".
linear-algebra linear-programming
asked Oct 19 '17 at 23:58
tmntmn
1396
$endgroup$
I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc).
I've Googled for several hours looking at articles on this category of problem, but the documented problems are much more complicated than the one I am currently pondering, which I've contrived on my own as an exercise.
Here is the problem:
=======================
SCENARIO:
You have three drivers to make deliveries.
Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr
Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Only one worker can be working at a given time.
Operating day is 6:00 to 22:00, which must be fully covered.
Driver 2 cannot work after 11:00.
Create a schedule that minimizes the cost.
========================
Here is the work I have written out so far.
Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X
Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11
When I express these equations in my Kotlin code (which I can share if desired), I am getting shift overlaps. Here is the output:
OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]
It minimized the cost to $624, and it did correctly constrain to 16 hours worth of shifts. It also respected the max shift time allowed for each driver, and prevented Driver 2 from being scheduled beyond 11:00.
However, it scheduled the shifts to Driver 1 6:00-11:00, Driver 2 6:00-12:00, and Driver 3 6:00-11:00.
I've tried to research the solution to this problem, but I really cannot find a simple answer to my question. Can someone please share what mysterious linear functions I need to constrain to in order for my shifts to not overlap? I keep reading about binary constraints and I'm not sure how to use those to show a shift being "occupied".
linear-algebra linear-programming
linear-algebra linear-programming
asked Oct 19 '17 at 23:58
tmntmn
1396
asked Oct 19 '17 at 23:58
tmntmn
1396
edited Oct 20 '17 at 13:19
tmn
asked Oct 19 '17 at 23:58
tmntmn
1396
asked Oct 19 '17 at 23:58
tmntmn
1396
asked Oct 19 '17 at 23:58
tmntmn
1396
1396
$begingroup$
You can add $infty(Te1-Ts2) + infty(Te2-Ts1) + infty(Te1-Ts3) + infty(Te3-Ts1) + infty(Te2-Ts3) + infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 0:17
$begingroup$
How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try usingInteger.MAX_VALUEalthough I'm not sure that would have the same effect.
$endgroup$
– tmn
Oct 20 '17 at 0:29
$begingroup$
Here is what I originally posted on SO. stackoverflow.com/questions/46823121/…
$endgroup$
– tmn
Oct 20 '17 at 0:30
$begingroup$
It doesn't have to be infinity! It can just be a ridiculously large number like 99999999.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 1:00
$begingroup$
That would be a numerical disaster.
$endgroup$
– copper.hat
Oct 20 '17 at 1:37
|
show 2 more comments
$begingroup$
You can add $infty(Te1-Ts2) + infty(Te2-Ts1) + infty(Te1-Ts3) + infty(Te3-Ts1) + infty(Te2-Ts3) + infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 0:17
$begingroup$
How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try usingInteger.MAX_VALUEalthough I'm not sure that would have the same effect.
$endgroup$
– tmn
Oct 20 '17 at 0:29
$begingroup$
Here is what I originally posted on SO. stackoverflow.com/questions/46823121/…
$endgroup$
– tmn
Oct 20 '17 at 0:30
$begingroup$
It doesn't have to be infinity! It can just be a ridiculously large number like 99999999.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 1:00
$begingroup$
That would be a numerical disaster.
$endgroup$
– copper.hat
Oct 20 '17 at 1:37
$begingroup$
You can add $infty(Te1-Ts2) + infty(Te2-Ts1) + infty(Te1-Ts3) + infty(Te3-Ts1) + infty(Te2-Ts3) + infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 0:17
$begingroup$
You can add $infty(Te1-Ts2) + infty(Te2-Ts1) + infty(Te1-Ts3) + infty(Te3-Ts1) + infty(Te2-Ts3) + infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 0:17
$begingroup$
How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try using
Integer.MAX_VALUE although I'm not sure that would have the same effect.$endgroup$
– tmn
Oct 20 '17 at 0:29
$begingroup$
How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try using
Integer.MAX_VALUE although I'm not sure that would have the same effect.$endgroup$
– tmn
Oct 20 '17 at 0:29
$begingroup$
Here is what I originally posted on SO. stackoverflow.com/questions/46823121/…
$endgroup$
– tmn
Oct 20 '17 at 0:30
$begingroup$
Here is what I originally posted on SO. stackoverflow.com/questions/46823121/…
$endgroup$
– tmn
Oct 20 '17 at 0:30
$begingroup$
It doesn't have to be infinity! It can just be a ridiculously large number like 99999999.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 1:00
$begingroup$
It doesn't have to be infinity! It can just be a ridiculously large number like 99999999.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 1:00
$begingroup$
That would be a numerical disaster.
$endgroup$
– copper.hat
Oct 20 '17 at 1:37
$begingroup$
That would be a numerical disaster.
$endgroup$
– copper.hat
Oct 20 '17 at 1:37
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The continuous time no-overlap constraint cannot be modeled in a pure LP model. You need a discrete variable for that.
Let $S_i$ and $E_i$ be the start and end-time of shift for driver $i$. Then we want to model: $S_ige E_j text{ or } S_jge E_i$ (i.e. shift $i$ is later than shift $j$ or it is earlier). This can be formulated as:
$$
begin{align} &S_ige E_j - Mdelta_{i,j} \ &S_jge E_i - M (1-delta_{i,j})\ &delta_{i,j}in {0,1}
end{align}
$$
where $M$ is a large enough constant (e.g. length of planning window), and $delta_{i,j}$ is a binary variable.
However, usually shift scheduling is modeled with discrete time (i.e. time slots; e.g. personnel shifts start at whole hours). See the remarks in the cross-post for a link to some shift scheduling formulations. In these models, we do not prevent overlaps, but rather minimize cost. It is cheaper to have as few unnecessary overlaps as possible (having more employees than needed is wasteful -- at least from a direct cost perspective).
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
$endgroup$
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
1
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
1
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
2
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fmath.stackexchange.com%2fquestions%2f2480793%2flinear-programming-preventing-staff-scheduling-shift-overlap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The continuous time no-overlap constraint cannot be modeled in a pure LP model. You need a discrete variable for that.
Let $S_i$ and $E_i$ be the start and end-time of shift for driver $i$. Then we want to model: $S_ige E_j text{ or } S_jge E_i$ (i.e. shift $i$ is later than shift $j$ or it is earlier). This can be formulated as:
$$
begin{align} &S_ige E_j - Mdelta_{i,j} \ &S_jge E_i - M (1-delta_{i,j})\ &delta_{i,j}in {0,1}
end{align}
$$
where $M$ is a large enough constant (e.g. length of planning window), and $delta_{i,j}$ is a binary variable.
However, usually shift scheduling is modeled with discrete time (i.e. time slots; e.g. personnel shifts start at whole hours). See the remarks in the cross-post for a link to some shift scheduling formulations. In these models, we do not prevent overlaps, but rather minimize cost. It is cheaper to have as few unnecessary overlaps as possible (having more employees than needed is wasteful -- at least from a direct cost perspective).
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
$endgroup$
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
1
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
1
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
2
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
|
show 3 more comments
$begingroup$
The continuous time no-overlap constraint cannot be modeled in a pure LP model. You need a discrete variable for that.
Let $S_i$ and $E_i$ be the start and end-time of shift for driver $i$. Then we want to model: $S_ige E_j text{ or } S_jge E_i$ (i.e. shift $i$ is later than shift $j$ or it is earlier). This can be formulated as:
$$
begin{align} &S_ige E_j - Mdelta_{i,j} \ &S_jge E_i - M (1-delta_{i,j})\ &delta_{i,j}in {0,1}
end{align}
$$
where $M$ is a large enough constant (e.g. length of planning window), and $delta_{i,j}$ is a binary variable.
However, usually shift scheduling is modeled with discrete time (i.e. time slots; e.g. personnel shifts start at whole hours). See the remarks in the cross-post for a link to some shift scheduling formulations. In these models, we do not prevent overlaps, but rather minimize cost. It is cheaper to have as few unnecessary overlaps as possible (having more employees than needed is wasteful -- at least from a direct cost perspective).
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
$endgroup$
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
1
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
1
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
2
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
|
show 3 more comments
$begingroup$
The continuous time no-overlap constraint cannot be modeled in a pure LP model. You need a discrete variable for that.
Let $S_i$ and $E_i$ be the start and end-time of shift for driver $i$. Then we want to model: $S_ige E_j text{ or } S_jge E_i$ (i.e. shift $i$ is later than shift $j$ or it is earlier). This can be formulated as:
$$
begin{align} &S_ige E_j - Mdelta_{i,j} \ &S_jge E_i - M (1-delta_{i,j})\ &delta_{i,j}in {0,1}
end{align}
$$
where $M$ is a large enough constant (e.g. length of planning window), and $delta_{i,j}$ is a binary variable.
However, usually shift scheduling is modeled with discrete time (i.e. time slots; e.g. personnel shifts start at whole hours). See the remarks in the cross-post for a link to some shift scheduling formulations. In these models, we do not prevent overlaps, but rather minimize cost. It is cheaper to have as few unnecessary overlaps as possible (having more employees than needed is wasteful -- at least from a direct cost perspective).
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
$endgroup$
The continuous time no-overlap constraint cannot be modeled in a pure LP model. You need a discrete variable for that.
Let $S_i$ and $E_i$ be the start and end-time of shift for driver $i$. Then we want to model: $S_ige E_j text{ or } S_jge E_i$ (i.e. shift $i$ is later than shift $j$ or it is earlier). This can be formulated as:
$$
begin{align} &S_ige E_j - Mdelta_{i,j} \ &S_jge E_i - M (1-delta_{i,j})\ &delta_{i,j}in {0,1}
end{align}
$$
where $M$ is a large enough constant (e.g. length of planning window), and $delta_{i,j}$ is a binary variable.
However, usually shift scheduling is modeled with discrete time (i.e. time slots; e.g. personnel shifts start at whole hours). See the remarks in the cross-post for a link to some shift scheduling formulations. In these models, we do not prevent overlaps, but rather minimize cost. It is cheaper to have as few unnecessary overlaps as possible (having more employees than needed is wasteful -- at least from a direct cost perspective).
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
edited Oct 20 '17 at 12:03
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
answered Oct 20 '17 at 6:19
Erwin KalvelagenErwin Kalvelagen
3,2542512
3,2542512
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
1
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
1
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
2
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
|
show 3 more comments
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
1
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
1
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
2
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
That's what was throwing be off because most examples out there were discrete. Thanks I will play with this this weekend
$endgroup$
– tmn
Oct 20 '17 at 11:11
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
$begingroup$
Amazing... so that binary value will allow both scenarios where Si is greater than Ej, or Sj is greater than Ei. I think I know how to input this...
$endgroup$
– tmn
Oct 20 '17 at 13:58
1
1
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
$begingroup$
Correct. $delta_{i,j}=0 Rightarrow S_i ge E_j$ and $delta_{i,j}=1 Rightarrow S_j ge E_i$. Note that for binary variables you need a MIP solver.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 14:09
1
1
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
$begingroup$
@ErwinKalvelagen: Please excuse the hijacking of the comment thread. Do you have any textbook/reference suggestions for MIP? (My background is in continuous parameter optimisation and have a passing familiarity with some purely discrete problems in the context of formal verification for electronic design, but little exposure to MIP.)
$endgroup$
– copper.hat
Oct 20 '17 at 15:01
2
2
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
$begingroup$
@copper.hat There are many. For modeling, I like H.P.Williams. For theory, may be Nemhauser,Wolsey. Maybe someone else can suggest more recent texts.
$endgroup$
– Erwin Kalvelagen
Oct 20 '17 at 15:27
|
show 3 more comments
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f2480793%2flinear-programming-preventing-staff-scheduling-shift-overlap%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
$begingroup$
You can add $infty(Te1-Ts2) + infty(Te2-Ts1) + infty(Te1-Ts3) + infty(Te3-Ts1) + infty(Te2-Ts3) + infty(Te3-Ts2)$ to the objective function. That way it will rule out overlapping. And then once you get the Te and Ts values, you can go ahead and compute the optimal value yourself.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 0:17
$begingroup$
How did we go from a pizza delivery problem to doing distributive work with infinity? Haha, okay. I'm not sure if the library I'm using (ojAlgo) supports infinity as a parameter. I suppose I could try using
Integer.MAX_VALUEalthough I'm not sure that would have the same effect.$endgroup$
– tmn
Oct 20 '17 at 0:29
$begingroup$
Here is what I originally posted on SO. stackoverflow.com/questions/46823121/…
$endgroup$
– tmn
Oct 20 '17 at 0:30
$begingroup$
It doesn't have to be infinity! It can just be a ridiculously large number like 99999999.
$endgroup$
– Abhiram Natarajan
Oct 20 '17 at 1:00
$begingroup$
That would be a numerical disaster.
$endgroup$
– copper.hat
Oct 20 '17 at 1:37