J.C. Kantor (Kantor.1@nd.edu)
This IPython notebook demonstrates the formulation and solution of a team scheduling problem using GLPK/Mathprog.
from IPython.core.display import HTML
HTML(open("styles/custom.css", "r").read())
The following problem was formulated by Tomas C. (ND '09) who was working with the Jesuit Volunteer Corp in 2009-2010. Here was his problem:
There are 7 of us in the house. We have broken down the chores into 4 major sections: 1) Kitchen, 2) Bathroom, 3) Common Area, 4) Trash. The trash is the only task that needs only one person to accomplish, the other 3 tasks have 2 people assigned to them. Each person needs to rotate through each task twice and the trash only once. The assignments rotate each week. Each person needs to have a new partner each week and no person can have more than one task in a week.
In the formulation below we require every possible pair to do at least one task together. This is different that requiring a new partner each week, but Tomas said later that this would meet their needs.
This a challenging computation, depending on your computer this may take a few seconds to a few minutes.
%%script glpsol -m /dev/stdin
# Example: JesuitVols.mod
/* Number of weeks to schedule */
param T := 7;
/* Numeric labels for volunteers facilitate creating non-replicated pairs */
set VOLS := 1..7;
set TASKS := {'Kitchen', 'Bathroom', 'Commons', 'Trash'};
set WEEKS := 1..T;
/* Compute all pairs of volunteers */
set PAIRS := setof{u in VOLS, v in VOLS: u < v} (u,v);
/* x[v,t,w] = 1 if volunteer v is assigned task t in week w */
var x{v in VOLS, t in TASKS, w in WEEKS} binary;
/* p[u,v,t,w] = 1 if volunteers u and v are paired together on t in week w */
var p{(u,v) in PAIRS, t in TASKS, w in WEEKS} binary;
/* The objective will be the number of times anyone has to do the trash */
var z integer;
minimize obj: z;
/* Each volunteer each week must be assigned one task */
s.t. fa{v in VOLS, w in WEEKS}: sum {t in TASKS} x[v,t,w] = 1;
/* Except for Trash, each task each week must be assigned two volunteers */
s.t. fb{w in WEEKS}: sum {v in VOLS} x[v,'Trash',w] = 1;
s.t. fc{t in TASKS, w in WEEKS : t <> 'Trash'}: sum {v in VOLS} x[v,t,w] = 2;
/* Each volunteer must cycle through each task twice (except trash) */
s.t. fd{t in TASKS, v in VOLS : t <> 'Trash'}: sum {w in WEEKS} x[v,t,w] >= 2;
/* Minimize number of times anyone has to do trash */
s.t. fz{v in VOLS}: sum {w in WEEKS} x[v,'Trash',w] <= z;
/* Pair p(u,v,t,w) is 1 if u and v worked together on Week w and Task t */
s.t. ga{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[u,t,w];
s.t. gb{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[v,t,w];
s.t. gc{t in TASKS, w in WEEKS, (u,v) in PAIRS}:
p[u,v,t,w] >= x[u,t,w] + x[v,t,w] - 1;
/* Each possible pair must do at least one task together. */
s.t. gd{(u,v) in PAIRS}: sum{t in TASKS, w in WEEKS} p[u,v,t,w] >= 1;
solve;
printf "Volunteer Assignments by Weeks";
for {w in WEEKS}{
printf "\n\nWeek: %2s\n",w;
printf "Volunteer:";
printf {v in VOLS} "%3s",v;
for {t in TASKS}{
printf "\n%9s:",t;
printf {v in VOLS} "%3s", if x[v,t,w]=1 then "X" else "-";
}
}
printf "\n\n\n Analysis of Volunteer Pairs";
for{(u,v) in PAIRS}{
printf "\n\nPair: (%s,%s)\n",u,v;
printf " Week:";
printf {w in WEEKS} "%3s",w;
for {t in TASKS}{
printf "\n%9s:",t;
printf {w in WEEKS} "%3s", if p[u,v,t,w]=1 then "X" else "-";
}
}
end;
GLPSOL: GLPK LP/MIP Solver, v4.52 Parameter(s) specified in the command line: -m /dev/stdin Reading model section from /dev/stdin... /dev/stdin:72: warning: final NL missing before end of file 72 lines were read Generating obj... Generating fa... Generating fb... Generating fc... Generating fd... Generating fz... Generating ga... Generating gb... Generating gc... Generating gd... Model has been successfully generated GLPK Integer Optimizer, v4.52 1891 rows, 785 columns, 5300 non-zeros 785 integer variables, 784 of which are binary Preprocessing... 1890 rows, 785 columns, 5299 non-zeros 785 integer variables, 784 of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part is 1883 Solving LP relaxation... GLPK Simplex Optimizer, v4.52 1890 rows, 785 columns, 5299 non-zeros 0: obj = 0.000000000e+00 infeas = 5.960e+02 (7) 500: obj = 1.000000000e+00 infeas = 2.125e+01 (7) * 717: obj = 1.000000000e+00 infeas = 2.748e-15 (7) * 718: obj = 1.000000000e+00 infeas = 3.446e-15 (7) OPTIMAL LP SOLUTION FOUND Integer optimization begins... + 718: mip = not found yet >= -inf (1; 0) + 17067: >>>>> 1.000000000e+00 >= 1.000000000e+00 0.0% (49; 116) + 17067: mip = 1.000000000e+00 >= tree is empty 0.0% (0; 247) INTEGER OPTIMAL SOLUTION FOUND Time used: 3.1 secs Memory used: 4.0 Mb (4168594 bytes) Volunteer Assignments by Weeks Week: 1 Volunteer: 1 2 3 4 5 6 7 Kitchen: - - - X - X - Bathroom: - X X - - - - Commons: X - - - - - X Trash: - - - - X - - Week: 2 Volunteer: 1 2 3 4 5 6 7 Kitchen: X - - - X - - Bathroom: - - X - - - X Commons: - X - - - X - Trash: - - - X - - - Week: 3 Volunteer: 1 2 3 4 5 6 7 Kitchen: - - - - X - X Bathroom: X - - - - X - Commons: - - X X - - - Trash: - X - - - - - Week: 4 Volunteer: 1 2 3 4 5 6 7 Kitchen: - X - X - - - Bathroom: - - - - - X X Commons: - - X - X - - Trash: X - - - - - - Week: 5 Volunteer: 1 2 3 4 5 6 7 Kitchen: X - X - - - - Bathroom: - X - - X - - Commons: - - - X - - X Trash: - - - - - X - Week: 6 Volunteer: 1 2 3 4 5 6 7 Kitchen: - X - - - - X Bathroom: X - - X - - - Commons: - - - - X X - Trash: - - X - - - - Week: 7 Volunteer: 1 2 3 4 5 6 7 Kitchen: - - X - - X - Bathroom: - - - X X - - Commons: X X - - - - - Trash: - - - - - - X Analysis of Volunteer Pairs Pair: (1,2) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: - - - - - - X Trash: - - - - - - - Pair: (1,3) Week: 1 2 3 4 5 6 7 Kitchen: - - - - X - - Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (1,4) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - X - Commons: - - - - - - - Trash: - - - - - - - Pair: (1,5) Week: 1 2 3 4 5 6 7 Kitchen: - X - - - - - Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (1,6) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - X - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (1,7) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: X - - - - - - Trash: - - - - - - - Pair: (2,3) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: X - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (2,4) Week: 1 2 3 4 5 6 7 Kitchen: - - - X - - - Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (2,5) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - X - - Commons: - - - - - - - Trash: - - - - - - - Pair: (2,6) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: - X - - - - - Trash: - - - - - - - Pair: (2,7) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - X - Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (3,4) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: - - X - - - - Trash: - - - - - - - Pair: (3,5) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: - - - X - - - Trash: - - - - - - - Pair: (3,6) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - X Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (3,7) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - X - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (4,5) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - X Commons: - - - - - - - Trash: - - - - - - - Pair: (4,6) Week: 1 2 3 4 5 6 7 Kitchen: X - - - - - - Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (4,7) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: - - - - X - - Trash: - - - - - - - Pair: (5,6) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - - - - - Commons: - - - - - X - Trash: - - - - - - - Pair: (5,7) Week: 1 2 3 4 5 6 7 Kitchen: - - X - - - - Bathroom: - - - - - - - Commons: - - - - - - - Trash: - - - - - - - Pair: (6,7) Week: 1 2 3 4 5 6 7 Kitchen: - - - - - - - Bathroom: - - - X - - - Commons: - - - - - - - Trash: - - - - - - -Model has been successfully processed