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 job-types: A, B, and C. Each machine has different job-types that it can process. Some machines can process any job-type 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 job-types each machine must process.
An ideal plan would have each machine with the same amount of work and only processing a single job-type. The reason we want a machine to only process a single job-type is to minimize the waste associated with changing between job-types. Switching between job-types 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:
I like to override the
ToString method because the
ToString for the naming of constraints and decisions.
JobType is a straightforward Discriminated Union with three different cases
Job has an
Id field for identifying a particular
JobType which describes the type of job that it is, and the
Machine type has an
Id field and a
JobTypes field. The
JobTypes field is a
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
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
Jobs of a given type.
We now want to create a 1-dimensional
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
Now let’s create the set of
Decisions which will represent us assigning a
Job to a
Machine. We will store this in a 3-dimensional
SliceMap keyed by 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
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 job-types 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 job-types a machine must deal with. Ideally each machine only works on a single job-type. 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 job-types 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 job-types 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
Decisions to control for it. We will create two
Decisions. 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
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.
minWorkConstraints will force
minWork to take on the values of the most heavily and lightly loaded machines respectively.
maxWorkDifferenceConstraint states that the difference between
minWork must be within the permissable bounds. All together these constraints will prevent the solver from distributing jobs across machines unevenly.
Minimizing the Job-Types for Machines
We now need to quantify how many different job-types 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 job-type to a machine. We will store these in a 2-dimensional
SliceMap where the keys are the
Machine and the
1 will represent that we have decided to assign a given
JobType to a
0 will indicate that we did not. I like to think of this as “turning on” or “turning off” the job-type for the machine. We will call these decisions the
We now want to create some constraints which will force the solver to turn on the decision to allow the assigning of a job-type to a machine. We will do this by saying that the sum of jobs of a given job-type must be less than or equal to our decision to assign that job-type to the machine multiplied by a large number. This will force the solver to “turn on” the job-type 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 job-types that are assigned to machines.
We use this expression to create our objective of minimizing the number of different job-types 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.
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 job-type can be assigned to a given machine. Some job-types cause more wear and therefore we do not want too much assigned to a single machine. We will also look at needing to re-plan 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 email@example.com if you have any questions and subscribe so you can stay on top new posts and products I am offering.