YouTube Videos

A Simple Neural Network
KotlinConf 2018 - Mathematical Modeling
Creating a Sudoku Solver from Scratch
Traveling Salesman Problem
Text Categorization w/ Naive Bayes
Monty Hall Problem
Solving World's Hardest Sudoku

Friday, February 23, 2018

Linear Programming with Kotlin Part III - Generating Multi-day Schedules

In Part I of this series I introduced binary programming with Kotlin and ojAlgo. In Part II, I introduced continuous variables and optimization concepts. In this section, I am going to present something more ambitious and useful: generating multi-day schedules. This can be applied to scheduling problems such as staffing, manufacturing, transportation, classroom allocation, and even sport event planning.

I started building okAlgo which contains Kotlin idiomatic extensions to ojAlgo. Hopefully I will get a chance to release this soon.

It is one thing to create an app that allows you to input events into a calendar. It is another for it to automatically schedule the events for you. Rather than relying on iterative brute-force tactics to fit events into a schedule (which can be hopelessly inefficent), we can achieve magic one-click generation of a schedule using mathematical modeling.

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 blocks. 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 2 dimensions. The latter will likely be another article in this series.

Before I start, I found a challenging but useful Coursera class on discrete optimization. This class is fairly ambitious and I hope to find time to complete it. It goes into different techniques to build optimization models from scratch using Python, Java, or any other platform of your choice. So far I highly recommend this class if you want to commit 10-15 hours a week to this topic.

The Problem

You need a one-click application to schedule university classes against a single classroom. These classes have differing lengths and may “repeat” throughout the week:

  • 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)

Each session must start at the same time of day. 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/end 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

Classes must be scheduled within these times.

OBJECTIVE: Create a discrete programming model that schedules these classes with no overlap and complies with these requirements.

Laying the Groundwork

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. 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 is a “slot” that can be 1 or 0. This binary will serve 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:

This grid is crucial to thinking about this problem logically. It will make an effective visual aid because mathematical constraints will focus on regions within the grid.

On the Kotlin side, let’s get our infrastructure set up. First let’s improvise a DSL to make ojAlgo a little easier to work with. Note I am creating an extension to ojAlgo called okAlgo, which will create some nice Kotlin idioms. But for now, this should work.

import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
import java.util.concurrent.atomic.AtomicInteger

// declare model
val model = ExpressionsBasedModel()


// improvised DSL
val funcId = AtomicInteger(0)
val variableId = AtomicInteger(0)
fun variable() = Variable(variableId.incrementAndGet().toString().let { "Variable$it" }).apply(model::addVariable)
fun addExpression() = funcId.incrementAndGet().let { "Func$it"}.let { model.addExpression(it) }

We are going to take advantage of Java 8’s great LocalDate/LocalTime API to make calendar work easier. Let’s set up our core parameters like so:

import java.time.LocalDate
import 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(13,0)
)


// classes
val scheduledClasses = listOf(
        ScheduledClass(id=1, name="Psych 101",hoursLength=1.0, repetitions=2),
        ScheduledClass(id=2, name="English 101", hoursLength=1.5, repetitions=3),
        ScheduledClass(id=3, name="Math 300", hoursLength=1.5, repetitions=2),
        ScheduledClass(id=4, name="Psych 300", hoursLength=3.0, repetitions=1),
        ScheduledClass(id=5, name="Calculus I", hoursLength=2.0, repetitions=2),
        ScheduledClass(id=6, name="Linear Algebra I", hoursLength=2.0, repetitions=3),
        ScheduledClass(id=7, name="Sociology 101", hoursLength=1.0, repetitions=2),
        ScheduledClass(id=8, name="Biology 101", hoursLength=1.0, repetitions=2)
)


data class ScheduledClass(val id: Int,
                          val name: String,
                          val hoursLength: Double,
                          val repetitions: Int,
                          val repetitionGapDays: Int = 2)

The repetitionGapDays is the minimum number of days needed between each recurrence’s start time. For instance, since Psych 100 requires 2 repetitions and defaults to a 2-day gap, if the first class was on MONDAY at 8AM then the second repetition must be scheduled at least 2 days (48 hours) later, which is WEDNESDAY at 8AM. All classes will default to a 2-day gap.

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 of them 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 an operating day.

