Solving Scheduling Problems with Tree Search
Machine learning is quite the rage these days, so much it is easy to lose sight of the fact there are other algorithms in the “AI” space. As a matter of fact, these algorithms can be so crucial that it can be neglectful to overlook them.
Video version of this article
Imagine you needed to schedule classes and classrooms. There are 36 periods, 36 rooms, and 800 lectures as your dimensions to schedule against. Want to take a guess how many possible configurations there are? Here is the answer: 1⁰²⁴⁹⁰ possible configurations. To put it in perspective, there are 1⁰⁸⁰ observable atoms in the universe. Even a task as mundane as classroom scheduling deals with astronomical numbers and permutations, and ventures into NP Hard territory. But I can show you how to algorithmically solve these problems in a (usually) timely manner.
The field of operations research is not new, but its techniques and algorithms are vital to practical everyday problems. How do you maximize profit across several product lines with only so much factory capacity? How do you schedule 200 nurses in a hospital with different vacation requests, seniorities, union restrictions, and work hour regulations? What if you need to schedule sports tournaments and minimize team travel distances? How about optimizing the on-time performance of a train network? Or simply solving a Sudoku?
There are many algorithms out there to solve problems with an optimization nature. These include linear programming, metaheuristics, and integer programming just to name a few. I personally find these optimization and search algorithms quite fascinating, and there is an enormous number of practical problems to solve with them. It is also interesting how some of these algorithms apply directly to machine learning, as machine learning itself is an optimization problem at its core.
But today, I want to talk about how to schedule university classes against classrooms, as well as solving Sudokus. You can use this integer programming methodology to schedule staff, factory lines, cloud server jobs, transportation vehicles, and other resources under rule-based constraints. Rather than relying on iterative brute-force tactics to fit events into a schedule (which can be hopelessly inefficient), we can achieve magic one-click generation of a schedule using mathematical modeling. You can even adapt these approaches to build chess AI algorithms or do any discrete-based regression.
Before I start, I highly recommend this challenging but useful Coursera class on discrete optimization. This class is fairly ambitious but rewarding, useful, and fun. It is worth the time and energy, even if you have to pace yourself slowly.
Brace yourself, there is going to be quite a bit of code for you technical folks! It is important to keep your sights on the big picture and understand the model conceptually. So I encourage you to gloss over the code (or skip it altogether) the first time you read this. If you do decide to deep-dive, be sure you are familiar with object-oriented and functional programming.
Defining the Problem
In this article, we will generate a weekly university schedule against one classroom. We will plot the occupation state grid on two dimensions: classes vs a timeline of 15-minute discrete intervals. If we wanted to schedule against multiple rooms, that would be three dimensions: classes vs timeline vs room. We will stick with the former for now and do one room, and I will explain how you can do multiple rooms later.
These classes have differing lengths and may “recur” throughout the week. Each recurring session must start at the same time of day.
Here are the classes:
- Psych 101 (1 hour, 2 sessions/week)
- English 101 (1.5 hours, 2 sessions/week)
- Math 300 (1.5 hours, 2 sessions/week)
- Psych 300 (3 hours, 1 session/week)
- Calculus I (2 hours, 2 sessions/week)
- Linear Algebra I (2 hours, 3 sessions/week)
- Sociology 101 (1 hour, 2 sessions/week)
- Biology 101 (1 hour, 2 sessions/week)
- Supply Chain 300 (2.5 hours, 2 sessions/week)
- Orientation 101 (1 hour, 1 session/week)
The day should be broken up in discrete 15 minute increments, and classes can only be scheduled on those increments. In other words, a class can only start on the :00, :15, :30, or :45 of the hour.
The operating week is Monday through Friday. The operating day is as follows with a break from 11:30AM to 1:00PM:
- 8:00AM-11:30AM
- 1:00PM-5:00PM
YOUR OBJECTIVE: create a model that schedules these classes with no overlap and complies with these requirements.
SPOILER ALERT: Here is the solution we are ultimately going to calculate using an “AI” algorithm we build from scratch. If you want to learn how this is done, please keep reading.
SPOIILER ALERT: Here is the schedule our algorithm will build by the end of this article
Laying the Groundwork
Alright, overwhelmed yet? That’s a lot of rules and the number of permutations to explore is astronomical. But once I show you this technique, it will hopefully be pretty straight forward to implement.
The very first thing you should notice about this problem is how everything is broken up into “15 minute” blocks. This is not a continuous/linear problem but rather a discrete one, which is how most schedules are built in the real world. Imagine that we have created a timeline for the entire week broken up in 15 minute blocks, like this:
Note that the “…” is just a collapsed placeholder since we do not have enough room to display the 672 blocks for the week (672 = 7 days * 24 hours * 4 blocks in an hour).
Now let’s expand this concept and make the classes an axis against the timeline. Each intersection/cell is a Slot that can be 1 or 0. This binary variable will be solved to indicate whether or not that Slot is the start time for the first recurrence of that class. We will set them all to 0 for now as shown below:
A grid of our decision variables
This grid is crucial to thinking about this problem logically. It will make an effective visual aid because our constraints will focus on regions within the grid.
I am going to use Kotlin as the programming language, which works perfectly with Java libraries but is much more readable and concise than Java.We are going to take advantage of Java 8’s great LocalDate/LocalTime API to make our calendar work easier.
If you are not familiar with Kotlin, it is basically a “dumbed down Scala” similar to Swift, and used heavily for Android development. It essentially takes the practical features of Java, C#, Scala, Groovy, and Python to create a pragmatic industrial language. It also compiles to Java bytecode and interops with Java libraries seamlessly.
Let’s set up our basic rule parameters like so:
import java.time.LocalDateimport java.time.LocalTime
_// Any Monday through Friday date range will work_val operatingDates =LocalDate.of(2017,10,16)..LocalDate.of(2017,10,20)
val operatingDay = LocalTime.of(8,0)..LocalTime.of(17,0)
val breaks = listOf<ClosedRange<LocalTime>>(LocalTime.of(11,30)..LocalTime.of(12,59))
Next let’s declare the ScheduledClass which holds the properties of a given class we want to schedule.
data class ScheduledClass(val id: Int,val name: String,val hoursLength: Double,val recurrences: Int,val recurrenceGapDays: Int = 2)
The recurrenceGapDays is the minimum number of days needed between each recurrence’s start time. For instance, take Psych 100 which requires 2 repetitions and defaults to a 2-day gap. If the first class was on a MONDAY at 8AM, then the second repetition must be scheduled exactly 2 days (48 hours) later, which is WEDNESDAY at 8AM. We will default this value to 2, which will put 48 hours between the start of each session.
Next we can declare all the ScheduledClass instances in a List:
val scheduledClasses = listOf(ScheduledClass(id=1,name="Psych 101",hoursLength=1.0,recurrences=2),ScheduledClass(id=2,name="English 101",hoursLength=1.5,recurrences=3),ScheduledClass(id=3,name="Math 300",hoursLength=1.5,recurrences=2),ScheduledClass(id=4,name="Psych 300",hoursLength=3.0,recurrences=1),ScheduledClass(id=5,name="Calculus I",hoursLength=2.0,recurrences=2),ScheduledClass(id=6,name="Linear Algebra I",hoursLength=2.0,recurrences=3),ScheduledClass(id=7,name="Sociology 101",hoursLength=1.0,recurrences=2),ScheduledClass(id=8,name="Biology 101",hoursLength=1.0,recurrences=2),ScheduledClass(id=9,name="Supply Chain 300",hoursLength=2.5,recurrences=2),ScheduledClass(id=10,name="Orientation 101",hoursLength=1.0,recurrences=1))
The Block class will represent each discrete 15-minute time period. We will use a Kotlin Sequence in combination with Java 8’s LocalDate/LocalTime API to generate all blocks for the entire planning window. We will also create a few helper properties to extract the timeRange as well as whether it is withinOperatingDay. The withinOperatingDay property will determine if this Block is within a schedulable window of time (e.g. not scheduled in the middle of the night or inside a break period).
_/** A discrete, 15-minute chunk of time a class can be scheduled on */_data class Block(val range: ClosedRange<LocalDateTime>) {
**val timeRange** \=
**range**.**start**.toLocalTime()..**range**.**endInclusive**.toLocalTime()
/** indicates if this block is in operating day/breakconstraints */ val withinOperatingDay get() =breaks.all { timeRange.start !in it } &&timeRange.start in operatingDay &&timeRange.endInclusive in operatingDay
_// manage instances_ **companion object** {
_/\*
All operating blocks for the entire week, broken up in 15
minute increments.
Lazily initialize to prevent circular construction issues
\*/_ **val all by** _lazy_ **{**
generateSequence(operatingDates.start.atStartOfDay()){dt -> dt.plusMinutes(15).takeIf { it.plusMinutes(15) <=operatingDates.endInclusive.atTime(23,59)}}.map { Block(it..it.plusMinutes(15)) } .toList()} /* only returns blocks within the operating times */ val allInOperatingDay by lazy {all.filter { it.withinOperatingDay }} }}
Note I am going to initialize items for each domain object using a [lazy { }](https://kotlinlang.org/docs/reference/delegated-properties.html#lazy) delegate. This is to prevent circular construction issues by not constructing the items until they are first called.
Finally, the Slot class will represent an intersection/cell between a ScheduledClass and a Block. We will generate all of them by pairing every ScheduledClass with every Block. We will also create an unassigned selected binary variable which will be null until we assign it a 1 or 0.
data class Slot(val block: Block,val scheduledClass: ScheduledClass) {
**var selected**: Int? = **null**
**companion object** {
**val all by** _lazy_ **{** Block.**all**._asSequence_()._flatMap_ **{** b **\->** ScheduledClass.**all**._asSequence_()._map_ **{** Slot(b,**it**)**}
}**._toList_()
**}** }
}
Modeling the Constraints
Before I go into the implementation of the model, I should emphasize you can use mixed integer solver libraries to model the constraints with linear functions and have it solve for the selected variables. In Python you can use PuLp or PyOmo. On the Java platform you can use ojAlgo or OptaPlanner. For many of these libraries, I could also drop in a $10K IBM CPLEX license which can execute a solve more quickly for larger, more complex problems.
But I’m going to show how to build a solution from scratch. The benefit of doing optimization without any libraries is you get a great deal of control over the heuristics (the search strategies) and expressing the model in terms of your domain.
Before we dive into solving for the selected variables in each Slot, let us do some thought experiments to understand our constraints. I probably wasted 50 sheets of papers coming up with models to do this, but I found something that works. It is a bit abstract, but powerful and effective for this particular problem.
Again, we are going to assign each Slot a 1 or 0 to indicate the start of the first class repetition. Here is one possible iteration our solver may come up with, where the first Psych 101 class starts on MON 9:00AM and Sociology 101 starts on MON 9:15AM. Here it is on our grid:
Study this scenario closely. Do you see why this is an invalid case? In the MON 9:45AM block, Psych 101 (which requires four blocks) and Sociology 101 (which also requires four blocks) are in conflict with each other. Visually, you might be able to see the conflict. But how do you describe it?
The sum of scheduled class slots that “affect” the 9:45AM block must be less than or equal to 1. A sum of 1 effectively means only one class is taking up that block, and 0 means no classes are occupying that block at all (also valid). The cases below are also failures because the sum of “affecting” slots is 2.
If we shifted Sociology 101 to 10:00AM, the sum would then be 1 and all is good (shown below):
We need to apply this logic to every block across the entire timeline, querying for earlier slots for each class that occupy this block, and dictate their sum must be no greater than 1. This abstract but powerful idea achieves everything we need constraint-wise. Here is what this looks like in practice below, where all slots affecting the 9:45AM block are highlighted in blue. All of these blue blocks must sum to no more than 1 for the 9:45AM block to not be double-booked.
This can even account for the recurrences too. After all, we put a 1 in a slot to indicate the candidate start time of the first class. If we were looking at the 9:45AM block on Friday, we would query for time slots earlier in the week that would result in this 9:45AM Friday block being occupied (all they way to Monday). Here is a wide visual below. The sum of these blue slots must be no greater than 1.
Okay is your head spinning yet? The power of this model is not so much the math, but the ability for each block to query the slots that impact it and mandate they must sum to no more than 1. That is where the hard work will happen. Another benefit is we do not have create any new variables just to model constraints, and can constrain the existing slot binary variables with a series of simple summation constraints.
Extracting Recurrences and Affected Slots
To execute this idea of affecting slots for a given block, what we need to do first is identify these slots for each class on a given block, and say they all must sum to “1”. The star of this codebase is going to be this Kotlin function against a given List of items:
enum class RecurrenceMode { PARTIAL_ONLY, FULL_ONLY, ALL }
fun List<T>.affectedWindows(slotsNeeded: Int,gap: Int,recurrences: Int,mode: RecurrenceMode = RecurrenceMode.FULL_ONLY) =
(0..size).asSequence().map { i -> (1..recurrences).asSequence().map { (it - 1) * gap } .filter { it + i < size } .map { r -> subList(i + r,(i + r + slotsNeeded).let { if (it > size) size else it })} .toList()}.filter {when (mode) {RecurrenceMode.ALL -> true
RecurrenceMode.FULL_ONLY ->it.size == recurrences &&it.all { it.size == slotsNeeded }
RecurrenceMode.PARTIAL_ONLY ->it.size < recurrences ||it.any { it.size < slotsNeeded } }}
I will let you dive deep into this function implementation on your own. For now it is more productive to cover what it accomplishes, which is take any List<Slot> and perform a specialized windowing operation that injects a gap between each recurrence. This will return a list of lists, List<List<T>>, where each list is a recurrence and the elements in it are the affected elements. Note the gap is the number of elements between each start of the window.
To get an idea of the pattern, we can take the integers 1 through 20 and break them up in groups of 4, with a gap of 6 between each recurrence start, and have 3 recurrences. We will only consider groups that are complete and not partial, so the mode will be set to RecurrenceMode.FULL_ONLY.
fun main(args: Array<String>) {
(1..20).toList().affectedWindows(slotsNeeded = 4,gap = 6,recurrences = 3,mode = RecurrenceMode.FULL_ONLY ).forEach { println(it) **}**}
OUTPUT:
[[1, 2, 3, 4], [7, 8, 9, 10], [13, 14, 15, 16]][[2, 3, 4, 5], [8, 9, 10, 11], [14, 15, 16, 17]][[3, 4, 5, 6], [9, 10, 11, 12], [15, 16, 17, 18]][[4, 5, 6, 7], [10, 11, 12, 13], [16, 17, 18, 19]][[5, 6, 7, 8], [11, 12, 13, 14], [17, 18, 19, 20]]
If we set the mode to RecurrenceMode.PARTIAL_ONLY, it will give us the “broken” groups that were unable to produce 3 recurrences all with a length of 4. This will be helpful later to identify slots that must be 0 because we cannot get all the required slots for a given block (e.g. they spill past the 5pm limit).
fun main(args: Array<String>) {(1..20).toList().affectedWindows(slotsNeeded = 4,gap = 6,recurrences = 3,mode = RecurrenceMode.PARTIAL_ONLY ).forEach { println(it) **}**}
OUTPUT:
[[6, 7, 8, 9], [12, 13, 14, 15], [18, 19, 20]][[7, 8, 9, 10], [13, 14, 15, 16], [19, 20]][[8, 9, 10, 11], [14, 15, 16, 17], [20]][[9, 10, 11, 12], [15, 16, 17, 18]][[10, 11, 12, 13], [16, 17, 18, 19]][[11, 12, 13, 14], [17, 18, 19, 20]][[12, 13, 14, 15], [18, 19, 20]][[13, 14, 15, 16], [19, 20]][[14, 15, 16, 17], [20]][[15, 16, 17, 18]][[16, 17, 18, 19]][[17, 18, 19, 20]][[18, 19, 20]][[19, 20]][[20]]
We can use this affectedWindows() function to handle the class repetitions, and generate all possible permutations within our time planning window Monday through Friday. We can then use that to find slots for a particular class that affect a particular block. We will also “zero out” slots that are part of broken groups. For example, starting Biology 101 at 4:15PM will result in it spilling past 5:00PM. Therefore, this slot should just be fixed to “0” and not even considered in our search which we will do later.
_/** A discrete, 15-minute chunk of time a class can be scheduled on */_data class Block(val range: ClosedRange<LocalDateTime>) {
**val timeRange** \=
**range**.**start**.toLocalTime()..**range**.**endInclusive**.toLocalTime()
/** indicates if this block is zeroed due to operatingday/break constraints */ val withinOperatingDay get() =breaks.all { timeRange.start !in it } &&timeRange.start in operatingDay &&timeRange.endInclusive in operatingDay
**val affectingSlots by** _lazy_ **{** ScheduledClass.**all**._asSequence_()
._flatMap_ **{
it**.affectingSlotsFor(**this**)._asSequence_()
**}**._toSet_()
**}**
**companion object** {
_/\*
All operating blocks for the entire week, broken up in 15
minute increments.
Lazily initialize to prevent circular construction issues
\*/_ **val all by** _lazy_ **{**
generateSequence(operatingDates.start.atStartOfDay()){dt -> dt.plusMinutes(15).takeIf { it.plusMinutes(15) <=operatingDates.endInclusive.atTime(23,59)}}.map { Block(it..it.plusMinutes(15)) } .toList()} /* only returns blocks within the operating times */ val allInOperatingDay by lazy {all.filter { it.withinOperatingDay }} }}
data class ScheduledClass(val id: Int,val name: String,val hoursLength: Double,val recurrences: Int,val recurrenceGapDays: Int = 2) {
_/\*\* the # of slots between each recurrence \*/_ **val gap** \= **recurrenceGapDays** \* 24 \* 4
_/\*\* the # of slots needed for a given occurrence \*/_ **val slotsNeededPerSession** \= (**hoursLength** \* 4).toInt()
_/\*\* yields slots for this given scheduled class \*/_ **val slots by** _lazy_ **{** Slot.**all**._asSequence_()
._filter_ **{ it**.**scheduledClass** \== **this }** ._toList_()
**}**
_/\*\* yields slot groups for this scheduled class \*/_ **val recurrenceSlots by** _lazy_ **{
slots**._affectedWindows_(slotsNeeded = **slotsNeededPerSession**,
gap = **gap**,
recurrences = **recurrences**,
mode = RecurrenceMode.**FULL\_ONLY** )._toList_()
**}**
_/\*\* yields slots that affect the given block for this
scheduled class \*/_ **fun** affectingSlotsFor(block: Block) =
**recurrenceSlots**._asSequence_()
._filter_ **{** blk **\->** blk._flatMap_ **{ it }** ._any_ **{ it**.**block** \== block **}
}** ._map_ **{ it**._first_()._first_() **}**
_/\*\* These slots should be fixed to zero \*\*/_ **val slotsFixedToZero by** _lazy_ **{** _// broken recurrences_ **slots**._affectedWindows_(slotsNeeded = **slotsNeededPerSession**,
gap = **gap**,
recurrences = **recurrences**,
mode = RecurrenceMode.**PARTIAL\_ONLY** ) ._flatMap_ **{ it**._asSequence_() **} //flatten the groups!** ._flatMap_ **{ it**._asSequence_() **}** ._plus_(
**recurrenceSlots**._asSequence_()
._flatMap_ **{ it**._asSequence_() **}** ._filter_ **{** slot **\->** slot._any_ **{** !**it**.**block**.**withinOperatingDay
}
}** ._map_ **{ it**._first_() **}** )
._distinct_()
._onEach_ **{
it**.**selected** \= 0
**}** ._toList_()
**}**
/**translates and returns the optimized start time of the class */ val start get() =slots.asSequence().filter { it.selected == 1 } .map { it.block.dateTimeRange.start } .min()!!
/** translates and returns the optimized end time of the class */ val end get() = start.plusMinutes((hoursLength * 60.0).toLong())
_/\*\* returns the DayOfWeeks where recurrences take place \*/_ **val daysOfWeek get**() = (0..(**recurrences**\-1))._asSequence_()
._map_ **{
start**._dayOfWeek_.plus(**it**.toLong() \* **recurrenceGapDays**)
**}**._sorted_()
**companion object** {
**val all by** _lazy_ **{** _scheduledClasses_ **}** }
}
Solving for the Variables
Now that we have an effective infrastructure set up to query out slots affecting a given block, we are now ready to solve for the variables that comply to our constraints. Hopefully you are fairly comfortable with writing recursive algorithms. If not, here is an opportunity to practice!
But first I am going to demonstrate this idea using a simpler and cleaner example: the Sudoku. It will demonstrate how to solve for variables using a branching algorithm before I circle back to the scheduling problem.
Consider the Sudoku
Hopefully Sudokus are a familiar puzzle game. You are provided a 9x9 grid of cells, where some cells already have possible numbers 1–9. You need to find values for the rest of the blank cells so that every row, column, and 3x3 square has the numbers 1–9.
A typical Sudoku puzzle
So how do you solve for the blank values? Brute-forcing this will be hopelessly inefficient, so we need a smarter search strategy.
Allow me to introduce you to tree search. It feels similar to decision trees but we are dealing with discrete variables (integers) and not continuous variables (decimals).
First take the cells and sort them in a list by the number of candidate values they have. For instance, cell[4,4] can only be one value, 5, so it goes first while cell[2,6] should be last since it has 6 possible values. Then create a function that recursively explores each possible value as a branching algorithm. Here is a visual of how this recursive algorithm explores possible values:
With this sorted list, create a recursive tree that explores each Sudoku cell and its possible values.
Notice how we start with the most constrained cells first, which greatly reduces our search space. This usage of a search strategy is known as a “heuristic”. The moment a given branch is deemed infeasible (breaking our Sudoku rules), that branch immediately terminates and moves on to the next alternative branch. Above, cell[4,2] cannot be assigned a “3” because cell[3,2] was already assigned a “3”. This would mean a “3” already exists in column 2, so there is no reason to continue searching that branch and we prune it.
The moment we find a branch that explored all 91 values and no constraints are broken, we have solved our Sudoku! We can then collapse the branch values back into the game board like so:
We have solved our Sudoku!
If you want to see the source code of the Sudoku solver, you can find it here. This part of the code is where the recursive tree happens.
thomasnield/kotlin-sudoku-solver_A suduko game solver written in Kotlin. Contribute to thomasnield/kotlin-sudoku-solver development by creating an…_github.com
Back to the Scheduling Problem
So what do Sudokus have to do with scheduling problem. Well, a lot actually! We can apply this very technique to solve our slots being 1 or 0 values by using a search tree. On every tip of a branch being explored, you can check to see if your constraints have still been met just like a Sudoku, making sure a class has not been scheduled over an already occupied time slot.
Conceptually, here is what our recursive search tree will look like:
Here is the how I can implement this beastly algorithm from scratch (please forgive my code formatting or just look at the source code). Note how I use BranchNode to represent the tip of a branch being searched and I can traverse backwards on the branch to evaluate if decisions made so far do not clash with my current one. I can then create a traverse() function to explore the entire tree recursively until a solution is found.
import java.time.DayOfWeek
class BranchNode(val selectedValue: Int,restOfTree: List<Slot>,val previous: BranchNode? = null) {
**val slot** \= restOfTree._first_()
**val traverseBackwards** \= _generateSequence_(**this**) **{
it**.**previous
}**._toList_()
_// calculate remaining slots and prune where constraint propagates_ **val remainingSlots by** _lazy_ **{
if** (**selectedValue** \== 0)
restOfTree._minus_(**slot**)
**else** {
_// if this slot is occupied, affected slots can be pruned_ **val** affectedSlotsPropogated = Block.**allInOperatingDay** ._asSequence_()._filter_ **{
slot in it**.**affectingSlots
}**._flatMap_ **{ it**.**affectingSlots**._asSequence_() **}** ._filter_ **{ it**.**selected** \== **null }** ._toSet_()
restOfTree._asSequence_()
._filter_ **{
it**.**scheduledClass** != **slot**.**scheduledClass** && **it !in** affectedSlotsPropogated
**}**._toList_()
}
**}
**
**val scheduleMet get**() = **traverseBackwards** ._asSequence_()
._filter_ **{ it**.**selectedValue** \== 1 **}** ._map_ **{ it**.**slot**.**scheduledClass }** ._distinct_()
._count_() == ScheduledClass.**all**._count_()
**val isContinuable get**() = !**scheduleMet** &&
**remainingSlots**._count_() > 0
val isSolution get() = scheduleMet
**fun** applySolution() {
**slot**.**selected** \= **selectedValue** }
}
fun executeBranchingSearch() {
_// pre-constraints_ ScheduledClass.**all**._flatMap_ **{ it**.**slotsFixedToZero }** ._forEach_ **{ it**.**selected** \= 0 **}**
_// Encourage most "constrained" slots to be searched first_ **val** sortedSlots = Slot.**all**._asSequence_()
._filter_ **{ it**.**selected** \== **null }**._sortedWith_(
_compareBy_(
**{** _// prioritize slots dealing with recurrences_ **val** dow = **it**.**block**.**range**.**start**._dayOfWeek_ **when** {
dow == DayOfWeek.**MONDAY** &&
**it**.**scheduledClass**.**recurrences** \== 3
-> -1000
dow != DayOfWeek.MONDAY &&it.scheduledClass.recurrences == 3-> 1000
dow in DayOfWeek.MONDAY..DayOfWeek.WEDNESDAY && it.scheduledClass.recurrences == 2-> -500
dow !in DayOfWeek.MONDAY..DayOfWeek.WEDNESDAY && it.scheduledClass.recurrences == 2-> 500
dow in DayOfWeek.THURSDAY..DayOfWeek.FRIDAY &&it.scheduledClass.recurrences == 1-> -300
dow !in DayOfWeek.THURSDAY..DayOfWeek.FRIDAY &&it.scheduledClass.recurrences == 1 -> 300
else -> 0}},
_// make search start at beginning of week_ { it.block.range.start },
// followed by class length {-it.scheduledClass.**slotsNeededPerSession } **)).toList()
_// this is a recursive function for exploring nodes
// in a branch-and-bound tree_ **fun** traverse(currentBranch: BranchNode? = **null**): BranchNode? {
**if** (currentBranch != **null** &&
currentBranch.**remainingSlots**.isEmpty()) {
**return** currentBranch
}
for (candidateValue in intArrayOf(1,0)) {val nextBranch = BranchNode(candidateValue,currentBranch?.remainingSlots?: sortedSlots,currentBranch)
**if** (nextBranch.isSolution)
**return** nextBranch
**if** (nextBranch.isContinuable) {
**val** terminalBranch = traverse(nextBranch)
**if** (terminalBranch?.isSolution == **true**) {
**return** terminalBranch
}
}
}
**return null** }
_// start with the first Slot and set it as the seed
// recursively traverse from the seed and get a solution_ **val** solution = traverse()
solution?.traverseBackwards?.forEach **{** it.applySolution() **}**?: **throw** Exception(**"Infeasible"**)
}
import java.time.LocalDateimport java.time.LocalTime
_// Any Monday through Friday date range will work_val operatingDates =LocalDate.of(2017,10,16)..LocalDate.of(2017,10,20)
val operatingDay = LocalTime.of(8,0)..LocalTime.of(17,0)
val breaks = listOf<ClosedRange<LocalTime>>(LocalTime.of(11,30)..LocalTime.of(12,59))
I also use a heuristic to search slots that are the “most constrained” first, meaning they are more likely to be assigned a “1”. For example, 3-recurrence classes must be scheduled on a MONDAY, so we should evaluate its slots on MONDAY first. The heuristic will also prioritize high-recurrence classes (like 3 and 2) to be searched first so we get them over with. After all, high recurrence classes do not have much flexibility and should be evaluated first.
Notice we also aggressively prune unexplored values “ahead” that we no longer have reason to search. For example, if my branch just assigned a “1” to a 9:30AM slot for Biology 101, I should prune all slots ahead for that 9:30AM block as well as Biology 101, as both have become occupied for this branch.
Now all I have left to do is call this recursive function and print the results!
fun main(args: Array<String>) {
_executeBranchingSearch_()
ScheduledClass.all.sortedBy { it.start } .forEach { println("${it.name}-${it.daysOfWeek.joinToString("/")}${it.start.toLocalTime()}-${it.end.toLocalTime()}")}}
If you set up your heuristics and parameters exactly like mine, here is the schedule it generates:
Linear Algebra I- MONDAY/WEDNESDAY/FRIDAY 08:00-10:00English 101- MONDAY/WEDNESDAY/FRIDAY 10:00-11:30Supply Chain 300- MONDAY/WEDNESDAY 13:00-15:30Math 300- MONDAY/WEDNESDAY 15:30-17:00Calculus I- TUESDAY/THURSDAY 08:00-10:00Psych 101- TUESDAY/THURSDAY 10:00-11:00Sociology 101- TUESDAY/THURSDAY 13:00-14:00Biology 101- TUESDAY/THURSDAY 14:00-15:00Orientation 101- THURSDAY 15:00-16:00Psych 300- FRIDAY 13:00-16:00
Validate the output. Not bad, right? If we were to plot this out visually, here is what the schedule looks like:
Pretty cool, isn’t it? We can use this exact same methodology beyond just scheduling staff and other resources. It can also be used for any discrete model that needs to find feasible or optimal values to find a greater solution. This comes surprisingly handy in the most unexpected situations. I cannot share the specifics, but I had a project that seemed to have a forecasting/regression nature. When I abandoned traditional continuous regression models and discretely used a tree search technique, it was powerfully effective and solved my specific problem better than any regression library could.
Before I wrap up, if you want to schedule against multiple classrooms, just set each binary Slot variable against a time block, a class, and a room to make it 3-dimensional as shown below. You can then create constraints to ensure any room is not occupied twice. Otherwise the modeling works just the same.
A 3-dimensional model that defines variables against multiple rooms
Hopefully you guys find this fascinating and useful. I also hope this opened your eyes to other “AI” models that have existed for decades and yet rarely get exposure. If you want to learn more, definitely check out the Discrete Optimization class on Coursera to learn some more best-kept secrets from the field of operations research.
SOURCE CODE:
thomasnield/optimized-scheduling-demo_A branch-and-bound solver to create classroom schedules — thomasnield/optimized-scheduling-demo_github.com