# # Jesuit Volunteer Corps
# This notebook demonstrates the formulation and solution of a team scheduling problem using GLPK/Mathprog.
# ## 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]: get_ipython().run_cell_magic('script', 'glpsol -m /dev/stdin -y JesuitVols.txt --out output', '\n# Example: JesuitVols.mod\n\n/* Number of weeks to schedule */\nparam T := 7;\n\n/* Numeric labels for volunteers facilitate creating non-replicated pairs */\nset VOLS := 1..7;\nset TASKS := {\'Kitchen\', \'Bathroom\', \'Commons\', \'Trash\'};\nset WEEKS := 1..T;\n\n/* Compute all pairs of volunteers */\nset PAIRS := setof{u in VOLS, v in VOLS: u < v} (u,v);\n\n/* x[v,t,w] = 1 if volunteer v is assigned task t in week w */\nvar x{v in VOLS, t in TASKS, w in WEEKS} binary;\n\n/* p[u,v,t,w] = 1 if volunteers u and v are paired together on t in week w */\nvar p{(u,v) in PAIRS, t in TASKS, w in WEEKS} binary;\n\n/* The objective will be the number of times anyone has to do the trash */\nvar z integer;\n\nminimize obj: z;\n\n/* Each volunteer each week must be assigned one task */\ns.t. fa{v in VOLS, w in WEEKS}: sum {t in TASKS} x[v,t,w] = 1;\n\n/* Except for Trash, each task each week must be assigned two volunteers */\ns.t. fb{w in WEEKS}: sum {v in VOLS} x[v,\'Trash\',w] = 1;\ns.t. fc{t in TASKS, w in WEEKS : t <> \'Trash\'}: sum {v in VOLS} x[v,t,w] = 2;\n\n/* Each volunteer must cycle through each task twice (except trash) */\ns.t. fd{t in TASKS, v in VOLS : t <> \'Trash\'}: sum {w in WEEKS} x[v,t,w] >= 2;\n\n/* Minimize number of times anyone has to do trash */\ns.t. fz{v in VOLS}: sum {w in WEEKS} x[v,\'Trash\',w] <= z;\n\n/* Pair p(u,v,t,w) is 1 if u and v worked together on Week w and Task t */\ns.t. ga{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[u,t,w];\ns.t. gb{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[v,t,w];\ns.t. gc{t in TASKS, w in WEEKS, (u,v) in PAIRS}: \n p[u,v,t,w] >= x[u,t,w] + x[v,t,w] - 1;\n\n/* Each possible pair must do at least one task together. */\ns.t. gd{(u,v) in PAIRS}: sum{t in TASKS, w in WEEKS} p[u,v,t,w] >= 1;\n\nsolve;\n\nprintf "Volunteer Assignments by Weeks";\nfor {w in WEEKS}{\n printf "\\n\\nWeek: %2s\\n",w;\n printf "Volunteer:";\n printf {v in VOLS} "%3s",v;\n for {t in TASKS}{\n printf "\\n%9s:",t;\n printf {v in VOLS} "%3s", if x[v,t,w]=1 then "X" else "-";\n }\n}\n\nprintf "\\n\\n\\n Analysis of Volunteer Pairs";\nfor{(u,v) in PAIRS}{\n printf "\\n\\nPair: (%s,%s)\\n",u,v;\n printf " Week:";\n printf {w in WEEKS} "%3s",w;\n for {t in TASKS}{\n printf "\\n%9s:",t;\n printf {w in WEEKS} "%3s", if p[u,v,t,w]=1 then "X" else "-";\n }\n}\n\nend;\n') # In[3]: print(open('JesuitVols.txt').read()) # In[ ]: # # < [Job Shop Scheduling](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/04.03-Job-Shop-Scheduling.ipynb) | [Contents](toc.ipynb) | [Unit Commitment](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/04.05-Unit-Commitment.ipynb) >