data class Block(val dateTimeRange: ClosedRange<LocalDateTime>) {

  val timeRange = dateTimeRange.let {
     it.start.toLocalTime()..it.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

    companion object {

        // Operating blocks
        val all by lazy {
            generateSequence(operatingDates.start.atStartOfDay()) {
                it.plusMinutes(15).takeIf {
                  it.plusMinutes(15) <= operatingDates.endInclusive.atTime(23,59)
                }
            }.map { Block(it..it.plusMinutes(15)) }
             .toList()
        }
    }
}

Note I am going to initialize items for each domain object using a lazy { } delegate. This is to prevent circular construction issues.

Finally, the Slot class will represent an intersection between a ScheduledClass and a Block. We will generate all of them by pairing every ScheduledClass with every Block. We will also create a binary() ojAlgo variable which will be fixed to 0 if the Block is not within the operating day.

data class Slot(val block: Block, val scheduledClass: ScheduledClass) {
    val occupied = variable().apply { if (block.withinOperatingDay) binary() else level(0) }

    companion object {

        val all by lazy {
            Block.all.asSequence().flatMap { b ->
                ScheduledClass.all.asSequence().map { Slot(b,it) }
            }.toList()
        }
    }
}

Coming Up with a Model

In the first article in this series, I showed an approach to capture the necessary contiguous blocks for a given session. I found this approach to scale poorly with ojAlgo, although there are changes in the upcoming release (support for ordered sets) that might work with this approach. I could also drop in a $10K CPLEX license which also might execute a solve quickly.

But I like things to remain free and open-source where possible, so I concentrated hard and came up with a better mathematical model. It is highly abstract but powerful and effective for this particular problem.

Again, we are going to label each Slot as 1 or 0 to indicate the start of the first class repetition. Here is one possible iteration the solver may come up with, where the first Psych 101 class starts on MON 9:00AM and Sociology 101 starts on MON 9:45AM. Here it is on our grid:

Study this scenario closely. Do you see a pattern for 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 blocks 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). This particular case fails because the sum of “affecting” blocks is 2.

If we shifted Sociology 101 to 10:00AM, the sum would then be 1 and all is good.

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. 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.

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, and Kotlin’s stdlib can nail this effectively. The benefit is we do not have create any new variables, and can constrain the existing slot binary variables with a series of simple sum constraints.

Extracting Recurrences and Affected Slots

Wrangling and transforming data is tedious, and it is the unglamorous part of data science where 90% of the work occurs. It is for this reason Python has rapidly overtook R, but I think Kotlin can serve us type safety-minded folks who also appreciate extensibility and higher-order functions.

What we need to do first is identify the “groups” of slots for each class, and by “group” I mean an entire set of recurrences across the week. The star of this codebase is is going to be this Kotlin extension function, which will accomplish just that:

fun <T> List<T>.rollingRecurrences(slotsNeeded: Int, gap: Int, recurrences: Int) =
        (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 })
                    }.filter { it.size == slotsNeeded }
                    .toList()
        }.filter { it.size == recurrences }

I will let you dive deep into the implementation on your own later. For now it is more productive to cover what it accomplishes, which is take any List<T> and perform a specialized windowed() operation that injects a gap between each grouping. Note the gap is the number of items between each start of the window. For instance, we can take the numbers 1…20 and break them up in groups of 4, with a gap of 6 between each recurrence start, and have 3 recurrences.

fun main(args: Array<String>) {

    (1..20).toList().rollingRecurrences(slotsNeeded = 4, gap = 6, recurrences = 3)
            .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]]

We can use this extension function to handle the class repetitions, and generate all possible permutations within our time planning window of one week. We can then use that to find slots for a particular class that affect a particular block, as implemented with our affectingSlotsFor() function shown below. We will also set our constraints dictating

