Sudokus and Schedules

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 . But I can show you how to algorithmically solve these problems in a (usually) timely manner. NP Hard territory 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 ? How about optimizing the on-time performance of a train network? Or simply solving a Sudoku? schedule sports tournaments and minimize team travel distances There are many algorithms out there to solve problems with an optimization nature. These include , , and 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. linear programming metaheuristics integer programming 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 or do any discrete-based regression. adapt these approaches to build chess AI algorithms Before I start, I highly recommend this challenging but useful . 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. Coursera class on discrete optimization 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 create a model that schedules these classes with no overlap and complies with these requirements. YOUR OBJECTIVE: 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. SPOILER ALERT: 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 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 week broken up in 15 minute blocks, like this: very entire 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 that can be 1 or 0. This binary variable will be solved to indicate whether or not that is the start time for the first recurrence of that class. We will set them all to 0 for now as shown below: Slot Slot 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 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 / API to make our calendar work easier. Kotlin LocalDate LocalTime 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: java.time.LocalDate java.time.LocalTime import import _// Any Monday through Friday date range will work_ =LocalDate.of(2017,10,16)..LocalDate.of(2017,10,20) val operatingDates = LocalTime.of(8,0)..LocalTime.of(17,0) val operatingDay = >(LocalTime.of(11,30)..LocalTime.of(12,59)) val breaks listOf Next let’s declare the which holds the properties of a given class we want to schedule. ScheduledClass ScheduledClass( : Int, : String, : Double, : Int, : Int = 2) data class val id val name val hoursLength val recurrences val recurrenceGapDays The is the minimum number of days needed between each recurrence’s start time. For instance, take 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 , which will put 48 hours between the start of each session. recurrenceGapDays Psych 100 2 Next we can declare all the instances in a : ScheduledClass List = (ScheduledClass(id=1,name= ,hoursLength=1.0,recurrences=2),ScheduledClass(id=2,name= ,hoursLength=1.5,recurrences=3),ScheduledClass(id=3,name= ,hoursLength=1.5,recurrences=2),ScheduledClass(id=4,name= ,hoursLength=3.0,recurrences=1),ScheduledClass(id=5,name= ,hoursLength=2.0,recurrences=2),ScheduledClass(id=6,name= ,hoursLength=2.0,recurrences=3),ScheduledClass(id=7,name= ,hoursLength=1.0,recurrences=2),ScheduledClass(id=8,name= ,hoursLength=1.0,recurrences=2),ScheduledClass(id=9,name= ,hoursLength=2.5,recurrences=2),ScheduledClass(id=10,name= ,hoursLength=1.0,recurrences=1)) val scheduledClasses listOf "Psych 101" "English 101" "Math 300" "Psych 300" "Calculus I" "Linear Algebra I" "Sociology 101" "Biology 101" "Supply Chain 300" "Orientation 101" The class will represent each discrete 15-minute time period. We will use a Kotlin in combination with Java 8’s API to generate all blocks for the entire planning window. We will also create a few helper properties to extract the as well as whether it is . The property will determine if this is within a schedulable window of time (e.g. not scheduled in the middle of the night or inside a break period). Block Sequence LocalDate/LocalTime timeRange withinOperatingDay withinOperatingDay Block _/** A discrete, 15-minute chunk of time a class can be scheduled on */_ Block( : ClosedRange ) { data class val range **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_ **{** ( . .atStartOfDay()){dt dt.plusMinutes(15). .plusMinutes(15) takeIf { it operatingDates endInclusive }} map { it it } 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 . This is to prevent circular construction issues by not constructing the items until they are first called. [lazy { }](https://kotlinlang.org/docs/reference/delegated-properties.html#lazy) delegate Finally, the class will represent an intersection/cell between a and a . We will generate all of them by pairing every with every . We will also create an unassigned binary variable which will be until we assign it a or . Slot ScheduledClass Block ScheduledClass Block selected null 1 0 Slot( : Block, : ScheduledClass) { data class val block val 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 variables. In Python you can use or . On the Java platform you can use or . For many of these libraries, I could also drop in a $10K which can execute a solve more quickly for larger, more complex problems. selected PuLp PyOmo ojAlgo OptaPlanner IBM CPLEX license 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 variables in each , 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. selected Slot Again, we are going to assign each a or . 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: Slot 1 0 to indicate the start of the first class repetition 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 . A sum of effectively means only one class is taking up that block, and means no classes are occupying that block at all (also valid). The cases below are also failures because the sum of “affecting” slots is . 1 1 0 2 If we shifted Sociology 101 to 10:00AM, the sum would then be and all is good (shown below): 1 We need to apply this logic to 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. every This can even account for the recurrences too. After all, we put a in a slot to indicate the candidate start time . 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. 1 of the first class 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 of items: List RecurrenceMode { , , } enum class PARTIAL_ONLY FULL_ONLY ALL List .affectedWindows(slotsNeeded: Int,gap: Int,recurrences: Int,mode: RecurrenceMode = RecurrenceMode. ) = fun FULL_ONLY (0.. ). (). i (1..recurrences). (). ( - 1) * gap . + i ) ) . () . (mode) {RecurrenceMode. -> size asSequence map { -> asSequence map { it } filter { it size } map { -> let { if it size size else it } } toList } filter {when ALL true RecurrenceMode. -> . == recurrences && . . == slotsNeeded FULL_ONLY it size it all { it size } RecurrenceMode. -> . < recurrences || . . < slotsNeeded } PARTIAL_ONLY it size it any { it size } } 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 and perform a specialized windowing operation that injects a between each recurrence. This will return a list of lists, , where each list is a recurrence and the elements in it are the affected elements. Note the is the number of elements between each start of the window. List gap List > gap 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 will be set to . mode RecurrenceMode.FULL_ONLY main(args: Array ) { fun (1..20). (). (slotsNeeded = 4,gap = 6,recurrences = 3,mode = RecurrenceMode. ). ( ) **}**} toList affectedWindows 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 to , it will give us the “broken” groups that were unable to produce recurrences all with a length of . 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). mode RecurrenceMode.PARTIAL_ONLY 3 4 main(args: Array ) {(1..20). (). (slotsNeeded = 4,gap = 6,recurrences = 3,mode = RecurrenceMode. ). ( ) **}**} fun toList affectedWindows 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 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. affectedWindows() _/** A discrete, 15-minute chunk of time a class can be scheduled on */_ Block( : ClosedRange ) { data class val range **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_ **{** ( . .atStartOfDay()){dt dt.plusMinutes(15). .plusMinutes(15) takeIf { it operatingDates endInclusive }} map { it it } toList } /* only returns blocks within the operating times */ val allInOperatingDay by lazy {all filter { it withinOperatingDay }} ScheduledClass( : Int, : String, : Double, : Int, : Int = 2) { data class val id val name val hoursLength val recurrences val recurrenceGapDays _/\*\* 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_() **}** () = . (). . == 1 . . . . . ()!! /**translates and returns the optimized start time of the class */ val start get slots asSequence filter { it selected } map { it block dateTimeRange start } min () = .plusMinutes(( * 60.0).toLong()) /** translates and returns the optimized end time of the class */ val end get start hoursLength _/\*\* 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 it. prune 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. is where the recursive tree happens. This part of the code _A suduko game solver written in Kotlin. Contribute to thomasnield/kotlin-sudoku-solver development by creating an…_github.com thomasnield/kotlin-sudoku-solver 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 ). Note how I use 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 function to explore the entire tree recursively until a solution is found. just look at the source code BranchNode traverse() java.time.DayOfWeek import BranchNode( : Int,restOfTree: List , : BranchNode? = ) { class val selectedValue val previous 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** } } executeBranchingSearch() { fun _// 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. && . . == 3-> 1000 MONDAY it scheduledClass recurrences dow DayOfWeek. ..DayOfWeek. && . . == 2-> -500 in MONDAY WEDNESDAY it scheduledClass recurrences dow DayOfWeek. ..DayOfWeek. && . . == 2-> 500 !in MONDAY WEDNESDAY it scheduledClass recurrences dow DayOfWeek. ..DayOfWeek. && . . == 1-> -300 in THURSDAY FRIDAY it scheduledClass recurrences dow DayOfWeek. ..DayOfWeek. && . . == 1 -> 300 !in THURSDAY FRIDAY it scheduledClass recurrences -> 0} , else } _// make search start at beginning of week_ . . . , { it block range start } - . .**slotsNeededPerSession } **)). () // followed by class length { it scheduledClass 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 } (candidateValue intArrayOf(1,0)) { nextBranch = BranchNode(candidateValue,currentBranch?.remainingSlots?: sortedSlots,currentBranch) for in val **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"**) } java.time.LocalDate java.time.LocalTime import import _// Any Monday through Friday date range will work_ =LocalDate.of(2017,10,16)..LocalDate.of(2017,10,20) val operatingDates = LocalTime.of(8,0)..LocalTime.of(17,0) val operatingDay = >(LocalTime.of(11,30)..LocalTime.of(12,59)) val breaks listOf 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! main(args: Array ) { fun _executeBranchingSearch_() ScheduledClass. . . . ( . . . ( ) . .toLocalTime() . .toLocalTime() ) } all sortedBy { it start } forEach { println "${it name}-${it daysOfWeek joinToString "/" }${it start }-${it end }" } 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 could. regression library Before I wrap up, if you want to schedule against multiple classrooms, just set each binary 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. Slot 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 to learn some more best-kept secrets from the field of operations research. Discrete Optimization class on Coursera SOURCE CODE: _A branch-and-bound solver to create classroom schedules — thomasnield/optimized-scheduling-demo_github.com thomasnield/optimized-scheduling-demo