In my previous post I introduced a scheduling problem where I needed to assign jobs to machines to achieve the maximum efficiency. We say efficiency is calculated as the number of times a machine must change the jobtype it is working on. I want to continue exploring this problem by adding some nuance.
Note: Full code for this post can be found here
Not Too Many Bad Jobs
As my conversation continued with my friend regarding this problem a new constraint came up. It turns out there is a fourth jobtype, let’s call it jobtype D, that can cause significant wear on a machine if it is run for too long. He wanted to add a constraint to the problem which would limit that amount of jobtype D assigned to any given machine. In his case, he wanted a machine to have no more than 50% of the total work assigned to it to be of jobtype D. Fortunately this is a relatively simple update to our model.
Refactoring the Domain
The great thing about F# is that it is easy to refactor our domain. In our case the Job
type and the Machine
type don’t need to change. What does need to be updated is the JobType
type. We will add another case to the discriminated union to represent jobtype D. I have also decided to do some refactoring and clean up how the code is organized. We are also going to move all the type definitions into their own Module.


Next, we need to adjust our data generation. Again, we are going to do some code cleanup and move all the code for generating random jobs and machines into its own module. We are adjusting two thing from the previous post. The jobTypes
Array had the new JobType
case. We are also going to adjust the jobTypeSets
. This is the possible job qualifications for a machine. In our new problem, jobtype A is the most difficult and therefore fewer machines are qualified. All machines are capable of jobtype D, even though it is not preferred.


Updating Our Model
I won’t go over all the model code that we created before. I am just going to show the new constraints that we need to add to the original formulation. One of the reasons I love Mathematical Planning is that it makes it relatively easy to tweak and update models over time. If the code is well organized, it’s trivial to turn features on and off. To add our limits on the amount of jobtype D that a machine has, let’s define a value which is the maximum percent of D allowed.


Now we want to create a constraint for each of our machines which says the the percent of the total work assigned to the machine is no more than this percentage. Fortunately, this is relatively easy with Flips.


Okay, let’s unpack this. We are using the ConstraintBuilder
Computation Expression to create a constraint for each machine
in machines
. We then calculate the total amount of work assigned to a machine
by using the assignments
SliceMap and selecting all the assignments for our machine
and performing elementwise multiplication, .*
, by the jobSizes
. We then sum that up to get the total amount of work assigned to the machine
. We store that expression in the totalWork
value.
To get the total amount of jobtype D work assigned to the machine, we need to subselect the assignments
SliceMap for the machine
and JobType.D
then elementwise multiply by the jobSizes
. We sum these values up to get the jobTypeDWork
expression. totalWork
is an expression which represents the total amount of work assigned to the machine
. jobTypeDWork
represent the total amount of jobtype D assigned to the machine
.
We can now create our constraint expression. We state that jobTypeDWork
must be less or equal to the totalWork
expression multiplied by the max allowed percentage of jobtype D, maxJobTypeDPercentage
. This constraint will limit just how much work of jobtype D that is allowed on the machine. That’s all we must do to accommodate this new restriction from my friend.
Unpacking the Results
The only other change my friend asked for was to increase the number of jobs up to 100 because it would be more represented of the size of the realworld problem. With that adjustment, we can now compose our new model with these new constraints included.


We setup our solver settings and attempt to solve.


We now inspect the result. We add a couple of functions for getting the job assignments for each machine and summarizing the total loading of the machines.


We then use these to analyze the result and print out what we found.


This will show the following results.


You can see that the machines are evenly loaded according to the maximum allowable difference and that no machine has more than 50% loading of jobtype D. I would say that we have a success!
Takeaways
We are only beginning to look at variations of this problem. Hopefully, what you have been able to observe was that it was simple to update our model code to add this new requirement my friend found. I think that is part of the beautify of Mathematical Planning. Updating and adjusting the logic can be simple. In our next post we are going to look at what happens when we add capacity for the machines and our problem becomes unsolvable!
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.