0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you think your problem is more relevant on CS than stackoverflow, please delete it from SO. Then you should refine your question. Focus on the job shop scheduling, there is no need to talk about DB, SQL and queries. $\endgroup$ – Vince Apr 16 at 11:21
  • 1
    $\begingroup$ Your problem is likely to be a "bin packing", and is indeed NP-complete. Are you interested with an heuristic method ? If there is not several order of magnitude in the range of process times (like $1$ for an item and $10^3$ for another), there are indeed very good approximations. $\endgroup$ – Vince Apr 16 at 14:48
  • $\begingroup$ Regarding the process times, they're not orders of magnitude different. They may range from 1 hour to 12 hours, but that's at the extremes. Pointers for good approximation methods greatly appreciated. $\endgroup$ – Bob Apr 16 at 16:29
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.