The latest version of this IPython notebook is available at http://github.com/jckantor/ESTM60203 for noncommercial use under terms of the Creative Commons Attribution Noncommericial ShareAlike License (CC BY-NC-SA 4.0).

J.C. Kantor ([email protected])

Jesuit Volunteer Corps

This IPython notebook demonstrates the formulation and solution of a team scheduling problem using GLPK/Mathprog.

Initializations
In [1]:
from IPython.core.display import HTML
HTML(open("styles/custom.css", "r").read())
Out[1]:

Background

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.

Solution

In [2]:
%%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