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 SlotsTo 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 operating day/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 VariablesNow 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 SudokuHopefully Sudokus are a familiar puzzle game.
You are provided a 9×9 grid of cells, where some cells already have possible numbers 1–9.
You need to find values of 1–9 for the rest of the blank cells so that every row, column, and 3×3 square has the numbers 1–9.
A typical Sudoku puzzleSo 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-solverA suduko game solver written in Kotlin.
Contribute to thomasnield/kotlin-sudoku-solver development by creating an…github.
comBack to the Scheduling ProblemSo 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.
DayOfWeekclass 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 workval 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:00Validate 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 roomsHopefully 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-demoA branch-and-bound solver to create classroom schedules – thomasnield/optimized-scheduling-demogithub.
com.