data class ScheduledClass(val id: Int,
                          val name: String,
                          val hoursLength: Double,
                          val repetitions: Int,
                          val repetitionGapDays: Int = 2) {

    /** the # of slots between each recurrence */
    val gapLengthInSlots = repetitionGapDays * 24 * 4

    /** the # of slots needed for a given recurrence */
    val slotsNeeded = (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 slotGroups by lazy {
        slots.rollingRecurrences(slotsNeeded = slotsNeeded, gap = gapLengthInSlots, recurrences = repetitions)
    }

    /** yields slots that affect the given block for this scheduled class */
    fun affectingSlotsFor(block: Block) = slotGroups.asSequence()
            .filter { it.flatMap { it }.any { it.block == block } }
            .map { it.first().first() }

    companion object {
        val all by lazy { scheduledClasses }
    }
}

To finish this off, let’s implement the needed constraints in the ScheduledClass with a addConstraints() function. We will set the sum of slots for each given class must be 1, so that at least one instance is scheduled. We will also limit the model exploring solutions for classes that have 3 repetitions, and say the start of the first class must be on MONDAY for those cases. For 2 repetitions, we will specify the first class must start on MONDAY, WEDNESDAY, or FRIDAY. We will achieve these by saying the sum in these regions must be 1.

We will also create start and end properties that will translate the model’s optimized slots (where one slot is 1), and translate it back to a LocalDateTime.

data class ScheduledClass(val id: Int,
                          val name: String,
                          val hoursLength: Double,
                          val repetitions: Int,
                          val repetitionGapDays: Int = 2) {

    /** the # of slots between each recurrence */
    val gapLengthInSlots = repetitionGapDays * 24 * 4

    /** the # of slots needed for a given occurrence */
    val slotsNeeded = (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 slotGroups by lazy {
        slots.rollingRecurrences(slotsNeeded = slotsNeeded, gap = gapLengthInSlots, recurrences = repetitions)
    }

    /** yields slots that affect the given block for this scheduled class */
    fun affectingSlotsFor(block: Block) = slotGroups.asSequence()
            .filter { it.flatMap { it }.any { it.block == block } }
            .map { it.first().first() }

    /** translates and returns the optimized start time of the class */
    val start get() = slots.asSequence().filter { it.occupied.value.toInt() == 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..(repetitions-1)).asSequence().map { start.dayOfWeek.plus(it.toLong() * repetitionGapDays) }.sorted()

    fun addConstraints() {

        //sum of all slots for this scheduledClass must be 1
        // s1 + s2 + s3 .. + sn = 1
        addExpression().level(1).apply {
            slots.forEach {
                set(it.occupied, 1)
            }
        }

        // Guide Mon/Wed/Fri for three repetitions
        // If 3 repetitions are needed, the sum of slots on Monday must be 1
        if (repetitions == 3) {
            addExpression().level(1).apply {
                slots.filter { it.block.dateTimeRange.start.dayOfWeek == DayOfWeek.MONDAY }
                        .forEach {
                            set(it.occupied, 1)
                        }
            }
        }

        // Guide two repetitions to start on Mon, Tues, or Wed
        // If 2 repetitions are needed, the sum of slots on Monday, Tuesday, and Wednesday must be 1

        if (repetitions == 2) {
            addExpression().level(1).apply {
                slots.filter { it.block.dateTimeRange.start.dayOfWeek in DayOfWeek.MONDAY..DayOfWeek.WEDNESDAY }.forEach {
                    set(it.occupied, 1)
                }
            }
        }
    }

    companion object {
        val all by lazy { scheduledClasses }
    }
}

lNow going back to the Block class, I will add an addConstraints() function. It will query all the affecting blocks for each ScheduledClass and say they must all sum to no more than 1. This ensures no overlap between classes will occur. But if a block is not within an operating day, not only should its slots be fixed to 0, but all of its affecting slots should be fixed to 0.

/** A discrete, 15-minute chunk of time a class can be scheduled on */
data class Block(val dateTimeRange: ClosedRange<LocalDateTime>) {

    val timeRange = dateTimeRange.let { it.start.toLocalTime()..it.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

    fun addConstraints() {
        if (withinOperatingDay) {
            addExpression().lower(0).upper(1).apply {
                ScheduledClass.all.asSequence().flatMap { it.affectingSlotsFor([email protected]) }
                        .forEach {
                            set(it.occupied, 1)
                        }
            }
        } else {
            ScheduledClass.all.asSequence().flatMap { it.affectingSlotsFor([email protected]) }
                    .forEach {
                        it.occupied.level(0)
                    }
        }
    }

    companion object {

        /* All operating blocks for the entire week, broken up in 15 minute increments */
        val all by lazy {
            generateSequence(operatingDates.start.atStartOfDay()) {
                it.plusMinutes(15).takeIf { it.plusMinutes(15) <= operatingDates.endInclusive.atTime(23,59) }
            }.map { Block(it..it.plusMinutes(15)) }
                    .toList()
        }

        fun applyConstraints() {
            all.forEach { it.addConstraints() }
        }
    }
}

Here is the Kotlin code in its entirety, where the respective addConstraints() functions are invoked and the results are iterated. You can also get this code here on GitHub.

import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
import java.time.DayOfWeek
import java.time.LocalDate
import java.time.LocalDateTime
import java.time.LocalTime
import java.util.concurrent.atomic.AtomicInteger


// 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(13,0)
)


// classes
val scheduledClasses = listOf(
        ScheduledClass(id=1, name="Psych 101",hoursLength=1.0, repetitions=2),
        ScheduledClass(id=2, name="English 101", hoursLength=1.5, repetitions=3),
        ScheduledClass(id=3, name="Math 300", hoursLength=1.5, repetitions=2),
        ScheduledClass(id=4, name="Psych 300", hoursLength=3.0, repetitions=1),
        ScheduledClass(id=5, name="Calculus I", hoursLength=2.0, repetitions=2),
        ScheduledClass(id=6, name="Linear Algebra I", hoursLength=2.0, repetitions=3),
        ScheduledClass(id=7, name="Sociology 101", hoursLength=1.0, repetitions=2),
        ScheduledClass(id=8, name="Biology 101", hoursLength=1.0, repetitions=2)
)

fun main(args: Array<String>) {

    println("Job started at ${LocalTime.now()}")

    applyConstraints()

    model.countVariables().run { println("$this variables") }

    model.options.apply {
        iterations_suffice = 0
    }

    println(model.minimise())

    ScheduledClass.all.forEach {
        println("${it.name}- ${it.daysOfWeek.joinToString("/")} ${it.start.toLocalTime()}-${it.end.toLocalTime()}")
    }

    println("Job ended at ${LocalTime.now()}")

}

// declare model
val model = ExpressionsBasedModel()


// improvised DSL
val funcId = AtomicInteger(0)
val variableId = AtomicInteger(0)
fun variable() = Variable(variableId.incrementAndGet().toString().let { "Variable$it" }).apply(model::addVariable)
fun addExpression() = funcId.incrementAndGet().let { "Func$it"}.let { model.addExpression(it) }


/** A discrete, 15-minute chunk of time a class can be scheduled on */
data class Block(val dateTimeRange: ClosedRange<LocalDateTime>) {

    val timeRange = dateTimeRange.let { it.start.toLocalTime()..it.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

    fun addConstraints() {
        if (withinOperatingDay) {
            addExpression().lower(0).upper(1).apply {
                ScheduledClass.all.asSequence().flatMap { it.affectingSlotsFor([email protected]) }
                        .filter { it.block.withinOperatingDay }
                        .forEach {
                            set(it.occupied, 1)
                        }
            }
        } else {
            ScheduledClass.all.asSequence().flatMap { it.affectingSlotsFor([email protected]) }
                    .forEach {
                        it.occupied.level(0)
                    }
        }
    }

    companion object {

        /* All operating blocks for the entire week, broken up in 15 minute increments */
        val all by lazy {
            generateSequence(operatingDates.start.atStartOfDay()) {
                it.plusMinutes(15).takeIf { it.plusMinutes(15) <= operatingDates.endInclusive.atTime(23,59) }
            }.map { Block(it..it.plusMinutes(15)) }
                    .toList()
        }

        fun applyConstraints() {
            all.forEach { it.addConstraints() }
        }
    }
}


data class ScheduledClass(val id: Int,
                          val name: String,
                          val hoursLength: Double,
                          val repetitions: Int,
                          val repetitionGapDays: Int = 2) {

    /** the # of slots between each recurrence */
    val gapLengthInSlots = repetitionGapDays * 24 * 4

    /** the # of slots needed for a given occurrence */
    val slotsNeeded = (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 slotGroups by lazy {
        slots.rollingRecurrences(slotsNeeded = slotsNeeded, gap = gapLengthInSlots, recurrences = repetitions)
    }

    /** yields slots that affect the given block for this scheduled class */
    fun affectingSlotsFor(block: Block) = slotGroups.asSequence()
            .filter { it.flatMap { it }.any { it.block == block } }
            .map { it.first().first() }

    /** translates and returns the optimized start time of the class */
    val start get() = slots.asSequence().filter { it.occupied.value.toInt() == 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..(repetitions-1)).asSequence().map { start.dayOfWeek.plus(it.toLong() * repetitionGapDays) }.sorted()

    fun addConstraints() {

        //sum of all slots for this scheduledClass must be 1
        // s1 + s2 + s3 .. + sn = 1
        addExpression().level(1).apply {
            slots.forEach {
                set(it.occupied, 1)
            }
        }

        // Guide Mon/Wed/Fri for three repetitions
        // If 3 repetitions are needed, the sum of slots on Monday must be 1
        if (repetitions == 3) {
            addExpression().level(1).apply {
                slots.filter { it.block.dateTimeRange.start.dayOfWeek == DayOfWeek.MONDAY }
                        .forEach {
                            set(it.occupied, 1)
                        }
            }
        }

        // Guide two repetitions to start on Mon, Tues, or Wed
        // If 2 repetitions are needed, the sum of slots on Monday, Tuesday, and Wednesday must be 1

        if (repetitions == 2) {
            addExpression().level(1).apply {
                slots.filter { it.block.dateTimeRange.start.dayOfWeek in DayOfWeek.MONDAY..DayOfWeek.WEDNESDAY }.forEach {
                    set(it.occupied, 1)
                }
            }
        }
    }

    companion object {
        val all by lazy { scheduledClasses }
    }
}



data class Slot(val block: Block, val scheduledClass: ScheduledClass) {
    val occupied = variable().apply { if (block.withinOperatingDay) binary() else level(0) }

    companion object {

        val all by lazy {
            Block.all.asSequence().flatMap { b ->
                ScheduledClass.all.asSequence().map { Slot(b,it) }
            }.toList()
        }
    }
}


fun applyConstraints() {
    Block.applyConstraints()
    ScheduledClass.all.forEach { it.addConstraints() }
}

fun <T> List<T>.rollingBatches(batchSize: Int) = (0..size).asSequence().map { i ->
    subList(i, (i + batchSize).let { if (it > size) size else it })
}.filter { it.size == batchSize }

fun <T> List<T>.rollingRecurrences(slotsNeeded: Int, gap: Int, recurrences: Int) =
        (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 })
                    }.filter { it.size == slotsNeeded }
                    .toList()
        }.filter { it.size == recurrences }

When I run this entire application, here are the scheduled classes!

Psych 101- WEDNESDAY/FRIDAY 10:30-11:30
English 101- MONDAY/WEDNESDAY/FRIDAY 13:15-14:45
Math 300- TUESDAY/THURSDAY 15:15-16:45
Psych 300- THURSDAY 08:15-11:15
Calculus I- TUESDAY/THURSDAY 13:15-15:15
Linear Algebra I- MONDAY/WEDNESDAY/FRIDAY 08:15-10:15
Sociology 101- WEDNESDAY/FRIDAY 16:00-17:00
Biology 101- WEDNESDAY/FRIDAY 15:00-16:00

If we were to plot this out visually, here is what the schedule looks like:

Hopefully you guys find this fascinating and useful. I will definitely post a few more articles on Kotlin for linear programming when I find some interesting use cases.

46 comments:

  1. It would be interesting to compare ojAlgo's results with those of the course scheduling implementation in our optaplanner-examples: https://youtu.be/4meWIhPRVn8
    That particular example is implemented in Java, but there are quite a few users implementing use cases with Kotlin (it's all JVM anyway).

    ReplyDelete
    Replies
    1. Hi Geoffrey, glad to see you here. Yes doing an implementation of this in OptaPlanner is next on my docket. As a matter of fact, it's literally on the Roadmap checklist on the GitHub page for this project: https://github.com/thomasnield/optimized-scheduling-demo

      I struggled figuring out how to use it with Kotlin at first, but I have a colleague who has done so successfully. I need to look at this example project he just gave me: https://github.com/KevinGreene/grjug-optaplanner-lab

      Delete
  2. TechnologyTechnology is constantly changing. It is an industry that moves so fast, things can become obsolete within weeks. Thus it is essential to always stay on top of news and information, whether it be by newsletter, following RSS feeds and blogs, tutorials or going back to school.

    Click here to know more information Tech Blogs

    ReplyDelete
  3. Wow, wonderful blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your site is great, as well as the content!

    ReplyDelete
  4. Such an ideal piece of blog. It’s quite interesting to read content like this. I appreciate your blog
    Data Science Training in Bangalore

    ReplyDelete
  5. How to write a paper you don't want to write? Order it at

    ReplyDelete
  6. I am happy with your article, your website is pretty good. Many articles are very useful for everyone. I am sure your website will grow in the future
    help.norton.com

    ReplyDelete
  7. Hi,Thanks for sharing nice blog post...
    More: https://www.kellytechno.com/Hyderabad/Course/Data-Science-Training
    Data Science Training in Hyderabad

    ReplyDelete
  8. Are you unable to deal with transaction errors in your Binance account through mobile app? if you don’t know the process, you can always call the team of skilled executives who is always available and users can talk to the team anytime to avail fruitful solutions. Whenever Binance Support Number you are in doubt, you can dial Binance support number and avail facilities from the team to deal with your issues in no time. You can connect with the team to avail solutions immediately.

    ReplyDelete
  9. Are you unable to receive digital currency from another wallet in Blockchain? Has this become a problem and are you daunted by the fact that you might not enjoy a smooth trading? Don’t worry it is not a big issue and can be taken care of by contacting Blockchain support number where you get in touch with experienced professionals who are Blockchain Support NUmber reliable as well as pro-active. They feel happy and privileged to assist you, so contact them to get your issues fixed in no time in flawless manner.

    ReplyDelete
  10. Are you unable to receive digital currency from another wallet in Gemini? Has this become a problem and are you daunted by the fact that you might not enjoy a smooth trading? Don’t worry it is not a big issue and can be taken care of by contacting Gemini support number Gemini Support Number where you get in touch with experienced professionals who are reliable as well as pro-active. They feel happy and privileged to assist you, so contact them to get your issues fixed in no time in flawless manner.

    ReplyDelete
  11. Are you unable to deal with transaction errors in your Libra Coin account through mobile app? if you don’t know the process, you can always call the team of skilled executives who is always available and users can talk to the team anytime to avail fruitful solutions. Libra Support Number Whenever you are in doubt, you can dial Libra support number and avail facilities from the team to deal with your issues in no time. You can connect with the team to avail solutions immediately.

    ReplyDelete
  12. Gemini is an open source wallet that is utilized for storing, saving and sending the bitcoins. In Gemini, users get permanent payment address that can be displayed publicly. To know more information about the Gemini exchange, you can approach the experts who will guide you everything in stepwise manner. You can approach the experts by dialing Gemini support phone number and convey your issue to them. They will provide best guidance related to the issue and clear all the doubts from the roots and also provide full-fledged information about the Gemini exchange.

    ReplyDelete
  13. Really great article, Glad to read the article. It is very informative for us. Thanks for posting.Norton™
    provides industry-leading antivirus and security software
    for your PC, Mca, and mobile devices Visit @: - McAfee.com/activate | norton.com/setup | McAfee.com/activate

    ReplyDelete
  14. Thank™ you for sharing excellent information. ✆ Your website is so cool. I am impressed by the details that you have on this website ☞ It reveals how nicely you understand this subject. Bookmarked♠ this website page, will come back for extra articles. You, my friend, ROCK£ I found simply the info I already searched everywhere and simply could not come across. What a great website. Visit௹☞ Norton.com/setupoffice.com/setupTelstra supportPlumbers Near Me | office.com/setup | Nurton.com/nu16..

    ReplyDelete


  15. To install office setup you have to select the downloaded file otherwise insert the office setup CD disc. If you use the CD disc then you have to enter the Office Product Key for authorizing it. After selecting the downloaded file you have to run or setup this file on your computer.

    office.com/setup

    ReplyDelete
  16. The 123.hp.com/setup team of technical experts is an excellent group of people who believe in great repairs. They have been working in the same domain from almost a decade and that is why they deliver the most amazing services & The 123.hp.com/setup team of technical experts is an excellent group of people who believe in great repairs. They have been working in the same domain from almost a decade and that is why they deliver the most amazing services.

    ReplyDelete
  17. If you are looking for laser printer, then Brother is the place for you to look for it. If you’ve purchased a Brother Printer but don’t know how to setup the printer with your computer, then don’t worry. All you need is to give us a call for technical assistance and get a step-by-step solution to install your machine. Brother Printer Support is available 24/7 to help tackle unique problems you face with your brother printer.

    ReplyDelete
  18. You could definitely see your skills in the article you write. The world hopes for even more passionate writers like you who aren’t afraid to say how they believe. All the time go after your heart.
    Factory Reset Computer

    ReplyDelete
  19. Are you looking for HP Printer Assistant. Visit Help Number USA to fix technical error. Get support from HP Printer Assistant!
    HP Printer Assistant download |
    HP Support Assistant download |
    How to change password in Outlook |
    How to reset apple id password on iPhone |

    ReplyDelete
  20. Thank for important information . I like your explanation of topic and ability to do work.I really found your post very interesting .
    Netflix Password Reset

    ReplyDelete
  21. It has been great to read this article it was quiet to be nice you every detail about the topic Thanks for sharing this article with us.
    How to reset mac computer

    ReplyDelete
  22. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    How to reset your Wireless Router successfully

    ReplyDelete
  23. Positive web page source, where did u come up with the information on this posting? Before you set up McAfee Antivirus protection on your device, you first need to make sure that you don’t have an older version of McAfee on your device. mcafee.com/activate | mcafee.com/activate | mcafee.com/activate

    ReplyDelete
  24. Thank you so much for sharing such superb information's with us. Download the Microsoft Office setup on your Windows or Mac computer. Make sure that the Office product key is already copied for the activation procedure. office.com/setup | office.com/setup | office.com/setup

    ReplyDelete
  25. To get protection, download, install and activate norton setup with 25-digit alphanumeric product key at norton.com setup. In case a new user, then create an account or log In by entering email address and password.

    ReplyDelete
  26. Norton is a reputed and cost-effective antivirus suite company which offers protection so that

    no virus can damage your computer. It also provides many other products and services apart

    from antivirus.

    norton.com/setup

    ReplyDelete
  27. office.com/setup - Easy guide to install office setup at www.office.com/setup Online. Get Started with MS Office Setup at office.com/setup.

    ReplyDelete
  28. www.trendmicro.com/downloadme For Trend Micro Download , you must create a Trend Micro account from trend micro that can help you in smooth Trend Micro installation.

    ReplyDelete
  29. www.norton.com/setup USA, Download & install Norton setup product key. Norton.com/setup login for norton.com/setup activate & wwwnorton.com/setup Key
    norton.com/setup
    norton.com/setup
    norton.com/setup

    ReplyDelete
  30. This comment has been removed by the author.

    ReplyDelete
  31. This comment has been removed by the author.

    ReplyDelete

  32. Norton.com/setup helps you to deploy Norton setup on your computing devices. Here are the steps for deployment of Norton setup without any interruptions.
    norton.com/setup

    ReplyDelete
  33. We support all types of HP printer troubleshooting and service. Just enter the model number of your printer in 123.hp.com/setup to identify the software and drivers your printer requires. Download and install it in your mac and 'Run' the file. The process is easy however if you have any doubts or queries regarding HP printers contact us.

    ReplyDelete
  34. Crackle, the most entertaining channel is now on Roku to entertain you. If you are new to this channel, use the page crackle.com/activate. Once if you activate the channel, the most interesting program collections are on its way. The categories include full-length movies, TV shows, and documentaries and much more.

    ReplyDelete
  35. Toll-free Helpline Number available 24*7*365 at your service for any of the HP hardware or software related issues and get the result-oriented services from the HP Technical Support team


    how to install hp driver and software

    ReplyDelete