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 job-type 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 job-type, let’s call it job-type 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 job-type 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 job-type 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 job-type 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, job-type A is the most difficult and therefore fewer machines are qualified. All machines are capable of job-type 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 job-type 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
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
To get the total amount of job-type D work assigned to the machine, we need to sub-select the
assignments SliceMap for the
JobType.D then elementwise multiply by the
jobSizes. We sum these values up to get the
totalWork is an expression which represents the total amount of work assigned to the
jobTypeDWork represent the total amount of job-type D assigned to the
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 job-type D,
maxJobTypeDPercentage. This constraint will limit just how much work of job-type 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 real-world 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 job-type D. I would say that we have a success!
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 email@example.com if you have any questions and subscribe so you can stay on top new posts and products I am offering.