I am looking for a solution that i know exists already in the field of "Operational Research"... I Just can't put my finger on the name of the thing. An heuristic to solve a very common and simple resource management problem.
I am currently in the process of making a small ERP software for a local factory. The factory produces complex steel structures. They produce one structure per contract and on an "on demand" basis… so they have the challenge of taking orders only if they have enough resources to do the jobs assuming a predefined delivery date. In fact, they will never refuse a contract but if they don't have enough resources left to do the job, they need to know when and where the bottle neck is to occur and how much overtime they will have to allow to meet the demand. (Overtime or delaying the delivery of other projects.)
THE PROBLEM:
The production cycle is always the same and quite simple. A finite sequence of no more than 3 steps:
- making detailed drawings of the steel parts to be cut
- cutting the parts
- welding the parts
That's it… Also, they have well known capacities for each of the three steps…
- The only person doing the CAD work can only draw the equivalent of X elements per day
- The cutting machine can only cut Y parts per day
- The welders can only weld Z parts per day
A bottleneck can occur at any of the three production steps.
Each time they work on a prospect, they can produce pretty good estimates of what the contract involves in terms of efforts and hours needed for the drawing, cutting and welding steps.
THE GOAL:
I am looking for an algorithm that can be used to do a little more than just tell, "Yes, we can do it" or "No, we already have too much contracts and would not be able to meet the delivery date".
Since the factory will never say "No" to a client, the system must place the order in the software's calendar and distribute the effort for all three steps. (i.e. CAD, Cutting and Welding) Then, if the factory is to lack resources to meet the delivery date, the system must show the work load at each production steps displaying the dates when, for instance, the cutting machine will have to work more than 8 hours. This information will then be used by the managers to allow overtime or to delay some other projects.
Of course, I am looking for the algorithm that will distribute the workload of a new contract based on the previous distribution made for the other older contracts. And I am not looking to optimise the whole thing… just plain simple MS Project/GanttChart like placement of the tasks.
Is this problem equivalent to the "Job Shop Scheduling" problem ?... I recall seeing a solution for this same problem a couple of years ago while working on a genetic algorithm based system? I just can't remember how it was called.
I already have a pretty good idea of what the algorithm should do but i also have the feeling that i could be re-inventing the wheel... this is a very simple problem that is quite common so the approach to adopt should be well known and well documented...