{ "cells": [ { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "\n", "*This notebook contains course material from [CBE40455](https://jckantor.github.io/CBE40455) by\n", "Jeffrey Kantor (jeff at nd.edu); the content is available [on Github](https://github.com/jckantor/CBE40455.git).\n", "The text is released under the [CC-BY-NC-ND-4.0 license](https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode),\n", "and code is released under the [MIT license](https://opensource.org/licenses/MIT).*" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "\n", "< [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) >

\"Open

\"Download\"" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "# Jesuit Volunteer Corps" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "This notebook demonstrates the formulation and solution of a team scheduling problem using GLPK/Mathprog." ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "## Background" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "

\n", " The following problem was formulated by Tomas C. (ND '09) who was \n", " working with the Jesuit Volunteer Corp in 2009-2010. Here was his \n", " problem:\n", "

\n", "
\n", " There are 7 of us in the house. We have broken down the chores into 4 \n", " major sections: 1) Kitchen, 2) Bathroom, 3) Common Area, 4) Trash. The \n", " trash is the only task that needs only one person to accomplish, the \n", " other 3 tasks have 2 people assigned to them. Each person needs to rotate\n", " through each task twice and the trash only once. The assignments rotate \n", " each week. Each person needs to have a new partner each week and no \n", " person can have more than one task in a week.\n", "
\n", "

\n", " In the formulation below we require every possible pair to do at least\n", " one task together. This is different that requiring a new partner each \n", " week, but Tomas said later that this would meet their needs.\n", "

\n", "

\n", " This a challenging computation, depending\n", " on your computer this may take a few seconds to a few minutes.\n", "

\n" ] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "## Solution" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false, "pycharm": {} }, "outputs": [], "source": [ "%%script glpsol -m /dev/stdin -y JesuitVols.txt --out output\n", "\n", "# Example: JesuitVols.mod\n", "\n", "/* Number of weeks to schedule */\n", "param T := 7;\n", "\n", "/* Numeric labels for volunteers facilitate creating non-replicated pairs */\n", "set VOLS := 1..7;\n", "set TASKS := {'Kitchen', 'Bathroom', 'Commons', 'Trash'};\n", "set WEEKS := 1..T;\n", "\n", "/* Compute all pairs of volunteers */\n", "set 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 */\n", "var 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 */\n", "var 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 */\n", "var z integer;\n", "\n", "minimize obj: z;\n", "\n", "/* Each volunteer each week must be assigned one task */\n", "s.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 */\n", "s.t. fb{w in WEEKS}: sum {v in VOLS} x[v,'Trash',w] = 1;\n", "s.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) */\n", "s.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 */\n", "s.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 */\n", "s.t. ga{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[u,t,w];\n", "s.t. gb{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[v,t,w];\n", "s.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. */\n", "s.t. gd{(u,v) in PAIRS}: sum{t in TASKS, w in WEEKS} p[u,v,t,w] >= 1;\n", "\n", "solve;\n", "\n", "printf \"Volunteer Assignments by Weeks\";\n", "for {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", "\n", "printf \"\\n\\n\\n Analysis of Volunteer Pairs\";\n", "for{(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", "\n", "end;\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false, "pycharm": {}, "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Volunteer Assignments by Weeks\n", "\n", "Week: 1\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - - - X - X -\n", " Bathroom: - X X - - - -\n", " Commons: X - - - - - X\n", " Trash: - - - - X - -\n", "\n", "Week: 2\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: X - - - X - -\n", " Bathroom: - - X - - - X\n", " Commons: - X - - - X -\n", " Trash: - - - X - - -\n", "\n", "Week: 3\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - - - - X - X\n", " Bathroom: X - - - - X -\n", " Commons: - - X X - - -\n", " Trash: - X - - - - -\n", "\n", "Week: 4\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - X - X - - -\n", " Bathroom: - - - - - X X\n", " Commons: - - X - X - -\n", " Trash: X - - - - - -\n", "\n", "Week: 5\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: X - X - - - -\n", " Bathroom: - X - - X - -\n", " Commons: - - - X - - X\n", " Trash: - - - - - X -\n", "\n", "Week: 6\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - X - - - - X\n", " Bathroom: X - - X - - -\n", " Commons: - - - - X X -\n", " Trash: - - X - - - -\n", "\n", "Week: 7\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - - X - - X -\n", " Bathroom: - - - X X - -\n", " Commons: X X - - - - -\n", " Trash: - - - - - - X\n", "\n", "\n", " Analysis of Volunteer Pairs\n", "\n", "Pair: (1,2)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - X\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,3)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - X - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,4)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - X -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - X - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - X - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: X - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,3)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: X - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,4)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - X - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - X - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - X - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - X -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,4)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - X - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - X - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - X\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - X - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (4,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - X\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (4,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: X - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (4,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - X - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (5,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - X -\n", " Trash: - - - - - - -\n", "\n", "Pair: (5,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - X - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (6,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - X - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n" ] } ], "source": [ "print(open('JesuitVols.txt').read())" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true, "pycharm": {} }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": { "pycharm": {} }, "source": [ "\n", "< [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) >

\"Open

\"Download\"" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.10" } }, "nbformat": 4, "nbformat_minor": 0 }