I originally asked this question on StackOverflow but a comment was made to the effect that my problem pertains to Job Shop Scheduling and that it was more of a comp sci problem than a programming problem.
It's the first time I've come across this topic and I've tried researching with a view to solving my problem below, but to no avail - I am not an academic. Can anybody advise how I should be approaching this problem, or which algorithms I should research to help?
My goal is to develop a capacity model for the manufacturing facility at work. I have a process monitoring application where I need to determine tool capacity requirements based on a loading forecast. I have a selection of "Equipment" that process the product using "Recipes".
The key "rules" for the interaction are:
- A recipe can be run on one or more equipment
- An equipment can run one or more recipes
- An equipment can only run one recipe at a time
- Time taken to run a recipe is specific to the equipment / recipe combination.
So, for a given set of equipment, recipes, tool-to-recipe relationships & processing times, I need to determine what the quickest possible processing time is for a given loading.
The table below shows a possible interaction, where the numbers in the columns are process units (e.g. hours). I've assumed processing time is the same for each tool per recipe (despite the fourth point, above).
| Eqp#1 | Eqp#2 | Eqp#3 | Eqp#4 | Eqp#5 -------+---------+---------+---------+---------+------- Rcp#1 | 5 | | | 5 | Rcp#2 | 6 | | | 6 | 6 Rcp#3 | 3 | | 3 | | 3 Rcp#4 | | 4 | 4 | | Rcp#5 | 2 | 2 | 2 | 2 | 2
Assuming the following recipe quantities, is it possible to, and if so, how would one determine the minimum total processing time for the processes?
Rcp#1 = 10 Rcp#2 = 8 Rcp#3 = 2 Rcp#4 = 6 Rcp#5 = 8
I can plot this out graphically, and show that stacking Rcp#2 on Eqp#5 six times (and other recipes elsewhere) gives me the minimum process time, but I can't seem to arrive at this programatically. The table below shows a process matrix showing, per hour, which tool is running which recipe, showing a min process time of 36 hours (I hope it makes sense!)
| Equipment Hour | #1 | #2 | #3 | #4 | #5 ------+------+------+------+------+------ 1 | 1 | 4 | 3 | 1 | 2 2 | 1 | 4 | 3 | 1 | 2 3 | 1 | 4 | 3 | 1 | 2 4 | 1 | 4 | 3 | 1 | 2 5 | 1 | 4 | 3 | 1 | 2 6 | 1 | 4 | 3 | 1 | 2 7 | 1 | 4 | 4 | 1 | 2 8 | 1 | 4 | 4 | 1 | 2 9 | 1 | 4 | 4 | 1 | 2 10 | 1 | 4 | 4 | 1 | 2 11 | 1 | 4 | 4 | 1 | 2 12 | 1 | 4 | 4 | 1 | 2 13 | 1 | 4 | 4 | 1 | 2 14 | 1 | 4 | 4 | 1 | 2 15 | 1 | 4 | 5 | 1 | 2 16 | 1 | 4 | 5 | 1 | 2 17 | 1 | 5 | 5 | 1 | 2 18 | 1 | 5 | 5 | 1 | 2 19 | 1 | 5 | 5 | 1 | 2 20 | 1 | 5 | 5 | 1 | 2 21 | 1 | 5 | 5 | 1 | 2 22 | 1 | 5 | 5 | 1 | 2 23 | 1 | 5 | | 1 | 2 24 | 1 | 5 | | 1 | 2 25 | 1 | | | 1 | 2 26 | 2 | | | 2 | 2 27 | 2 | | | 2 | 2 28 | 2 | | | 2 | 2 29 | 2 | | | 2 | 2 30 | 2 | | | 2 | 2 31 | 2 | | | 2 | 2 32 | | | | | 2 33 | | | | | 2 34 | | | | | 2 35 | | | | | 2 36 | | | | | 2 37 | | | | | 38 | | | | | 39 | | | | | 40 | | | | |
My real world example is more complex than this, I've just (hopefully) supplied enough information to explain what I'm trying to achieve. For example, I have tens of equipments running tens of different recipes.
Thanks for reading and for any advice.