sat solver for school scheduling problem
1,688 views
Skip to first unread message
Sebastian Yonekura Baeza
Jan 8, 2018, 5:00:32 PM1/8/18
to or-tools-discuss
Hi, thanks for developing this great tool!
I'm trying to solve a school scheduling problem using the SAT solver. Since is similar to the nurse scheduling problem (https://github.com/google/or-tools/blob/master/examples/python/nurses_sat.py) I used a similar approach, but I'm having some trouble with a constraint, I would like to ask you for your guidance since i've been stuck for a while now.
In this problem I have courses, subjects, teachers and timeslots. , A course is made of a level (first grade, second grade, etc) and a section (A, B), for example 1°A, 1°B, 2°A, ...., subjects are Math, English, History, etc, We have t Teachers, each one with some skills that allow them to teach some subjects and the timeslots are when the subjects are taught. Also, every level contains a curriculum, that is the quantity of timeslots per subject required, for example all the first grades need to have 5 timeslots of english, 3 of math, and so on.
So we have some restrictions:
+ A teacher cannot teach more than 1 class simultaneosly
+ A teacher can only teach subjects of his/her set of skills (specialties)
+ Each course must meet the quantity of classes speicfied in the curriculum
+ Each teacher has a maximum number of working hours (here hours == timeslots)
- For a given course and subject, the teacher must be the same for all of them (ex: 1°A has only one Math teacher)
I modeled the problem as a big boolean matrix: assign[c, s, t, ts] = 1 if teacher t is assigned to course c and subject s in timeslot ts, and I've been able to add all the constraints but the last one.
Here is what I did for the last constraint:
# Teacher makes all the classes of a subject's course
for level in range(self.num_levels):
for section in range(self.num_sections):
for subject in range(self.num_subjects):
sums = []
subject_slots = self.problem.curriculum[self.problem.levels[level], self.problem.subjects[subject]]
for t in range(self.num_teachers):
course = level * self.num_sections + section
sum_expr = sum([self.assignment[course, subject, t, slot] for slot in range(self.num_slots)])
sums.append(sum_expr)
self.model.Add(subject_slots == max(sums))
the problem is that with that constraint the solver doesn't find any solution. I tried to change that for things like (sum_expr == subject_slots OR sum_expr == 0) without success. I guess there is some better way to model this, could someone help me with that?
Thanks!
Laurent Perron
Jan 9, 2018, 7:46:38 AM1/9/18
to or-tools-discuss
I am surprised you are not using the number of days.
You need 20+ slots, and have 4 * 3 available slots if you do not use the days.
--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Sebastian Yonekura Baeza
Jan 9, 2018, 8:44:09 AM1/9/18
to or-tools-discuss
Hi Laurent,
I'm not sure about that, the number of slots are num_slots = working_days * periods. Also, I need 8 slots per course, and the lectures across courses can be teached simultaneosly (for example 1°A with Math at Monday 08:00-09:30 and 2°A with English at Monday 08:00-09:30), is the teacher who cannot be the same.
I added more timeslots to see if that makes the problem 'feasible' although I think it already is, and still doesn't find solutions.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
Laurent Perron
Jan 9, 2018, 8:48:10 AM1/9/18
to or-tools-discuss
Sorry, I misread your code.
I will look at it.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
Laurent Perron
Jan 9, 2018, 8:52:34 AM1/9/18
to or-tools-discuss
Quick note:
self.courses = [x + y for x in problem.levels for y in problem.sections]
should be something like x * problem.num_levels + y ...
Laurent Perron
Jan 9, 2018, 9:38:57 AM1/9/18
to or-tools-discuss
Here is a working version:
I had to simplify the code to make it work on python 2.7. (remove ->, f' ', super()).
The main problem is that max() is not interpreted as a sat constraint. So I created intermediate sat variables to indicate if a teacher was assigned a given lecture.
from ortools.sat.python import cp_model
class SchoolSchedulingProblem(object):
def __init__(self, subjects, teachers, curriculum, specialties, working_days,
periods, levels, sections, teacher_work_hours):
self.subjects = subjects
self.teachers = teachers
self.curriculum = curriculum
self.specialties = specialties
self.working_days = working_days
self.periods = periods
self.levels = levels
self.sections = sections
self.teacher_work_hours = teacher_work_hours
class SchoolSchedulingSatSolver(object):
def __init__(self, problem):
# Problem
self.problem = problem
# Utilities
self.timeslots = [
'{0:10} {1:6}'.format(x, y)
for x in problem.working_days
for y in problem.periods
]
self.num_days = len(problem.working_days)
self.num_periods = len(problem.periods)
self.num_slots = len(self.timeslots)
self.num_teachers = len(problem.teachers)
self.num_subjects = len(problem.subjects)
self.num_levels = len(problem.levels)
self.num_sections = len(problem.sections)
self.courses = [
x * self.num_levels + y
for x in problem.levels
for y in problem.sections
]
self.num_courses = self.num_levels * self.num_sections
all_courses = range(self.num_courses)
all_teachers = range(self.num_teachers)
all_slots = range(self.num_slots)
all_sections = range(self.num_sections)
all_subjects = range(self.num_subjects)
all_levels = range(self.num_levels)
self.model = cp_model.CpModel()
self.assignment = {}
for c in all_courses:
for s in all_subjects:
for t in all_teachers:
for slot in all_slots:
if t in self.problem.specialties[s]:
name = 'C:{%i} S:{%i} T:{%i} Slot:{%i}' % (c, s, t, slot)
self.assignment[c, s, t, slot] = self.model.NewBoolVar(name)
else:
name = 'NO DISP C:{%i} S:{%i} T:{%i} Slot:{%i}' % (c, s, t, slot)
self.assignment[c, s, t, slot] = self.model.NewIntVar(0, 0, name)
# Constraints
# Each course must have the quantity of classes specified in the curriculum
for level in all_levels:
for section in all_sections:
course = level * self.num_sections + section
for subject in all_subjects:
required_slots = self.problem.curriculum[self.problem.levels[
level], self.problem.subjects[subject]]
self.model.Add(
sum(self.assignment[course, subject, teacher, slot]
for slot in all_slots
for teacher in all_teachers) == required_slots)
# Teacher can do at most one class at a time
for teacher in all_teachers:
for slot in all_slots:
self.model.Add(
sum([
self.assignment[c, s, teacher, slot]
for c in all_courses
for s in all_subjects
]) <= 1)
# Maximum work hours for each teacher
for teacher in all_teachers:
self.model.Add(
sum([
self.assignment[c, s, teacher, slot]
for c in all_courses for s in all_subjects for slot in all_slots
]) <= self.problem.teacher_work_hours[teacher])
# Teacher makes all the classes of a subject's course
teacher_courses = {}
for level in all_levels:
for section in all_sections:
course = level * self.num_sections + section
for subject in all_subjects:
for t in all_teachers:
name = 'C:{%i} S:{%i} T:{%i}' % (course, subject, teacher)
teacher_courses[course, subject, t] = self.model.NewBoolVar(name)
temp_array = [
self.assignment[course, subject, t, slot] for slot in all_slots
]
self.model.AddMaxEquality(teacher_courses[course, subject, t],
temp_array)
self.model.Add(
sum(teacher_courses[course, subject, t]
for t in all_teachers) == 1)
# Solution collector
self.collector = None
def solve(self):
print('Solving')
solver = cp_model.CpSolver()
solution_printer = SchoolSchedulingSatSolutionPrinter()
status = solver.SearchForAllSolutions(self.model, solution_printer)
print()
print('Branches', solver.NumBranches())
print('Conflicts', solver.NumConflicts())
print('WallTime', solver.WallTime())
def print_status(self):
pass
class SchoolSchedulingSatSolutionPrinter(cp_model.CpSolverSolutionCallback):
def NewSolution(self):
print('Found Solution!')
def main():
# DATA
subjects = ['English', 'Math', 'History']
levels = ['1-', '2-', '3-']
sections = ['A']
teachers = ['Mario', 'Elvis', 'Donald', 'Ian']
teachers_work_hours = [18, 12, 12, 18]
working_days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']
periods = ['08:00-09:30', '09:45-11:15', '11:30-13:00']
curriculum = {
('1-', 'English'): 3,
('1-', 'Math'): 3,
('1-', 'History'): 2,
('2-', 'English'): 4,
('2-', 'Math'): 2,
('2-', 'History'): 2,
('3-', 'English'): 2,
('3-', 'Math'): 4,
('3-', 'History'): 2
}
# Subject -> List of teachers who can teach it
specialties_idx_inverse = [
[1, 3], # English -> Elvis & Ian
[0, 3], # Math -> Mario & Ian
[2, 3] # History -> Donald & Ian
]
problem = SchoolSchedulingProblem(
subjects, teachers, curriculum, specialties_idx_inverse, working_days,
periods, levels, sections, teachers_work_hours)
solver = SchoolSchedulingSatSolver(problem)
solver.solve()
solver.print_status()
if __name__ == '__main__':
main()
Sebastian Yonekura Baeza
Jan 9, 2018, 10:10:35 AM1/9/18
to or-tools...@googlegroups.com
So the trick was to add a MaxEquality between this new variable and the assignment and Sum = 1 for the new variable across all teachers, thank you so much!
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/-ox5tJDOIOc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
Saludos,
Sebastián
Laurent Perron
Jan 9, 2018, 10:19:40 AM1/9/18
to or-tools-discuss
Yes.
2018-01-09 16:10 GMT+01:00 Sebastian Yonekura Baeza <sebastian...@gmail.com>:
So the trick was to add a MaxEquality between this new variable and the assignment and Sum = 1 for the new variable across all teachers, thank you so much!
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/-ox5tJDOIOc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--Saludos,Sebastián--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
Bill Zhong
Apr 4, 2018, 4:04:03 PM4/4/18
to or-tools-discuss
Is it same one at github?
I only get infinite "Found Solution!" print out. Any change you can post an actual working version?
Thanks.
Reply all
Reply to author
Forward
0 new messages