Matthew Crews
Blog About
Matthew Crews

Scheduling Jobs for Maximum Efficiency - Part 3

I’ve continued to consult with my friend on the job assignments problem that I have been discussing in post 1 and post 2. At first, he was excited about what we had come up with but I knew there were likely more complexities that had not been uncovered yet. He went back to the client and came away with some new information. He told me, “Mathew, it turns out that machines have limited capacity. We have to limit how much work is assigned to them.”

“Not a problem,” I respond. I tell me friend that it is straightforward to add constraints to the model which limit how much work is assigned to a machine. Let me walk you through how I update the model we created in post 1 and post 2 to take this new limitation into consideration.

Note: The full code for this post can be found here

Machine Capacity Constraints

The first thing we need to know is how much capacity machines have. My friend tells me that they are limited to 24.0 units of work. Our jobs are coming in sizes of 1, 2, or 3. Let’s create a constraint for each machine which states that the total loading cannot exceed this amount.

1
2
3
4
5
6
7
8
9

// Limit on how much work a machine can be assigned
let maxMachineCapacity = 24.0

// Machines have a limited capacity
let maxMachineCapacityConstraints =
    ConstraintBuilder "MachineCapacity" {
        for machine in machines ->
            sum (assignments[machine, All, All] .* jobSizes) <== maxMachineCapacity
    }

Remember, machines is the list of machines available for us to assign work to. We are looping through each machine and creating a constraint which says the sum of the work assigned to the machine cannot exceed the max capacity, maxMachineCapacity. assignments is a SliceMap indexed by machine, job-type, and job where the value is a Boolean decision. 1 indicates that we are assigning the job to the machine and 0 indicates that we are not. The notation assignments.[machine, All, All] is a “slice” which says, “Give me the assignments for this machine across all job-types and jobs.” jobSizes is another SliceMap where the key is a job and the value is the size of the job. We multiply the decisions by the size of the job using the Hadamard Product .*.

Now that we have created some capacity constraints for the machines, let’s add them to our model and try to solve.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Compose the model
let model =
    Model.addObjective minSetupsObjective
    |> Model.addConstraints maxWorkConstraints
    |> Model.addConstraints minWorkConstraints
    |> Model.addConstraint maxWorkDifferenceConstraint
    |> Model.addConstraints setupConstraints
    |> Model.addConstraints jobsAssignmentConstraints
    |> Model.addConstraints maxJobTypeDConstraints
    |> Model.addConstraints maxMachineCapacityConstraints // <- New constraints

// Give the solver plenty of time to find a solution
let settings = { Settings.basic with MaxDuration = 60_000L }

let result = Solver.solve settings model

We’ve cleaned up some of our code from earlier posts. All the solving is now abstracted behind the Scheduler.schedule function. It returns a new type if the solver can find a solution, MachineAssignments. This type contains a list machines and the jobs that are assigned to it.

1
2
3
4
5
6

type MachineAssignment = {
    Machine : Machine
    Jobs : Job list
}

type MachineAssignments = MachineAssignments of MachineAssignment list

We now call Scheduler.schedule to see if we can find a plan which fits our requirements.

1
2

let scheduleResult = 
    Scheduler.schedule maxWorkDifference maxJobTypeDPercentage maxMachineCapacity jobs machines

We would like to have the script print out some nice output. We created a function, Printer.MachineAssignments.print, which provides nice clean output if we are able to solve the problem. Let’s call this function in the case that our solver successfully solved.

1
2
3

match scheduleResult with
| Result.Ok assignments -> Printer.MachineAssignments.print assignments
| Result.Error msg -> printfn $"{msg}"

What do we get?

1
2
3
4
5

> match scheduleResult with
- | Result.Ok assignments -> Printer.MachineAssignments.print assignments
- | Result.Error msg -> printfn $"{msg}";;
Unable to solve
val it : unit = ()

Uh oh, the solver failed to find a solution to our problem. What went wrong?

When the Solver Fails

The solver was not able to find a solution. It is reporting “Unable to solve”. How can this be? We were able to solve this problem before. What has changed? Let’s think about it. We have added constraints which state that a machine cannot be overloaded. Overloaded in this case means anything over 24.0. Previously we were loading the machines up to 28.0, 29.0, or 30.0. We need to introduce a new concept to our vocabulary, “Infeasible”. Infeasible is a term you will find frequently in the optimization literature. In this context what it means is that there is no solution to the problem. Our problem is overly constrained. What other constraints combined with our new machine capacity constraints could be causing this problem?

