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