On-Call Weekends? (Linear Programming)
$begingroup$
There are 9 persons. On every weekend two of them has to be on-call. I want to create on-call calendar so that
- every person will have at least two free weekends after an on-call weekend
- on-call pairs will always change
Possible pairs are (persons are 1...9), total 36 different pairs:
12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
How can i solve this with Excel solver, or GLPK?
> lp beginner, Finland
linear-programming integer-programming mixed-integer-programming
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
asked Aug 23 '16 at 11:03
M. H.M. H.
111
$endgroup$
add a comment |
$begingroup$
There are 9 persons. On every weekend two of them has to be on-call. I want to create on-call calendar so that
- every person will have at least two free weekends after an on-call weekend
- on-call pairs will always change
Possible pairs are (persons are 1...9), total 36 different pairs:
12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
How can i solve this with Excel solver, or GLPK?
> lp beginner, Finland
linear-programming integer-programming mixed-integer-programming
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
asked Aug 23 '16 at 11:03
M. H.M. H.
111
$endgroup$
$begingroup$
Actually LP (linear programming) assumes continuous decision variables. I believe this scheduling problem will need a Mixed Integer Programming (MIP) solver.
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 11:29
$begingroup$
Thanks. Excel and GLPK can handle integer and binary variables.
$endgroup$
– M. H.
Aug 23 '16 at 11:32
add a comment |
$begingroup$
There are 9 persons. On every weekend two of them has to be on-call. I want to create on-call calendar so that
- every person will have at least two free weekends after an on-call weekend
- on-call pairs will always change
Possible pairs are (persons are 1...9), total 36 different pairs:
12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
How can i solve this with Excel solver, or GLPK?
> lp beginner, Finland
linear-programming integer-programming mixed-integer-programming
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
asked Aug 23 '16 at 11:03
M. H.M. H.
111
$endgroup$
There are 9 persons. On every weekend two of them has to be on-call. I want to create on-call calendar so that
- every person will have at least two free weekends after an on-call weekend
- on-call pairs will always change
Possible pairs are (persons are 1...9), total 36 different pairs:
12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
How can i solve this with Excel solver, or GLPK?
> lp beginner, Finland
linear-programming integer-programming mixed-integer-programming
linear-programming integer-programming mixed-integer-programming
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
asked Aug 23 '16 at 11:03
M. H.M. H.
111
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
asked Aug 23 '16 at 11:03
M. H.M. H.
111
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
edited Aug 23 '16 at 14:22
Michael Grant
15k11944
15k11944
asked Aug 23 '16 at 11:03
M. H.M. H.
111
asked Aug 23 '16 at 11:03
M. H.M. H.
111
asked Aug 23 '16 at 11:03
M. H.M. H.
111
111
$begingroup$
Actually LP (linear programming) assumes continuous decision variables. I believe this scheduling problem will need a Mixed Integer Programming (MIP) solver.
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 11:29
$begingroup$
Thanks. Excel and GLPK can handle integer and binary variables.
$endgroup$
– M. H.
Aug 23 '16 at 11:32
add a comment |
$begingroup$
Actually LP (linear programming) assumes continuous decision variables. I believe this scheduling problem will need a Mixed Integer Programming (MIP) solver.
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 11:29
$begingroup$
Thanks. Excel and GLPK can handle integer and binary variables.
$endgroup$
– M. H.
Aug 23 '16 at 11:32
$begingroup$
Actually LP (linear programming) assumes continuous decision variables. I believe this scheduling problem will need a Mixed Integer Programming (MIP) solver.
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 11:29
$begingroup$
Actually LP (linear programming) assumes continuous decision variables. I believe this scheduling problem will need a Mixed Integer Programming (MIP) solver.
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 11:29
$begingroup$
Thanks. Excel and GLPK can handle integer and binary variables.
$endgroup$
– M. H.
Aug 23 '16 at 11:32
$begingroup$
Thanks. Excel and GLPK can handle integer and binary variables.
$endgroup$
– M. H.
Aug 23 '16 at 11:32
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.
Let's use the following notation:
- $x_{i,t} in {0,1}$ is assigning person $i$ to weekend $t$
- $y_{i,j,t} in {0,1}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.
The obvious constraints on $y$ are:
$$begin{align}
&sum_{(i,j) in P} y_{i,j,t} = 1 & forall t >>& text{(one pair per weekend)} \
&sum_t y_{i,j,t} le 1 & forall (i,j) in P
>> & text{(no repeats of pairs)}end{align}$$
The constraint on $x$ is that we need $x_{i,t}=1 implies x_{i,t+1}=x_{i,t+2}=0 $ . This we can formulate surprisingly simple as:
$$
x_{i,t}+x_{i,t+1}+x_{i,t+2} le 1 >> forall i,t
$$
(The equivalence of these two requires a bit of thought).
Finally we need to connect $x$ and $y$. This is done by $y_{i,j,t}=x_{i,t} cdot x_{j,t}$. This binary multiplication can be linearized as:
$$begin{align}
& y_{i,j,t} le x_{i,t} & forall (i,j) in P, forall t\
& y_{i,j,t} le x_{j,t} & forall (i,j) in P, forall t\
& y_{i,j,t} ge x_{i,t}+x_{j,t}-1 & forall (i,j) in P, forall t
end{align}$$
There is no objective. This MIP model can be solved with any MIP solver (although Excel solver has size limits that are probably too small for this problem). As there is no objective the solver will stop at the first integer feasible point. A constraint programming (CP) solver would make the model simpler to express.
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
$endgroup$
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
add a comment |
$begingroup$
Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:
(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
$endgroup$
add a comment |
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%2f1900953%2fon-call-weekends-linear-programming%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$
Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.
Let's use the following notation:
- $x_{i,t} in {0,1}$ is assigning person $i$ to weekend $t$
- $y_{i,j,t} in {0,1}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.
The obvious constraints on $y$ are:
$$begin{align}
&sum_{(i,j) in P} y_{i,j,t} = 1 & forall t >>& text{(one pair per weekend)} \
&sum_t y_{i,j,t} le 1 & forall (i,j) in P
>> & text{(no repeats of pairs)}end{align}$$
The constraint on $x$ is that we need $x_{i,t}=1 implies x_{i,t+1}=x_{i,t+2}=0 $ . This we can formulate surprisingly simple as:
$$
x_{i,t}+x_{i,t+1}+x_{i,t+2} le 1 >> forall i,t
$$
(The equivalence of these two requires a bit of thought).
Finally we need to connect $x$ and $y$. This is done by $y_{i,j,t}=x_{i,t} cdot x_{j,t}$. This binary multiplication can be linearized as:
$$begin{align}
& y_{i,j,t} le x_{i,t} & forall (i,j) in P, forall t\
& y_{i,j,t} le x_{j,t} & forall (i,j) in P, forall t\
& y_{i,j,t} ge x_{i,t}+x_{j,t}-1 & forall (i,j) in P, forall t
end{align}$$
There is no objective. This MIP model can be solved with any MIP solver (although Excel solver has size limits that are probably too small for this problem). As there is no objective the solver will stop at the first integer feasible point. A constraint programming (CP) solver would make the model simpler to express.
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
$endgroup$
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
add a comment |
$begingroup$
Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.
Let's use the following notation:
- $x_{i,t} in {0,1}$ is assigning person $i$ to weekend $t$
- $y_{i,j,t} in {0,1}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.
The obvious constraints on $y$ are:
$$begin{align}
&sum_{(i,j) in P} y_{i,j,t} = 1 & forall t >>& text{(one pair per weekend)} \
&sum_t y_{i,j,t} le 1 & forall (i,j) in P
>> & text{(no repeats of pairs)}end{align}$$
The constraint on $x$ is that we need $x_{i,t}=1 implies x_{i,t+1}=x_{i,t+2}=0 $ . This we can formulate surprisingly simple as:
$$
x_{i,t}+x_{i,t+1}+x_{i,t+2} le 1 >> forall i,t
$$
(The equivalence of these two requires a bit of thought).
Finally we need to connect $x$ and $y$. This is done by $y_{i,j,t}=x_{i,t} cdot x_{j,t}$. This binary multiplication can be linearized as:
$$begin{align}
& y_{i,j,t} le x_{i,t} & forall (i,j) in P, forall t\
& y_{i,j,t} le x_{j,t} & forall (i,j) in P, forall t\
& y_{i,j,t} ge x_{i,t}+x_{j,t}-1 & forall (i,j) in P, forall t
end{align}$$
There is no objective. This MIP model can be solved with any MIP solver (although Excel solver has size limits that are probably too small for this problem). As there is no objective the solver will stop at the first integer feasible point. A constraint programming (CP) solver would make the model simpler to express.
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
$endgroup$
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
add a comment |
$begingroup$
Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.
Let's use the following notation:
- $x_{i,t} in {0,1}$ is assigning person $i$ to weekend $t$
- $y_{i,j,t} in {0,1}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.
The obvious constraints on $y$ are:
$$begin{align}
&sum_{(i,j) in P} y_{i,j,t} = 1 & forall t >>& text{(one pair per weekend)} \
&sum_t y_{i,j,t} le 1 & forall (i,j) in P
>> & text{(no repeats of pairs)}end{align}$$
The constraint on $x$ is that we need $x_{i,t}=1 implies x_{i,t+1}=x_{i,t+2}=0 $ . This we can formulate surprisingly simple as:
$$
x_{i,t}+x_{i,t+1}+x_{i,t+2} le 1 >> forall i,t
$$
(The equivalence of these two requires a bit of thought).
Finally we need to connect $x$ and $y$. This is done by $y_{i,j,t}=x_{i,t} cdot x_{j,t}$. This binary multiplication can be linearized as:
$$begin{align}
& y_{i,j,t} le x_{i,t} & forall (i,j) in P, forall t\
& y_{i,j,t} le x_{j,t} & forall (i,j) in P, forall t\
& y_{i,j,t} ge x_{i,t}+x_{j,t}-1 & forall (i,j) in P, forall t
end{align}$$
There is no objective. This MIP model can be solved with any MIP solver (although Excel solver has size limits that are probably too small for this problem). As there is no objective the solver will stop at the first integer feasible point. A constraint programming (CP) solver would make the model simpler to express.
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
$endgroup$
Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.
Let's use the following notation:
- $x_{i,t} in {0,1}$ is assigning person $i$ to weekend $t$
- $y_{i,j,t} in {0,1}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.
The obvious constraints on $y$ are:
$$begin{align}
&sum_{(i,j) in P} y_{i,j,t} = 1 & forall t >>& text{(one pair per weekend)} \
&sum_t y_{i,j,t} le 1 & forall (i,j) in P
>> & text{(no repeats of pairs)}end{align}$$
The constraint on $x$ is that we need $x_{i,t}=1 implies x_{i,t+1}=x_{i,t+2}=0 $ . This we can formulate surprisingly simple as:
$$
x_{i,t}+x_{i,t+1}+x_{i,t+2} le 1 >> forall i,t
$$
(The equivalence of these two requires a bit of thought).
Finally we need to connect $x$ and $y$. This is done by $y_{i,j,t}=x_{i,t} cdot x_{j,t}$. This binary multiplication can be linearized as:
$$begin{align}
& y_{i,j,t} le x_{i,t} & forall (i,j) in P, forall t\
& y_{i,j,t} le x_{j,t} & forall (i,j) in P, forall t\
& y_{i,j,t} ge x_{i,t}+x_{j,t}-1 & forall (i,j) in P, forall t
end{align}$$
There is no objective. This MIP model can be solved with any MIP solver (although Excel solver has size limits that are probably too small for this problem). As there is no objective the solver will stop at the first integer feasible point. A constraint programming (CP) solver would make the model simpler to express.
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
edited Aug 23 '16 at 14:59
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
answered Aug 23 '16 at 13:57
Erwin KalvelagenErwin Kalvelagen
3,1192511
3,1192511
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
add a comment |
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
Thank You ! Now can i ask a little more help. I have a reference (different problem) here www3.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMVO.mod and another very simple example (without obj function) ... var x; var y; s.t. c1: x + y <= 6; s.t. c2: x + y >= 7; solve; ... GLPK can input these. But i cannot create .mod file from your great answer ?
$endgroup$
– M. H.
Aug 23 '16 at 15:46
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
$begingroup$
I think the mathematical model above can be translated directly into AMPL or the GLPK's version of AMPL (GLPK implements a subset of AMPL).
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 19:38
add a comment |
$begingroup$
Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:
(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
$endgroup$
add a comment |
$begingroup$
Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:
(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
$endgroup$
add a comment |
$begingroup$
Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:
(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
$endgroup$
Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:
(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
answered Oct 20 '17 at 8:04
TavasanisTavasanis
665
665
add a comment |
add a comment |
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%2f1900953%2fon-call-weekends-linear-programming%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$
Actually LP (linear programming) assumes continuous decision variables. I believe this scheduling problem will need a Mixed Integer Programming (MIP) solver.
$endgroup$
– Erwin Kalvelagen
Aug 23 '16 at 11:29
$begingroup$
Thanks. Excel and GLPK can handle integer and binary variables.
$endgroup$
– M. H.
Aug 23 '16 at 11:32