I’ll give you a hint, it’s the machine assignment constraints. Previously we defined a set of constraints, jobsAssignmentConstraints, which stated that every job must be assigned to a machine. In this new world though, that is not possible. There is simply too much work given the capacity of the machines. Therefore, the solver cannot find a solution. This is when we need to go back to the business and discuss priorities. What is truly the most important thing?

In this scenario, I was able to discuss the problem with my friend. We agreed that the first priority is to fully utilize the machines. After that, we want to minimize the number of different jobs that a machine processes. This is an example of multi-objective optimization.

The idea is that there is a series of objective in order of importance. You iteratively solve for each objective. The mechanics of how this works will need to wait for another post. Fortunately, multi-objective models are simple to express with Flips. We add the objectives to the model in the order of their priority.

Mult-Objective Formulation

We need to create a new objective for maximizing the loading of machines. Let’s do that by first creating an expression which evaluates the total machine loading.

1
2

// Maximize Utilization expression
let maxUtilizationExpression = sum (assignments .* jobSizes)

The maxUtilizationExpression expression evaluates just how much we we have assigned to all machines. We can use this to create an objective.

1
2

let maxUtilizationObjective =
    Objective.create "MaxUtilization" Maximize maxUtilizationExpression

This objective states that we would like to maximize the loading of the machines. We will use this new objective as the first objective of our model. We will also omit the jobsAssignmentConstraints that existed before since we no longer anticipate being able to assign all of the jobs to machines. Let’s compose our new model.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// Compose the model
let model =
    Model.create maxUtilizationObjective // First priority objective
    |> Model.addObjective minSetupsObjective // Second priority objective
    |> Model.addConstraints maxWorkConstraints
    |> Model.addConstraints minWorkConstraints
    |> Model.addConstraint maxWorkDifferenceConstraint
    |> Model.addConstraints setupConstraints
    |> Model.addConstraints maxJobTypeDConstraints
    |> Model.addConstraints maxMachineCapacityConstraints

Note that we create the initial model using the maxUtilizationObjective objective then add the minSetupsObjective to the model. This means that the solver will find a solution which maximizes the machine utilization first and then search for a solution that minimizes the number of different job-types. Let’s try to solve this and see what we get. This code comes from the Scheduler.schedule function. If the solver is successful, it returns a Result.Ok with the machine assignments. If it fails to find a solution, it returns a Result.Error with “Unable to solve” as the message.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Give the solver plenty of time to find a solution
let settings = { Settings.basic with MaxDuration = 60_000L }

let result = Solver.solve settings model

match result with
| Optimal solution -> 
    getMachineAssignments solution assignments
    |> MachineAssignments
    |> Result.Ok
| _ -> Result.Error "Unable to solve"

If we use our pretty printer function, we get the following.

1
2
3
4
5
6

let scheduleResult = 
    Scheduler.schedule maxWorkDifference maxJobTypeDPercentage maxMachineCapacity jobs machines

match scheduleResult with
| Result.Ok assignments -> Printer.MachineAssignments.print assignments
| Result.Error msg -> printfn $"{msg}"

I use the Specture.Console library for printing these tables to the console.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Machine Loading:
┌─────────┬────────────┬─────────────────────┬────────────────────┐
│ Machine │ Total Work │ Percent Type D Work │ Distinct Job Count │
├─────────┼────────────┼─────────────────────┼────────────────────┤
│ 1       │ 24         │ 0.00%               │ 1                  │
│ 2       │ 24         │ 0.00%               │ 1                  │
│ 3       │ 24         │ 0.00%               │ 1                  │
│ 4       │ 24         │ 0.00%               │ 1                  │
│ 5       │ 24         │ 0.00%               │ 1                  │
└─────────┴────────────┴─────────────────────┴────────────────────┘

We see that the solver is filling up each machine with the maximum capacity available. Each machine is also only processing a single job-type. None of job-type D is being processed on any of these machines, interesting. Is that what we want? Maybe we want a policy which prioritizes some of the jobs above others? Maybe when work carries over from the previous day, it needs to be prioritized over new work coming in?

These are some interesting questions that we will explore in the next post! I hope you are enjoying this series and it is giving you insight into how Mathematical Planning can be used to deal with many different scheduling challenges. More posts to come!

Please send me an email at matthewcrews@gmail.com if you have any questions and subscribe so you can stay on top new posts and products I am offering.