{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Timetabling Program for SMUS Middle School\n", "#### Copyright © 2020 Hoshino Math Services" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# import sys\n", "# !{sys.executable} -m pip install ortools \n", "\n", "# import modules\n", "import time\n", "import numpy as np\n", "import pandas as pd\n", "from ortools.linear_solver import pywraplp" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Import all the Data for Grades 6-8\n", "InputFile = pd.ExcelFile(\"Middle School Input.xlsx\") \n", "Grade6Matrix = pd.read_excel(InputFile, 'Grade6') \n", "Grade6Info = Grade6Matrix.values.tolist()\n", "Grade7Matrix = pd.read_excel(InputFile, 'Grade7') \n", "Grade7Info = Grade7Matrix.values.tolist()\n", "Grade8Matrix = pd.read_excel(InputFile, 'Grade8') \n", "Grade8Info = Grade8Matrix.values.tolist()\n", "\n", "\n", "# Generate the set of Courses and Teachers at the Middle School\n", "AllCourses = []\n", "AllTeachers = ['Cunningham', 'Kuklinski', 'Enns', 'Floyd', 'Smith', 'Bailey', 'Haydock']\n", "for j in [1,5,9,13]:\n", " for i in range(2, len(Grade6Info)-1):\n", " Course = Grade6Info[i][j]\n", " Teacher = Grade6Info[i][j+2]\n", " if not Course in AllCourses:\n", " AllCourses.append(Course)\n", " if not Teacher in AllTeachers and not pd.isna(Teacher):\n", " AllTeachers.append(Teacher)\n", " for i in range(2, len(Grade7Info)-1):\n", " Course = Grade7Info[i][j]\n", " Teacher = Grade7Info[i][j+2]\n", " if not Course in AllCourses:\n", " AllCourses.append(Course)\n", " if not Teacher in AllTeachers and not pd.isna(Teacher):\n", " AllTeachers.append(Teacher)\n", " for i in range(2, len(Grade8Info)-1):\n", " Course = Grade8Info[i][j]\n", " Teacher = Grade8Info[i][j+2]\n", " if not Course in AllCourses:\n", " AllCourses.append(Course)\n", " if not Teacher in AllTeachers and not pd.isna(Teacher):\n", " AllTeachers.append(Teacher)\n", " \n", " \n", "# For each (Grade, Section, Course) triplet, determine the Teacher of that class.\n", "\n", "GSCTeacher = [ [['Not Applicable' for c in range(40)] for s in range(5)] for g in range(10)]\n", "for j in [1,5,9,13]:\n", " s = int((j+3)/4)\n", " for i in range(2, len(Grade6Info)-1):\n", " Course = Grade6Info[i][j]\n", " Teacher = Grade6Info[i][j+2]\n", " c = AllCourses.index(Course)\n", " if not pd.isna(Teacher):\n", " GSCTeacher[6][s][c] = Teacher\n", " for i in range(2, len(Grade7Info)-1):\n", " Course = Grade7Info[i][j]\n", " Teacher = Grade7Info[i][j+2]\n", " c = AllCourses.index(Course)\n", " if not pd.isna(Teacher):\n", " GSCTeacher[7][s][c] = Teacher\n", " for i in range(2, len(Grade8Info)-1):\n", " Course = Grade8Info[i][j]\n", " Teacher = Grade8Info[i][j+2]\n", " c = AllCourses.index(Course)\n", " if not pd.isna(Teacher):\n", " GSCTeacher[8][s][c] = Teacher" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# Optimize assignment of courses to blocks\n", "\n", "\n", "solver = pywraplp.Solver('SMUS Middle School', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n", "start_time = time.time()\n", "\n", "# Define our Grades, Sections, Days, Periods, Courses\n", "Grades = [6,7,8]\n", "Sections = [1,2,3,4]\n", "Days = [1,2,3,4,5]\n", "Periods = [1,2,3,4,5,6,7]\n", "Courses = range(len(AllCourses))\n", "\n", "\n", "# Define our five-dimensional Boolean Variables\n", "x = {}\n", "for g in Grades:\n", " for s in Sections:\n", " for d in Days:\n", " for p in Periods:\n", " for c in Courses:\n", " x[g,s,d,p,c] = solver.IntVar(0,1, 'x[%d,%d,%d,%d,%d]' % (g,s,d,p,c))\n", "\n", " \n", "# CONSTRAINT 1: For each grade and each section, there is exactly one course each period.\n", "for g in Grades:\n", " for s in Sections:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add( sum(x[g,s,d,p,c] for c in Courses) == 1)\n", " \n", " \n", "# CONSTRAINT 2: Each course must be offered a set number of lessons in each week \n", "for s in Sections:\n", " for i in range(2, len(Grade6Info)-1):\n", " CourseName = Grade6Info[i][4*s-3]\n", " Lessons = Grade6Info[i][4*s-2]\n", " c = AllCourses.index(CourseName)\n", " solver.Add(sum(x[6,s,d,p,c] for d in Days for p in Periods) == Lessons)\n", " for i in range(2, len(Grade7Info)-1):\n", " CourseName = Grade7Info[i][4*s-3]\n", " Lessons = Grade7Info[i][4*s-2]\n", " c = AllCourses.index(CourseName)\n", " solver.Add(sum(x[7,s,d,p,c] for d in Days for p in Periods) == Lessons)\n", " for i in range(2, len(Grade8Info)-1):\n", " CourseName = Grade8Info[i][4*s-3]\n", " Lessons = Grade8Info[i][4*s-2]\n", " c = AllCourses.index(CourseName)\n", " solver.Add(sum(x[8,s,d,p,c] for d in Days for p in Periods) == Lessons)\n", " \n", " \n", "# CONSTRAINT 3: Certain courses must be offered in certain blocks:\n", "# Chapel on Tuesday Period 1, Assembly on Friday Period 1, XPLO on Friday Period 7\n", "# Grade 7 Option in Period 5 (Monday, Thursday)\n", "# Grade 8 Option in Period 5 (Tuesday, Friday)\n", "\n", "for s in Sections:\n", " for g in Grades: \n", " c = AllCourses.index('Chapel')\n", " solver.Add( x[g,s,2,1,c] == 1)\n", " c = AllCourses.index('Assembly')\n", " solver.Add( x[g,s,5,1,c] == 1)\n", " c = AllCourses.index('XPLO')\n", " solver.Add( x[g,s,5,7,c] == 1)\n", "\n", " c = AllCourses.index('OPTION')\n", " solver.Add( x[7,s,1,5,c] == 1)\n", " solver.Add( x[7,s,4,5,c] == 1)\n", " solver.Add( x[8,s,2,5,c] == 1)\n", " solver.Add( x[8,s,5,5,c] == 1)\n", "\n", " c = AllCourses.index('XPE')\n", " solver.Add( x[6,s,1,2,c] == 1)\n", " solver.Add( x[6,s,4,2,c] == 1)\n", " solver.Add( x[7,s,3,2,c] == 1)\n", " solver.Add( x[7,s,5,2,c] == 1)\n", " solver.Add( x[8,s,3,3,c] == 1)\n", " solver.Add( x[8,s,3,4,c] == 1)\n", " \n", " \n", "# CONSTRAINT 4: No teacher can teach two different classes simultaneously\n", "for Teacher in AllTeachers:\n", " Tset = []\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses: \n", " if GSCTeacher[g][s][c] == Teacher:\n", " GradeSectionCourse = [g, s, c]\n", " Tset.append(GradeSectionCourse)\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(sum(x[Tset[z][0],Tset[z][1],d,p,Tset[z][2]] \n", " for z in range(len(Tset))) <= 1)\n", " \n", " \n", "# CONSTRAINT 5: A student can't have two lessons in the same class in non-consecutive periods.\n", "# This constraint automatically implies that each class can be offered at most twice per day.\n", "for p1 in Periods:\n", " for p2 in Periods:\n", " if p2-p1>1:\n", " for g in Grades:\n", " for s in Sections:\n", " for d in Days:\n", " for CourseName in ['Humanities', 'Math', 'Math/Science']:\n", " c = AllCourses.index(CourseName)\n", " solver.Add(x[g,s,d,p1,c] + x[g,s,d,p2,c] <=1)\n", " \n", " \n", "# CONSTRAINT 6: No class (including MFA, MP, MAA) can meet 3 or more times in a day.\n", "for g in Grades:\n", " for s in Sections:\n", " for d in Days:\n", " for c in Courses:\n", " solver.Add( sum(x[g,s,d,p,c] for p in Periods) <=2)\n", "\n", " \n", "# CONSTRAINT 7: Other than Hum, Math/Science, and Science, no multi-lesson class can be \n", "# offered more than once per day to any cohort.\n", "for CourseName in ['French', 'Mandarin', 'Science', 'Art']:\n", " c = AllCourses.index(CourseName)\n", " for g in Grades:\n", " for s in Sections:\n", " for d in Days:\n", " solver.Add( sum(x[g,s,d,p,c] for p in Periods) <= 1)\n", "\n", " \n", "# CONSTRAINT 8: All Grade 6/7/8 students must have at least one Humanities class each day.\n", "c = AllCourses.index('Humanities')\n", "for g in Grades:\n", " for s in Sections:\n", " for d in Days:\n", " solver.Add( sum(x[g,s,d,p,c] for p in Periods) >= 1)\n", "\n", " \n", "# CONSTRAINT 9: All Grade 6/7 students must have at least one Math/Sci class each day.\n", "c = AllCourses.index('Math/Science')\n", "for g in [6,7]:\n", " for s in Sections:\n", " for d in Days:\n", " solver.Add( sum(x[g,s,d,p,c] for p in Periods) >= 1)\n", "\n", " \n", "# CONSTRAINT 10: All Grade 8 students must have Math four times a week\n", "# either 5 singles or 1 double and 3 singles. Thus, there cannot exist a pair of days\n", "# in which Grade 8 math is not taught.\n", "c = AllCourses.index('Math')\n", "for d1 in Days:\n", " for d2 in Days:\n", " if d2-d1>0:\n", " for s in Sections:\n", " solver.Add(sum(x[8,s,d1,p,c]+x[8,s,d2,p,c] for p in Periods) >= 1)\n", " \n", " \n", "# CONSTRAINT 11: Strings lessons must take place in the following periods:\n", "# Monday 5-7, Tuesday 1-7, Wednesday 5-7, Thursday 1-7\n", "# Smith teaches 5/5 MP blocks, 3/4 MAA blocks, 5/6 MFA blocks.\n", "# Also, MP (Music, PE) cannot be taught on Monday or Thursday because of XPE\n", "\n", "\n", "c = AllCourses.index('MP')\n", "solver.Add( sum(x[6,1,1,p,c]+x[6,1,3,p,c] for p in [1,2,3,4]) + sum(x[6,1,5,p,c] for p in [1,2,3,4,5,6,7]) == 0)\n", "c = AllCourses.index('MAA')\n", "solver.Add( sum(x[7,1,1,p,c]+x[7,1,3,p,c] for p in [1,2,3,4]) + sum(x[7,1,5,p,c] for p in [1,2,3,4,5,6,7]) <= 1)\n", "c = AllCourses.index('MFA')\n", "solver.Add( sum(x[8,1,1,p,c]+x[8,1,3,p,c] for p in [1,2,3,4]) + sum(x[8,1,5,p,c] for p in [1,2,3,4,5,6,7]) <= 1)\n", "\n", "\n", "# CONSTRAINT 12: Because of XPE, only one section of Grade 6 MP can be offered on Monday\n", "# or Thursday (and that will be the Shared Music class with no PE)\n", "c = AllCourses.index('MP')\n", "solver.Add( sum(x[6,1,1,p,c] + x[6,1,4,p,c] for p in Periods) <= 1)\n", " \n", " \n", "# CONSTRAINT 13: Choir lessons must take place in the following periods:\n", "# Monday 1-2, Tuesday 1-7, Thursday 5-7, Friday 1-7. Also no Grade 8 lessons during Period 7.\n", "c = AllCourses.index('Choir')\n", "for g in Grades:\n", " for s in Sections:\n", " solver.Add( sum(x[g,s,1,p,c] for p in [3,4,5,6,7]) == 0)\n", " solver.Add( sum(x[g,s,3,p,c] for p in [1,2,3,4,5,6,7]) == 0)\n", " solver.Add( sum(x[g,s,4,p,c] for p in [1,2,3,4]) == 0)\n", "for s in Sections:\n", " for d in Days:\n", " solver.Add( x[8,s,d,7,c] == 0)\n", " \n", "\n", "# CONSTRAINT 14: For each grade, French must take place in the same periods for cohorts A+C, and cohorts B+D\n", "# And Band/Strings must take place in the same periods for cohorts A+C, and cohorts B+D\n", "c = AllCourses.index('French')\n", "for g in [6,7]:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add( x[g,1,d,p,c] == x[g,3,d,p,c])\n", " solver.Add( x[g,2,d,p,c] == x[g,4,d,p,c])\n", " \n", " \n", "# CONSTRAINT 15: Grade 8 students cannot have Art lessons on two consecutive days.\n", "c = AllCourses.index('Art')\n", "for s in Sections:\n", " for d in [1,2,3,4]:\n", " solver.Add(sum(x[8,s,d,p,c] + x[8,s,d+1,p,c] for p in Periods) <= 1) \n", "\n", " \n", "# CONSTRAINT 16: Wilkins teaches at most 5 Art classes in a day.\n", "c = AllCourses.index('Art')\n", "c7 = AllCourses.index('MAA')\n", "for d in Days:\n", " solver.Add(sum(x[g,s,d,p,c] for g in Grades for s in Sections for p in Periods)\n", " + sum(x[7,1,d,p,c7] for p in Periods) <= 4)\n", " \n", " \n", "# CONSTRAINT 17: XPE teachers are not teaching XPE at the same time as their other classes\n", "\n", "xpe = AllCourses.index('XPE')\n", "\n", "for Teacher in ['Cunningham', 'Hollingworth', 'Kuklinski', 'Bell']:\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[6,1,d,p,xpe] <= 1)\n", "\n", "for Teacher in ['Cunningham','Hollingworth', 'Kuklinski', 'Danskin']:\n", " for g in Grades: \n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[7,1,d,p,xpe] <= 1)\n", " \n", "for Teacher in ['Kim', 'DeMerchant', 'Enns', 'Cunningham', 'Kuklinski', 'Floyd', 'Cade']:\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[8,1,d,p,xpe] <= 1)\n", " \n", " \n", "# CONSTRAINT 18: Computer Science (Option Course) cannot happen when any ADST is taking place.\n", "c = AllCourses.index('OPTION')\n", "c6 = AllCourses.index('ADST')\n", "c7 = AllCourses.index('MAA')\n", "c8 = AllCourses.index('MFA')\n", "\n", "for d in Days:\n", " for p in Periods:\n", " solver.Add(x[7,1,d,p,c7] + x[7,1,d,p,c] <= 1)\n", " solver.Add(x[7,1,d,p,c7] + x[8,1,d,p,c] <= 1)\n", " solver.Add(x[8,1,d,p,c8] + x[7,1,d,p,c] <= 1)\n", " solver.Add(x[8,1,d,p,c8] + x[8,1,d,p,c] <= 1)\n", " solver.Add(x[7,1,d,p,c7] + x[8,1,d,p,c8] <= 1)\n", " \n", "for d in Days:\n", " for p in Periods:\n", " for s in Sections:\n", " solver.Add(x[6,s,d,p,c6] + x[7,1,d,p,c] <= 1)\n", " solver.Add(x[6,s,d,p,c6] + x[8,1,d,p,c] <= 1)\n", " solver.Add(x[6,s,d,p,c6] + x[7,1,d,p,c7] <= 1)\n", " solver.Add(x[6,s,d,p,c6] + x[8,1,d,p,c8] <= 1)\n", " \n", "\n", " \n", "# CONSTRAINT 19: Two all-grade Option courses must take place in the morning, on the same days\n", "# as the Option courses taking place in Period 5 that day.\n", "\n", "c = AllCourses.index('OPTION')\n", "for g in [7,8]:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,1,d,p,c] == x[g,2,d,p,c])\n", " solver.Add(x[g,2,d,p,c] == x[g,3,d,p,c])\n", " solver.Add(x[g,3,d,p,c] == x[g,4,d,p,c])\n", " solver.Add(sum(x[7,1,1,p,c] for p in [1,2,3,4]) == 1)\n", " solver.Add(sum(x[7,1,4,p,c] for p in [1,2,3,4]) == 1)\n", " solver.Add(sum(x[8,1,2,p,c] for p in [1,2,3,4]) == 1)\n", " solver.Add(sum(x[8,1,5,p,c] for p in [1,2,3,4]) == 1) \n", " \n", " \n", "# CONSTRAINT 20: Option teachers are not teaching this class at the same time \n", "# as their other classes. Don't worry about Williams, as Williams only teaches Grade 8.\n", "\n", "opt = AllCourses.index('OPTION')\n", "\n", "for Teacher in ['Floyd', 'Zhang', 'Cunningham', 'Kuklinski']:\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[7,1,d,p,opt] <= 1)\n", " solver.Add(x[g,s,d,p,c] + x[8,1,d,p,opt] <= 1)\n", "\n", "\n", "# CONSTRAINT 21: Cunningham and Kuklinski teach OPTION and XPE, so these two courses cannot be \n", "# offered at the same time.\n", "\n", "opt = AllCourses.index('OPTION')\n", "xpe = AllCourses.index('XPE')\n", "\n", "for d in Days:\n", " for p in Periods:\n", " solver.Add(x[6,1,d,p,xpe] + x[7,1,d,p,opt] <= 1)\n", " solver.Add(x[6,1,d,p,xpe] + x[8,1,d,p,opt] <= 1)\n", " solver.Add(x[7,1,d,p,xpe] + x[7,1,d,p,opt] <= 1)\n", " solver.Add(x[7,1,d,p,xpe] + x[8,1,d,p,opt] <= 1)\n", " solver.Add(x[8,1,d,p,xpe] + x[7,1,d,p,opt] <= 1)\n", " solver.Add(x[8,1,d,p,xpe] + x[8,1,d,p,opt] <= 1)\n", "\n", " \n", "# CONSTRAINT 22: Option teachers are not teaching in Period 6 and Period 7 during their Option days,\n", "# since this would imply three afternoon classes in a row.\n", "\n", "for Teacher in ['Floyd', 'Zhang', 'Cunningham', 'Kuklinski']:\n", " Tset = []\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses: \n", " if GSCTeacher[g][s][c] == Teacher:\n", " GradeSectionCourse = [g, s, c]\n", " Tset.append(GradeSectionCourse)\n", " for d in [1,2,4,5]:\n", " solver.Add(sum(x[Tset[z][0],Tset[z][1],d,p,Tset[z][2]]\n", " for z in range(len(Tset)) for p in [6,7]) <= 1) \n", " \n", " \n", "# CONSTRAINT 23: MP teachers are not teaching this class at the same time as their other classes\n", "\n", "c6 = AllCourses.index('MP')\n", "for Teacher in ['Enns', 'Smith', 'Cunningham', 'Kuklinski', 'Hollingworth']:\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[6,1,d,p,c6] <= 1)\n", " \n", " \n", "# CONSTRAINT 24: MAA teachers are not teaching this class at the same time as their other classes\n", "c7 = AllCourses.index('MAA')\n", "for Teacher in ['Enns', 'Smith', 'Kim', 'Wilkins']:\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[7,1,d,p,c7] <= 1)\n", " \n", " \n", "# CONSTRAINT 25: MFA teachers are not teaching this class at the same time as their other classes\n", "c8 = AllCourses.index('MFA')\n", "for Teacher in ['Enns', 'Smith', 'Kim', 'Floyd', 'Marti', 'Pike']:\n", " for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == Teacher:\n", " for d in Days:\n", " for p in Periods:\n", " solver.Add(x[g,s,d,p,c] + x[8,1,d,p,c8] <= 1)\n", " \n", " \n", "# CONSTRAINT 26: MFA, MAA, MP cannot be offered simultaneously because of Enns and Smith\n", "# MP and OPTION cannot be offered simultaneously because of Cunningham and Kuklinski\n", "co = AllCourses.index('OPTION')\n", "c6 = AllCourses.index('MP')\n", "c7 = AllCourses.index('MAA')\n", "c8 = AllCourses.index('MFA')\n", "for d in Days:\n", " for p in Periods:\n", " solver.Add(x[6,1,d,p,c6] + x[7,1,d,p,c7] <= 1)\n", " solver.Add(x[6,1,d,p,c6] + x[8,1,d,p,c8] <= 1)\n", " solver.Add(x[7,1,d,p,c7] + x[8,1,d,p,c8] <= 1)\n", " solver.Add(x[7,1,d,p,co] + x[8,1,d,p,c8] <= 1)\n", " solver.Add(x[6,1,d,p,c6] + x[7,1,d,p,co] <= 1)\n", " solver.Add(x[6,1,d,p,c6] + x[8,1,d,p,co] <= 1)\n", " \n", " \n", "# CONSTRAINT 27: The Grade 6 MP course, the Grade 7 MAA course, and the Grade 8 MFA course must all\n", "# be all-grade courses, taking place in a common period.\n", "c6 = AllCourses.index('MP')\n", "c7 = AllCourses.index('MAA')\n", "c8 = AllCourses.index('MFA')\n", "\n", "for d in Days:\n", " for p in Periods:\n", " solver.Add(x[6,1,d,p,c6] == x[6,2,d,p,c6])\n", " solver.Add(x[6,2,d,p,c6] == x[6,3,d,p,c6])\n", " solver.Add(x[6,3,d,p,c6] == x[6,4,d,p,c6])\n", " solver.Add(x[7,1,d,p,c7] == x[7,2,d,p,c7])\n", " solver.Add(x[7,2,d,p,c7] == x[7,3,d,p,c7])\n", " solver.Add(x[7,3,d,p,c7] == x[7,4,d,p,c7])\n", " solver.Add(x[8,1,d,p,c8] == x[8,2,d,p,c8])\n", " solver.Add(x[8,2,d,p,c8] == x[8,3,d,p,c8])\n", " solver.Add(x[8,3,d,p,c8] == x[8,4,d,p,c8])\n", " \n", " \n", "# CONSTRAINT 28: Ensure Brambley off Tuesday afternoon\n", "for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == 'Brambley':\n", " solver.Add(x[g,s,2,5,c]+x[g,s,2,6,c]+x[g,s,2,7,c] == 0)\n", " \n", " \n", "# CONSTRAINT 29: Catherine Cade off on Thursday (fix one day of the week when she is off)\n", "for g in Grades:\n", " for s in Sections:\n", " for c in Courses:\n", " if GSCTeacher[g][s][c] == 'Cade':\n", " solver.Add(sum(x[g,s,4,p,c] for p in Periods) == 0)\n", " \n", "\n", " \n", "# CONSTRAINT 30: Core courses (Humanities, French, Math, Science) must have certain \n", "# splits between AM and PM classes.\n", "# 9 lessons must be 5-4 or 6-3 or 7-2 (Humanities, Math/Science)\n", "# 8 lessons must be 5-3 or 6-2 (Humanities)\n", "# 5 lessons must be 3-2 or 4-1 (Grade 8 Math)\n", "# 3 lessons must be 2-1 or 1-2 (French, Science)\n", "\n", "for s in Sections:\n", " for g in Grades:\n", " c = AllCourses.index('Humanities')\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [1,2,3,4]) >= 5)\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [5,6,7]) >= 2)\n", " for g in [6,7]:\n", " c = AllCourses.index('Math/Science')\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [1,2,3,4]) >= 5)\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [5,6,7]) >= 2)\n", " for g in [8]:\n", " c = AllCourses.index('Math')\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [1,2,3,4]) >= 3)\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [5,6,7]) >= 1)\n", " for g in [6,7]:\n", " c = AllCourses.index('French')\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [1,2,3,4]) >= 1)\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [5,6,7]) >= 1)\n", " for g in [8]:\n", " c = AllCourses.index('MFA')\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [1,2,3,4]) >= 2)\n", " solver.Add(sum(x[g,s,d,p,c] for d in Days for p in [5,6,7]) >= 2)\n", " \n", " \n", "# CONSTRAINT 31: Aim for balanced schedules whenever possible: DeMerchant should have at most 3 Math/Science\n", "# classes on Wednesday due to XPE being on Wednesday.\n", "\n", "c1 = AllCourses.index('Math')\n", "c2 = AllCourses.index('Science')\n", "solver.Add(sum(x[8,1,3,p,c1]+x[8,2,3,p,c1]+x[8,1,3,p,c2]+x[8,2,3,p,c2] for p in Periods) <= 3)\n", "\n", "\n", "# CONSTRAINT 32: Aim for balanced schedules whenever possible: ensure Pike does not teach more than 5 lessons\n", "# in any day\n", "\n", "Tset = [[8,1,16]]\n", "for g in Grades:\n", " for s in Sections:\n", " for c in Courses: \n", " if GSCTeacher[g][s][c] == 'Pike':\n", " GradeSectionCourse = [g, s, c]\n", " Tset.append(GradeSectionCourse)\n", "for d in Days:\n", " solver.Add(sum(x[Tset[z][0],Tset[z][1],d,p,Tset[z][2]] \n", " for p in Periods for z in range(len(Tset))) <= 5)\n", " \n", " \n", "# CONSTRAINT 33: Students cannot have French on three consecutive days.\n", "c = AllCourses.index('French')\n", "for g in Grades:\n", " for s in Sections:\n", " for d in [1,2,3]:\n", " solver.Add(sum(x[g,s,d,p,c] + x[g,s,d+1,p,c] + x[g,s,d+2,p,c] for p in Periods) <= 2)\n", " \n", " \n", "# CONSTRAINT 34: Aim for balanced schedules whenever possible: Enns should have at most 6\n", "# classes on Wednesday due to XPE being on Wednesday. (It's impossible for him to have only 5)\n", "\n", "c6 = AllCourses.index('MP')\n", "c7 = AllCourses.index('MAA')\n", "c8 = AllCourses.index('MFA')\n", "solver.Add(sum(x[6,1,3,p,c6]+x[7,1,3,p,c7]+x[8,1,3,p,c8] for p in Periods) <= 4)\n", "\n", "\n", "# CONSTRAINT 35: Aim for balanced schedules whenever possible: Hollingworth should have at most 5\n", "# classes on any day.\n", "\n", "Tset = [[7,1,8],[6,1,8],[6,1,7]]\n", "for g in Grades:\n", " for s in Sections:\n", " for c in Courses: \n", " if GSCTeacher[g][s][c] == 'Hollingworth':\n", " GradeSectionCourse = [g, s, c]\n", " Tset.append(GradeSectionCourse)\n", "for d in Days:\n", " solver.Add(sum(x[Tset[z][0],Tset[z][1],d,p,Tset[z][2]] \n", " for p in Periods for z in range(len(Tset))) <= 5)\n", " \n", " \n", " \n", " \n", "# RUN OPTIMIZATION\n", "\n", "solver.Maximize(solver.Sum(x[g,s,d,p,c] for g in Grades for s in Sections for d in Days\n", " for p in Periods for c in Courses))\n", "sol = solver.Solve()\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "CohortNames = [\"-\", \"A\", \"B\", \"C\", \"D\"]\n", "OurColumns = [\"Period\", \"Monday\", \"Tuesday\", \"Wednesday\", \"Thursday\", \"Friday\"]\n", "\n", "for g in Grades:\n", " for s in Sections:\n", " for c in [AllCourses.index('XPE'), AllCourses.index('OPTION'), AllCourses.index('XPLO'),\n", " AllCourses.index('MFA'), AllCourses.index('MP'), AllCourses.index('MAA')]:\n", " GSCTeacher[g][s][c] = 'Multiple Teachers'\n", " \n", " \n", "Timetable = [ [ \"-\" for d in range(6)] for z in range(28)]\n", "for z in range(28):\n", " Timetable[z][0] = \"P\" + str(1+int(z/4))\n", "for d in Days:\n", " for p in Periods:\n", " for s in Sections:\n", " for c in Courses:\n", " if x[6,s,d,p,c].solution_value()==1:\n", " CourseID = str(6) + CohortNames[s] + \"-\" + AllCourses[c]\n", " if AllCourses[c] in [\"XPE\", \"XPLO\", \"Chapel\", \"Assembly\", \"MP\"]:\n", " CourseID = str(6) + \"E\" + \"-\" + AllCourses[c]\n", " TeacherID = \" (\" + GSCTeacher[6][s][c] + \")\"\n", " RowIndex = 4*(p-1)+(s-1) \n", " Timetable[RowIndex][d] = CourseID + TeacherID\n", "Grade6 = pd.DataFrame(Timetable, columns=OurColumns)\n", "\n", "Timetable = [ [ \"-\" for d in range(6)] for z in range(28)]\n", "for z in range(28):\n", " Timetable[z][0] = \"P\" + str(1+int(z/4))\n", "for d in Days:\n", " for p in Periods:\n", " for s in Sections:\n", " for c in Courses:\n", " if x[7,s,d,p,c].solution_value()==1:\n", " CourseID = str(7) + CohortNames[s] + \"-\" + AllCourses[c]\n", " if AllCourses[c] in [\"XPE\", \"XPLO\", \"Chapel\", \"Assembly\", \"OPTION\", \"MAA\"]:\n", " CourseID = str(7) + \"E\" + \"-\" + AllCourses[c]\n", " TeacherID = \" (\" + GSCTeacher[7][s][c] + \")\"\n", " RowIndex = 4*(p-1)+(s-1) \n", " Timetable[RowIndex][d] = CourseID + TeacherID\n", "Grade7 = pd.DataFrame(Timetable, columns=OurColumns)\n", "\n", "Timetable = [ [ \"-\" for d in range(6)] for z in range(28)]\n", "for z in range(28):\n", " Timetable[z][0] = \"P\" + str(1+int(z/4))\n", "for d in Days:\n", " for p in Periods:\n", " for s in Sections:\n", " for c in Courses:\n", " if x[8,s,d,p,c].solution_value()==1:\n", " CourseID = str(8) + CohortNames[s] + \"-\" + AllCourses[c]\n", " if AllCourses[c] in [\"XPE\", \"XPLO\", \"Chapel\", \"Assembly\", \"OPTION\", \"MFA\"]:\n", " CourseID = str(8) + \"E\" + \"-\" + AllCourses[c]\n", " TeacherID = \" (\" + GSCTeacher[8][s][c] + \")\"\n", " RowIndex = 4*(p-1)+(s-1) \n", " Timetable[RowIndex][d] = CourseID + TeacherID\n", "Grade8 = pd.DataFrame(Timetable, columns=OurColumns)\n", "\n", "with pd.ExcelWriter('Optimal Middle School Timetable by Grade.xlsx') as writer: \n", " Grade6.to_excel(writer, sheet_name='Grade6', index=False)\n", " Grade7.to_excel(writer, sheet_name='Grade7', index=False)\n", " Grade8.to_excel(writer, sheet_name='Grade8', index=False)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "AllTeachers.sort()\n", "\n", "CohortNames = [\"-\", \"A\", \"B\", \"C\", \"D\"]\n", "OurColumns = [\"Period\"] + AllTeachers\n", "\n", "for d in Days:\n", " Timetable = [ [ \"-\" for t in range(len(AllTeachers)+1)] for z in range(7)]\n", " for z in range(7):\n", " Timetable[z][0] = \"P\" + str(1+z)\n", " for g in Grades:\n", " for s in Sections:\n", " for p in Periods:\n", " for c in Courses:\n", " if x[g,s,d,p,c].solution_value()==1:\n", " CourseID = str(g) + CohortNames[s] + \"-\" + AllCourses[c]\n", " TeacherID = GSCTeacher[g][s][c]\n", " if TeacherID != 'Not Applicable' and TeacherID != 'Multiple Teachers':\n", " t = AllTeachers.index(TeacherID)\n", " Timetable[p-1][t+1] = CourseID\n", " if TeacherID == 'Multiple Teachers':\n", " if AllCourses[c] == 'OPTION' and g==7:\n", " for Teacher in ['Floyd', 'Zhang', 'Cunningham', 'Kuklinski', 'Bailey', 'Haydock']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID\n", " if AllCourses[c] == 'OPTION' and g==8:\n", " for Teacher in ['Floyd', 'Zhang', 'Cunningham', 'Kuklinski', 'Williams', 'Haydock']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID\n", " if AllCourses[c] == 'XPE' and g==6:\n", " for Teacher in ['Cunningham', 'Hollingworth', 'Kuklinski', 'Bell']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID\n", " if AllCourses[c] == 'XPE' and g==7:\n", " for Teacher in ['Cunningham', 'Hollingworth', 'Kuklinski', 'Danskin']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID\n", " if AllCourses[c] == 'XPE' and g==8:\n", " for Teacher in ['Kim', 'DeMerchant', 'Enns', 'Cunningham', 'Kuklinski', 'Floyd', 'Cade']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID \n", " if AllCourses[c] == 'MP' and g==6:\n", " for Teacher in ['Enns', 'Smith', 'Cunningham', 'Kuklinski', 'Hollingworth']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID \n", " if AllCourses[c] == 'MAA' and g==7:\n", " for Teacher in ['Enns', 'Smith', 'Kim', 'Wilkins']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID \n", " if AllCourses[c] == 'MFA' and g==8:\n", " for Teacher in ['Enns', 'Smith', 'Floyd', 'Marti', 'Pike']:\n", " CourseID = str(g) + 'E' + \"-\" + AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID \n", " if AllCourses[c] == 'XPLO':\n", " for Teacher in ['Frater', 'Enns', 'Wilkins', 'Zhang', 'Pike', 'Hollingworth',\n", " 'Marti', 'Cunningham', 'Floyd', 'Stark', 'Williams', 'Harris',\n", " 'Gains', 'DeMerchant', 'Cade', 'Weckend', 'Bailey', 'Donatelli']:\n", " CourseID = AllCourses[c]\n", " t = AllTeachers.index(Teacher)\n", " Timetable[p-1][t+1] = CourseID \n", " \n", " \n", " \n", " if d==1: Day1 = pd.DataFrame(Timetable, columns=OurColumns)\n", " if d==2: Day2 = pd.DataFrame(Timetable, columns=OurColumns)\n", " if d==3: Day3 = pd.DataFrame(Timetable, columns=OurColumns)\n", " if d==4: Day4 = pd.DataFrame(Timetable, columns=OurColumns)\n", " if d==5: Day5 = pd.DataFrame(Timetable, columns=OurColumns)\n", "\n", "with pd.ExcelWriter('Optimal Middle School Timetable by Teacher.xlsx') as writer: \n", " Day1.to_excel(writer, sheet_name='Day1', index=False)\n", " Day2.to_excel(writer, sheet_name='Day2', index=False)\n", " Day3.to_excel(writer, sheet_name='Day3', index=False)\n", " Day4.to_excel(writer, sheet_name='Day4', index=False)\n", " Day5.to_excel(writer, sheet_name='Day5', index=False) " ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Daily Lessons for Bailey is [2, 0, 0, 2, 1] with a total of 5\n", "Daily Lessons for Bell is [4, 3, 4, 3, 4] with a total of 18\n", "Daily Lessons for Brambley is [1, 1, 1, 2, 0] with a total of 5\n", "Daily Lessons for Cade is [4, 1, 4, 0, 3] with a total of 12\n", "Daily Lessons for Cunningham is [3, 4, 5, 4, 4] with a total of 20\n", "Daily Lessons for Danskin is [4, 3, 5, 4, 4] with a total of 20\n", "Daily Lessons for DeMerchant is [4, 3, 5, 5, 2] with a total of 19\n", "Daily Lessons for Donatelli is [4, 4, 4, 4, 3] with a total of 19\n", "Daily Lessons for Enns is [2, 4, 6, 4, 2] with a total of 18\n", "Daily Lessons for Floyd is [4, 2, 3, 4, 4] with a total of 17\n", "Daily Lessons for Frater is [2, 4, 0, 3, 4] with a total of 13\n", "Daily Lessons for Gains is [4, 3, 4, 3, 5] with a total of 19\n", "Daily Lessons for Harris is [2, 1, 2, 2, 3] with a total of 10\n", "Daily Lessons for Haydock is [2, 2, 0, 2, 2] with a total of 8\n", "Daily Lessons for Hollingworth is [3, 3, 5, 4, 4] with a total of 19\n", "Daily Lessons for Jackson is [4, 4, 4, 4, 2] with a total of 18\n", "Daily Lessons for Kim is [2, 2, 5, 3, 0] with a total of 12\n", "Daily Lessons for Kuklinski is [3, 4, 5, 4, 3] with a total of 19\n", "Daily Lessons for Lee is [4, 2, 3, 3, 4] with a total of 16\n", "Daily Lessons for Marti is [5, 2, 4, 4, 4] with a total of 19\n", "Daily Lessons for Pike is [5, 1, 4, 4, 5] with a total of 19\n", "Daily Lessons for Smith is [2, 4, 4, 4, 1] with a total of 15\n", "Daily Lessons for Stark is [4, 4, 4, 3, 4] with a total of 19\n", "Daily Lessons for Vachon is [2, 2, 2, 2, 1] with a total of 9\n", "Daily Lessons for Weckend is [2, 2, 1, 2, 3] with a total of 10\n", "Daily Lessons for Wilkins is [4, 4, 3, 4, 2] with a total of 17\n", "Daily Lessons for Williams is [4, 6, 4, 4, 5] with a total of 23\n", "Daily Lessons for Zhang is [4, 3, 2, 4, 4] with a total of 17\n" ] } ], "source": [ "# Print list of lessons per day, for each teacher. \n", "# Note that some of these numbers are inflated since not every teach (e.g. Smith, Williams) teaches every\n", "# MFA/MP/MAA block or every OPTION block.\n", "\n", "for Teacher in AllTeachers:\n", " count=[7,7,7,7,7]\n", " for p in range(7):\n", " if Day1[Teacher][p] == '-': count[0]-=1\n", " if Day2[Teacher][p] == '-': count[1]-=1\n", " if Day3[Teacher][p] == '-': count[2]-=1\n", " if Day4[Teacher][p] == '-': count[3]-=1\n", " if Day5[Teacher][p] == '-': count[4]-=1\n", " print(\"Daily Lessons for\", Teacher, \"is\", count, \"with a total of\", count[0]+count[1]+count[2]+count[3]+count[4])" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Optimization Complete with Total Happiness Score of 420\n", "The complete timetabling algorithm ran in 69.4 seconds\n" ] } ], "source": [ "print(\"\")\n", "print('Optimization Complete with Total Happiness Score of', round(solver.Objective().Value()))\n", "\n", "# compute runtime\n", "solving_time = time.time() - start_time\n", "\n", "print('The complete timetabling algorithm ran in', round(solving_time,1), 'seconds')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }