I was recently having a discussion with a friend when they brought up a new problem they were looking into. He asked me if it was a good candidate for Mathematical Planning and I said, “Absolutely!” I am abstracting away the specific domain, but this is the essence of the problem.
There are a set of machines which can process jobs. The jobs are of different types and sizes. There are three jobtypes: A, B, and C. Each machine has different jobtypes that it can process. Some machines can process any jobtype while other machines can only work on one or two. At the beginning of the day, we are given a set of jobs to assign to the machines. We want to assign jobs to machines such that a) the machines are evenly loaded and b) we minimize the number of different jobtypes each machine must process.
An ideal plan would have each machine with the same amount of work and only processing a single jobtype. The reason we want a machine to only process a single jobtype is to minimize the waste associated with changing between jobtypes. Switching between jobtypes is fast, it just creates unwanted waste. Let’s start with creating a small domain model and generate some example data.
Note: You can find the full code example for this post here
A Domain for Job Assignments
Based on the description there are some clear types that we need to define: Machine
, Job
, and JobType
.


I like to override the ToString
method because the ConstraintBuilder
and DecisionBuilder
in Flips
use ToString
for the naming of constraints and decisions. JobType
is a straightforward Discriminated Union with three different cases A
, B
, and C
. Job
has an Id
field for identifying a particular Job
, a JobType
which describes the type of job that it is, and the Size
.
The Machine
type has an Id
field and a JobTypes
field. The JobTypes
field is a Set
of JobType
. This represents the jobs the Machine
can process.
We now want to setup some data for us to be able to play with. These will be the parameters which will help us generate random data for us to work with.


jobTypes
is an Array
which holds each of the possible JobType
cases. We will use this to create random jobs. The jobTypeSets
value is an Array
of Set<JobType>
. These are the possible values for the JobTypes
field of Machine
that we will use for generating random machines. For this example, we will have 20 jobs and 5 machines to assign them to. minJobSize
will control how small a job can be and maxJobSize
will determine how large. The maxWorkDifference
parameter will determine how different the loading of machines that we will allow.
We now create some convenience functions for generating random data. We will also add a function for looking up a key in a Map
but returning a default value when the key is not present.


We can now generate a random set of jobs and machines to work with.


Formulating the Problem
Now that we have some data to work with, we can get to formulating our model. Let’s go ahead and open Flips
. I love working with VS Code, Ionide, and .fsx
files for this kind of exploration. The new #r "nuget: <library name>"
syntax for using Nuget packages has been a game changer.


We want to create a Map
where they key is a JobType
and the value is a list of Job
that are of that type. This will make it easy for us to lookup the Job
s of a given type.


We now want to create a 1dimensional SliceMap
where the 'key
is a Job
and the 'value
is the size of the job. This will make it easy for us to sum up how much work has been assigned to a Machine
.


Now let’s create the set of Decision
s which will represent us assigning a Job
to a Machine
. We will store this in a 3dimensional SliceMap
keyed by the Machine
, the JobType
, and finally the Job
. The reason we key by the JobType
will become apparent later in the formulation. We will use a Boolean
decision where 1.0
indicates that we are assigning the Job
to a Machine
and 0.0
indicates not.


Now that we have these decisions which represent assigning a job to a machine, we can formulate our first and most obvious constraints. Each job must be assigned to one machine. For each job we say that the sum of assignments
for a given job
across all machines and all jobtypes must be 1.0
. This forces the solver to find a solution where each job
is assigned once.


Constraint or Objective?
We now come to an interesting question. Our original problem statement said that we want to minimize the number of different jobtypes a machine must deal with. Ideally each machine only works on a single jobtype. We also said that we want the machines evenly loaded. When I was chatting with my friend I dug into this point. Which one of these objectives is more important because we can’t optimize for both? This is where a modeler needs to work with their client to help them understand what the most important thing is truly.
In our case, minimizing the different jobtypes for machines was the most important, so long as the machines were not too unevenly loaded. This means that the goal for even loading becomes a constraint and the objective remains the minimization of different jobtypes for machines. We will explore variations of this problem in future posts.
Controlling the Difference in Loading
Now that we have decided that even machine loading needs to be a constraint, we need to create some Decision
s to control for it. We will create two Decision
s. One will represent the value of the machine with the greatest loading and the other the machine with the least loading.


Now, we want to create a Constraint
which states that the difference between these two values is not greater than the maximum allowed difference.


Okay, that’s great but will it do anything? Right now, there is nothing that forces the maxWork
decision to be equal to the loading of the most heavily loaded machine. There’s also nothing which forces minWork
to be equal to the loading of the most lightly loaded machine. The solver could set the values to 0.0
and be done with it. We need to create some constraints which will force maxWork
and minWork
to take on the loading of the most heavily and most lightly loaded machines.
Let’s create some constraints which state that the value of the maxWork
decision must be greater than or equal to the loading of all the machines. This will force it to be a value above or equal to the maximum loading.


We do a similar thing for the minWork
decision. In this case we will say that minWork
must be less than or equal to all the loadings of the machines.


maxWorkConstraints
and minWorkConstraints
will force maxWork
and minWork
to take on the values of the most heavily and lightly loaded machines respectively. maxWorkDifferenceConstraint
states that the difference between maxWork
and minWork
must be within the permissable bounds. All together these constraints will prevent the solver from distributing jobs across machines unevenly.
Minimizing the JobTypes for Machines
We now need to quantify how many different jobtypes are being assigned to machines. To do this, we will create a set of Boolean
decisions which will indicate whether we have decided to assign a job of a given jobtype to a machine. We will store these in a 2dimensional SliceMap
where the keys are the Machine
and the JobType
. 1
will represent that we have decided to assign a given JobType
to a Machine
. 0
will indicate that we did not. I like to think of this as “turning on” or “turning off” the jobtype for the machine. We will call these decisions the setups
decisions.


We now want to create some constraints which will force the solver to turn on the decision to allow the assigning of a jobtype to a machine. We will do this by saying that the sum of jobs of a given jobtype must be less than or equal to our decision to assign that jobtype to the machine multiplied by a large number. This will force the solver to “turn on” the jobtype for the machine. In our case the “large number” will be the total number of jobs.


We can now create an expression which represents the number of different jobtypes that are assigned to machines.


We use this expression to create our objective of minimizing the number of different jobtypes assigned to a machine.


We can now compose our model from the parts that we have created.


We now ask the solver to find us a solution.


If you want to see the code that prints out the results you can check it out here. This is the solution the solver found.


Next Steps
We’ve only begone to explore this model. There are quite a few variations and nuances that I will dive into in the posts to come. In the future we will discuss adding machine capacity and dealing with infeasible models. We will also explore adding restrictions on just how much of a jobtype can be assigned to a given machine. Some jobtypes cause more wear and therefore we do not want too much assigned to a single machine. We will also look at needing to replan part way through the day and look at scheduling over a longer time horizon.
These types of scheduling problems are common and therefore it’s valuable for us to explore how we can play and tweak with this model to make it suit our needs. Feel free to reach out with questions and ideas for modeling challenges in the future!
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.