ojAlgo Linear Optimization - Preventing work shift overlaps?

Question

I'm kind of new to linear optimization, and I want to apply it to classic scheduling problems. For staffing problems I'm not quite clear how to declare functions that capture the concept of a "shift" being taken.

I'm using ojAlgo which has been pretty awesome so far. Here is my contrived little problem I came up with:

SCENARIO:
You have three drivers to make deliveries.

Driver 1 costs $10 / hr
Driver 2 costs $12 / hr
Driver 3 costs $14 / hr


Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Operating day is 6:00 to 22:00, which must be fully covered.

Driver 2 cannot work after 11:00.

Create a schedule that minimizes the cost. 





Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X

Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
10Te1 - 10Te2 + 12Te2 - 12Ts2 + 14Te3 - 14Ts3

Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11

Here is the Kotlin code I put together. I found it easier for each Driver instance to take care of as many of its function inputs as possible (which yielded some interesting patterns with OOP).

import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable


fun main(args: Array<String>) {


    val model = ExpressionsBasedModel()

    val drivers = sequenceOf(
            Driver(1, 10.0, model),
            Driver(2, 12.0, model),
            Driver(3, 14.0, model)
    ).map { it.driverNumber to it }
     .toMap()


    model.addExpression("EnsureCoverage")
            .level(16.0)
            .apply {
                drivers.values.forEach {
                    set(it.shiftEnd, 1)
                    set(it.shiftStart, -1)
                }
            }

    model.addExpression("Driver2OffAt11")
            .upper(11)
            .set(drivers[1]!!.shiftEnd, 1)

    val result = model.minimise()

    println(result)
}

data class Driver(val driverNumber: Int,
                  val rate: Double,
                  val model: ExpressionsBasedModel) {

    val shiftStart = Variable.make("${driverNumber}shiftStart").weight(rate).lower(6).upper(22).apply(model::addVariable)
    val shiftEnd = Variable.make("${driverNumber}shiftEnd").weight(rate).lower(6).upper(22).apply(model::addVariable)

    init {
        model.addExpression("${driverNumber}shiftLength")
                .lower(4.0)
                .upper(6.0)
                .set(shiftEnd, 1)
                .set(shiftStart, -1)
    }

}

But I'm getting this output indicating all three drivers were assigned at 6:00AM and to work simultaneously. Driver 1 from 6:00-11:00, Driver 2 from 6:00-12:00, and Driver 3 from 6:00-11:00.

OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]

I don't want them to overlap. I want only one driver at a time to be assigned, and I want the entire working day to be covered. How do I express the binary state of time being occupied already?

Here is an example of a similar problem [[link](http://yetanothermathprogrammingconsultant.blogspot.com/2017/03/employee-scheduling-iv-direct.html)]. It has links to alternative formulations and approaches. — Erwin Kalvelagen, Oct 19 '17 at 08:39
That's a modelling question not in anyway specific to ojAlgo. If you google for scheduling and/or assignment problems you'll find there is a lot to read. — apete, Oct 19 '17 at 11:21

tmn · Answer 1 · 2017-10-20T15:50:26.200

It looks like I got this up and running, thanks to Erwin's help in the Math section. The key was a binary switch.

Here is the result. Driver 1 was scheduled 16:00-22:00, Driver 2 6:00-10:00, and Driver 3 10:00-16:00.

import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable

// declare model
val model = ExpressionsBasedModel()

// parameters
val operatingDay = 6..22
val operatingDayLength = operatingDay.endInclusive - operatingDay.start
val allowableShiftSize = 4..6

// Map drivers by their ID for ad hoc retrieval
val drivers = sequenceOf(
        Driver(driverNumber = 1, rate =  10.0),
        Driver(driverNumber = 2, rate = 12.0, availability = 6..11),
        Driver(driverNumber = 3, rate =  14.0)
    ).map { it.driverNumber to it }
     .toMap()


fun main(args: Array<String>) {

    drivers.values.forEach { it.addToModel() }

    val result = model.minimise()

    println(result)
}

// Driver class will put itself into the Model
data class Driver(val driverNumber: Int,
                  val rate: Double,
                  val availability: IntRange? = null) {

    val shiftStart = Variable.make("${driverNumber}shiftStart").weight(rate).lower(6).upper(22).apply(model::addVariable)
    val shiftEnd = Variable.make("${driverNumber}shiftEnd").weight(rate).lower(6).upper(22).apply(model::addVariable)

    fun addToModel() {

        //constrain shift length
        model.addExpression("${driverNumber}shiftLength")
                .lower(allowableShiftSize.start)
                .upper(allowableShiftSize.endInclusive)
                .set(shiftEnd, 1)
                .set(shiftStart, -1)

        //ensure coverage of entire day
        model.addExpression("EnsureCoverage")
                .level(operatingDayLength)
                .apply {
                    drivers.values.forEach {
                        set(it.shiftEnd, 1)
                        set(it.shiftStart, -1)
                    }
                }

        //add specific driver availability
        availability?.let {
            model.addExpression("${driverNumber}StartAvailability")
                    .lower(it.start)
                    .upper(it.endInclusive)
                    .set(shiftStart, 1)

            model.addExpression("${driverNumber}EndAvailability")
                    .lower(it.start)
                    .upper(it.endInclusive)
                    .set(shiftEnd, 1)
        }

        //prevent shift overlap
        drivers.values.asSequence()
                .filter { it != this }
                .forEach { otherDriver ->

                    val occupied = Variable.make("${driverNumber}occupyStatus").lower(0).upper(1).integer(true).apply(model::addVariable)

                    model.addExpression("${driverNumber}to${otherDriver.driverNumber}Binary1")
                            .upper(0)
                            .set(otherDriver.shiftEnd, 1)
                            .set(occupied, operatingDayLength * - 1)
                            .set(shiftStart, -1)

                    model.addExpression("${driverNumber}to${otherDriver.driverNumber}Binary2")
                            .upper(operatingDayLength)
                            .set(shiftEnd, 1)
                            .set(occupied, operatingDayLength)
                            .set(otherDriver.shiftStart, -1)
                }
    }
}

OUTPUT:

OPTIMAL 936.0 @ [16.0, 22.0, 6.0, 10.0, 10.0, 16.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0]

ojAlgo Linear Optimization - Preventing work shift overlaps?

1 Answers1