Skip to content

Instantly share code, notes, and snippets.

@mino98

mino98/hospital_scheduling.ipynb

Created February 13, 2020 21:20
Show Gist options
  • Save mino98/5ad8ae745eb4dbb283707b85b8980d69 to your computer and use it in GitHub Desktop.
Save mino98/5ad8ae745eb4dbb283707b85b8980d69 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
hospital_scheduling.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "hospital_scheduling",
"provenance": [],
"collapsed_sections": []
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "code",
"metadata": {
"id": "cgVeu4ExazdK",
"colab_type": "code",
"colab": {}
},
"source": [
"# This is an instance of the nurse scheduling problem, vaguely (?) based on:\n",
"# https://developers.google.com/optimization/scheduling/employee_scheduling#requests"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "QeplXUdF5u2s",
"colab_type": "code",
"outputId": "8fc35eec-12e0-49f5-cafe-76df96bb671e",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 324
}
},
"source": [
"!pip install --upgrade ortools"
],
"execution_count": 3,
"outputs": [
{
"output_type": "stream",
"text": [
"Collecting ortools\n",
"\u001b[?25l Downloading https://files.pythonhosted.org/packages/db/8f/7c099bcedd55df8f215ba42b50fd4db6fa5de69bb5b14a0586871683edcd/ortools-7.5.7466-cp36-cp36m-manylinux1_x86_64.whl (27.9MB)\n",
"\u001b[K |████████████████████████████████| 27.9MB 1.3MB/s \n",
"\u001b[?25hRequirement already satisfied, skipping upgrade: six>=1.10 in /usr/local/lib/python3.6/dist-packages (from ortools) (1.12.0)\n",
"Collecting protobuf>=3.11.2\n",
"\u001b[?25l Downloading https://files.pythonhosted.org/packages/57/02/5432412c162989260fab61fa65e0a490c1872739eb91a659896e4d554b26/protobuf-3.11.3-cp36-cp36m-manylinux1_x86_64.whl (1.3MB)\n",
"\u001b[K |████████████████████████████████| 1.3MB 36.9MB/s \n",
"\u001b[?25hRequirement already satisfied, skipping upgrade: setuptools in /usr/local/lib/python3.6/dist-packages (from protobuf>=3.11.2->ortools) (45.1.0)\n",
"Installing collected packages: protobuf, ortools\n",
" Found existing installation: protobuf 3.10.0\n",
" Uninstalling protobuf-3.10.0:\n",
" Successfully uninstalled protobuf-3.10.0\n",
"Successfully installed ortools-7.5.7466 protobuf-3.11.3\n"
],
"name": "stdout"
},
{
"output_type": "display_data",
"data": {
"application/vnd.colab-display-data+json": {
"pip_warning": {
"packages": [
"google"
]
}
}
},
"metadata": {
"tags": []
}
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "D8YWI1DD55M-",
"colab_type": "code",
"colab": {}
},
"source": [
"from string import ascii_uppercase \n",
"from ortools.sat.python import cp_model"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "FPd4DcOlFSln",
"colab_type": "code",
"colab": {}
},
"source": [
"num_docs_anytime = 7 # number of docs that can work at any shift (mornings, afternoons, nights)\n",
"num_docs_dayonly = 2 # number of docs that only work daytime (mornings or afternoons)\n",
"num_shifts_in_we = 5 # number of shifts in each weekend as follows:\n",
" # saturday afternoon: ID 0\n",
" # saturday night: ID 1\n",
" # sunday morning: ID 2\n",
" # sunday afternoon: ID 3\n",
" # sunday night: ID 4\n",
"num_weekends = 12 # number of weekends to schedule\n",
"\n",
"all_docs_anytime = range(num_docs_anytime)\n",
"all_docs_dayonly = range(num_docs_anytime, num_docs_anytime + num_docs_dayonly)\n",
"all_docs = range(num_docs_anytime + num_docs_dayonly)\n",
"all_shifts = range(num_shifts_in_we)\n",
"all_weekends = range(num_weekends)\n",
"\n",
"# we call the doctors \"A\", \"B\", etc.\n",
"doc_names = [ascii_uppercase[i] for i in range(num_docs_anytime + num_docs_dayonly)]\n",
"\n",
"model = cp_model.CpModel()"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "JIko4p1oFtT9",
"colab_type": "code",
"colab": {}
},
"source": [
"# Creates shift variables: shifts[(d, w, s)]: doc 'd', weekend \"w\", shift \"s\".\n",
"\n",
"shifts = {}\n",
"for d in all_docs:\n",
" for w in all_weekends:\n",
" for s in all_shifts:\n",
" shifts[(d, w, s)] = model.NewBoolVar('shift_d%iw%is%i' % (d, w, s))"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "Z2qDxcOyFwDL",
"colab_type": "code",
"colab": {}
},
"source": [
"# Each shift is assigned to exactly one doc:\n",
"\n",
"for w in all_weekends:\n",
" for s in all_shifts:\n",
" model.Add(sum(shifts[(d, w, s)] for d in all_docs) == 1)"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "b3Gmm5rdFyK2",
"colab_type": "code",
"colab": {}
},
"source": [
"# Day-only doctors don't work on night shifts (nights are shifts with ID 1 and 4, see above):\n",
"\n",
"for d in all_docs_dayonly:\n",
" for w in all_weekends:\n",
" model.Add(shifts[(d, w, 1)] == 0)\n",
" model.Add(shifts[(d, w, 4)] == 0)"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "aNe_uO9HOHSI",
"colab_type": "code",
"colab": {}
},
"source": [
"# Various constraints. \n",
"# constraint num: if you work: you can't work on:\n",
"# 1 sat_afternoon (0) sat_night (1)\n",
"# 2 sat_night (1) sun_morning (2)\n",
"# 3 sun_morning (2) sun_afternoon (3)\n",
"# 4 sun_afternoon (3) sun_night (4)\n",
"\n",
"for d in all_docs:\n",
" for w in all_weekends:\n",
" model.Add(shifts[(d, w, 0)] + shifts[(d, w, 1)] < 2)\n",
" model.Add(shifts[(d, w, 1)] + shifts[(d, w, 2)] < 2)\n",
" model.Add(shifts[(d, w, 2)] + shifts[(d, w, 3)] < 2)\n",
" model.Add(shifts[(d, w, 3)] + shifts[(d, w, 4)] < 2)"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "Tf7-7x2tPnjI",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "4f52c41d-0713-4170-b006-efc3ba822406"
},
"source": [
"# Cost parameter #1: the maximum number of weekends in which any single doc works\n",
"\n",
"num_of_we_worked = {}\n",
"we_worked = {}\n",
"\n",
"for d in all_docs:\n",
" for w in all_weekends:\n",
" # we_worked is 1 if d has worked in w, 0 otherwise\n",
" we_worked[(d, w)] = model.NewIntVar(0, 1, 'we_worked_d%iw%i' % (d, w))\n",
" model.AddMaxEquality(we_worked[(d, w)], [shifts[(d, w, s)] for s in all_shifts])\n",
"\n",
" num_of_we_worked[d] = model.NewIntVar(0, 999, 'num_of_we_worked_d%i' % (d))\n",
" model.Add(num_of_we_worked[(d)] == sum([we_worked[(d, w)] for w in all_weekends]))\n",
" \n",
"max_num_of_we_worked = model.NewIntVar(0, 999, 'max_num_of_we_worked')\n",
"model.AddMaxEquality(max_num_of_we_worked, [num_of_we_worked[(d)] for d in all_docs])"
],
"execution_count": 25,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"<ortools.sat.python.cp_model.Constraint at 0x7fb9287f0240>"
]
},
"metadata": {
"tags": []
},
"execution_count": 25
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "HbkfHhaBF1Ig",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "1eabfec8-0c22-4bc2-cd31-875c7718f69a"
},
"source": [
"# Cost parameter #2: minimize the max number of \"shift-units\" (SU) worked. \n",
"# We define 1 SU for daytime shifts and 2 SUs for nights.\n",
"\n",
"su_worked_per_we = {}\n",
"su_worked = {}\n",
"\n",
"for d in all_docs:\n",
" for w in all_weekends:\n",
" # we_worked is 1 if d has worked in w, 0 otherwise\n",
" su_worked_per_we[(d, w)] = model.NewIntVar(0, 999, 'su_worked_per_we_d%iw%i' % (d, w))\n",
" model.Add(su_worked_per_we[(d, w)] == \n",
" (shifts[(d, w, 0)] + shifts[(d, w, 2)] + shifts[(d, w, 3)]) \n",
" + 2 * (shifts[(d, w, 1)] + shifts[(d, w, 4)])\n",
" ) \n",
" \n",
" su_worked[d] = model.NewIntVar(0, 999, 'su_worked_d%i' % (d))\n",
" model.Add(su_worked[(d)] == sum([su_worked_per_we[(d, w)] for w in all_weekends]))\n",
" \n",
"max_su_worked = model.NewIntVar(0, 999, 'max_su_worked')\n",
"model.AddMaxEquality(max_su_worked, [su_worked[(d)] for d in all_docs])"
],
"execution_count": 26,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"<ortools.sat.python.cp_model.Constraint at 0x7fb928792908>"
]
},
"metadata": {
"tags": []
},
"execution_count": 26
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "JGJtJcYEUD1b",
"colab_type": "code",
"colab": {}
},
"source": [
"# Let's minimize the sum of the two cost functions \n",
"# (fixme: they should be normalized in their ranges, maybe?)\n",
"model.Minimize(max_su_worked + max_num_of_we_worked)"
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "code",
"metadata": {
"id": "FbyJuyCDaVo6",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "fac54571-c8e0-4b8f-cf55-0e549d98e246"
},
"source": [
"solver = cp_model.CpSolver()\n",
"\n",
"# Sets a time limit because I'm lazy\n",
"solver.parameters.max_time_in_seconds = 30.0\n",
"\n",
"status = solver.Solve(model)\n",
"\n",
"if status == cp_model.INFEASIBLE:\n",
" print(\"INFEASIBLE\")\n",
"elif status == cp_model.FEASIBLE:\n",
" print(\"FEASIBLE\")\n",
"elif status == cp_model.OPTIMAL:\n",
" print(\"OPTIMAL\")"
],
"execution_count": 28,
"outputs": [
{
"output_type": "stream",
"text": [
"FEASIBLE\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "jl_qe17dUMe1",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 34
},
"outputId": "d8e6e604-ce1c-4936-afef-553a225b155d"
},
"source": [
"print(f\"Best objective value found: {solver.ObjectiveValue()}\")"
],
"execution_count": 29,
"outputs": [
{
"output_type": "stream",
"text": [
"Best objective value found: 14.0\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "smR_7xAbUm7z",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 204
},
"outputId": "63bed7fc-c0b8-43d6-eb1e-2b07598b773a"
},
"source": [
"for d in all_docs:\n",
" print(f\"dr. {doc_names[d]} - number of weekend worked: {solver.Value(num_of_we_worked[(d)])} - total number of shift-units worked: {solver.Value(su_worked[(d)])}\")\n",
"\n",
"print(f\"\\nAverage number of weekends worked per doctor: {sum([solver.Value(num_of_we_worked[(d)]) for d in all_docs]) / (num_docs_anytime+num_docs_dayonly):.2f}\")"
],
"execution_count": 30,
"outputs": [
{
"output_type": "stream",
"text": [
"dr. A - number of weekend worked: 4 - total number of shift-units worked: 10\n",
"dr. B - number of weekend worked: 4 - total number of shift-units worked: 10\n",
"dr. C - number of weekend worked: 3 - total number of shift-units worked: 10\n",
"dr. D - number of weekend worked: 3 - total number of shift-units worked: 10\n",
"dr. E - number of weekend worked: 3 - total number of shift-units worked: 10\n",
"dr. F - number of weekend worked: 4 - total number of shift-units worked: 10\n",
"dr. G - number of weekend worked: 4 - total number of shift-units worked: 10\n",
"dr. H - number of weekend worked: 4 - total number of shift-units worked: 7\n",
"dr. I - number of weekend worked: 4 - total number of shift-units worked: 7\n",
"\n",
"Average number of weekends worked per doctor: 3.67\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "eZw5uzABF4do",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"outputId": "3f609535-55b7-4198-ac04-d75da9bb82c8"
},
"source": [
"def get_doc(weekend, shift):\n",
" \"\"\"Given a shift number, returns the doc name scheduled for that shift\"\"\"\n",
"\n",
" doc_id = [d for d in all_docs if solver.Value(shifts[(d, weekend, shift)]) == 1][0]\n",
" return doc_names[doc_id]\n",
"\n",
"\n",
"for w in all_weekends:\n",
" print(f\"======================= Weekend {w} =======================\")\n",
" print(f\"Saturday Afternoon: dr. {get_doc(w, 0)}\")\n",
" print(f\"Saturday Night: dr. {get_doc(w, 1)}\")\n",
" print(f\"Sunday Morning: dr. {get_doc(w, 2)}\")\n",
" print(f\"Sunday Afternoon: dr. {get_doc(w, 3)}\")\n",
" print(f\"Sunday Night: dr. {get_doc(w, 4)}\")"
],
"execution_count": 31,
"outputs": [
{
"output_type": "stream",
"text": [
"======================= Weekend 0 =======================\n",
"Saturday Afternoon: dr. E\n",
"Saturday Night: dr. A\n",
"Sunday Morning: dr. E\n",
"Sunday Afternoon: dr. A\n",
"Sunday Night: dr. B\n",
"======================= Weekend 1 =======================\n",
"Saturday Afternoon: dr. I\n",
"Saturday Night: dr. G\n",
"Sunday Morning: dr. H\n",
"Sunday Afternoon: dr. I\n",
"Sunday Night: dr. G\n",
"======================= Weekend 2 =======================\n",
"Saturday Afternoon: dr. H\n",
"Saturday Night: dr. C\n",
"Sunday Morning: dr. A\n",
"Sunday Afternoon: dr. H\n",
"Sunday Night: dr. C\n",
"======================= Weekend 3 =======================\n",
"Saturday Afternoon: dr. I\n",
"Saturday Night: dr. F\n",
"Sunday Morning: dr. G\n",
"Sunday Afternoon: dr. I\n",
"Sunday Night: dr. G\n",
"======================= Weekend 4 =======================\n",
"Saturday Afternoon: dr. C\n",
"Saturday Night: dr. F\n",
"Sunday Morning: dr. D\n",
"Sunday Afternoon: dr. C\n",
"Sunday Night: dr. D\n",
"======================= Weekend 5 =======================\n",
"Saturday Afternoon: dr. H\n",
"Saturday Night: dr. E\n",
"Sunday Morning: dr. G\n",
"Sunday Afternoon: dr. H\n",
"Sunday Night: dr. E\n",
"======================= Weekend 6 =======================\n",
"Saturday Afternoon: dr. I\n",
"Saturday Night: dr. B\n",
"Sunday Morning: dr. F\n",
"Sunday Afternoon: dr. I\n",
"Sunday Night: dr. F\n",
"======================= Weekend 7 =======================\n",
"Saturday Afternoon: dr. C\n",
"Saturday Night: dr. D\n",
"Sunday Morning: dr. C\n",
"Sunday Afternoon: dr. D\n",
"Sunday Night: dr. C\n",
"======================= Weekend 8 =======================\n",
"Saturday Afternoon: dr. E\n",
"Saturday Night: dr. A\n",
"Sunday Morning: dr. E\n",
"Sunday Afternoon: dr. A\n",
"Sunday Night: dr. E\n",
"======================= Weekend 9 =======================\n",
"Saturday Afternoon: dr. H\n",
"Saturday Night: dr. F\n",
"Sunday Morning: dr. H\n",
"Sunday Afternoon: dr. F\n",
"Sunday Night: dr. B\n",
"======================= Weekend 10 =======================\n",
"Saturday Afternoon: dr. G\n",
"Saturday Night: dr. B\n",
"Sunday Morning: dr. I\n",
"Sunday Afternoon: dr. G\n",
"Sunday Night: dr. B\n",
"======================= Weekend 11 =======================\n",
"Saturday Afternoon: dr. D\n",
"Saturday Night: dr. A\n",
"Sunday Morning: dr. D\n",
"Sunday Afternoon: dr. A\n",
"Sunday Night: dr. D\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "Y9_UeIPaJQW8",
"colab_type": "code",
"colab": {}
},
"source": [
""
],
"execution_count": 0,
"outputs": []
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment