Calculating minimum processing time for many recipes and tools

Question

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.

Answer 1

This kind of problem is likely to be NP-complete.

If you want an exact solution (the exact optimum), and the problem isn't too large, I would suggest formulating this as an instance of integer linear programming. You'll probably have variables like $x_{t,q,r}$, which is 1 if recipe $r$ is running on equipment $q$ at time $t$.

Alternatively, you could seek an approximate solution. It might be possible to adapt heuristics for bin packing to your situation; see e.g., https://en.wikipedia.org/wiki/Bin_packing_problem.

Lastly, the DB/SQL stuff is a distraction. No, you definitely would not solve this with PQ/SQL queries. Instead, you'd export the data from the database to a custom program you've written to find the optimal solution.