Job Shop Scheduling: Shifting Bottleneck

Topics: algorithm
May 2, 2010 at 8:26 PM


I'm currently looking into quick graph because I need to implement Job Shop Scheduling. I have been researching and found the shifting bottleneck algorithm very promising. As I'm not really proficient in math and search algorithm I wanted to ask you guys if shifting bottleneck would fit into my problem domain and how this could be achieved which quickgraph?

I have a number of machines which need to manufacture individual pieces. Pieces are describe by a meta job description. It is possible to define priority on individual jobs. Each jobs needs a number of tools for the manufacturing process which is either present on a machine or not. Machines can be "bound" together into a resource group which describes what kind of pieces can be manufactured on the machine. For example when manufacturing LEGO parts there could be a resource group L-types and I-types (speaking of the form of the lego part). A manufacturing plant could for example have 3 L-Type machines and 2 I-type machines.

The scheduling algorithm needs to calculate an optimal scheduling of work on the machines such that the machines are always occupied. The restrictions or the costs traveling from workpiece to workpiece could be the priority, the availability of the tools necessary to manufacture on the machine etc.

Any ideas?