Best algorithm for finding minimum installation cost of multiple Quality Control stations in a complex network

A company manufactures several products, using multiple machines in parallel at various sequential stages of production, and a new quality control (QC) system is to be implemented. The cost of installing each QC station varies depending on location, and can be installed at any point along the production line, either incorporated within a specific machine, or between sequential stages of production. Basically the problem requires optimizing the placement of QC stations so as to ensure that each item manufactured will pass through at least one QC station. What algorithm is most appropriate to find the minimum number of QC stations, and more importantly, the minimum cost of installation of the entire QC system? I will still have to resolve the problem, but at least if I have an idea where to start, I might have a chance of finishing it! :) Thanks!Best algorithm for finding minimum installation cost of multiple Quality Control stations in a complex network
Optimisation problems are normally done using partial derivatives, however you're problem is discreet so it will be handled differently. First make a map of the network lets say with coloured lines to represent the individual paths from the beginning to the end of the manufacturing process and nodes where they intersect, i.e. nodes that represent each machine. Then there are multiple ways to run the algorithm. For the case of minimum number search through the nodes to see if there is one that bundles all the lines through it if not start looking for pairs that would have all the lines going through one or the other of the nodes and so on until you find a solution. Unless visually it is a simple graph you will need a computer to do the processing.


The problem with a cost assigned is more difficult. In this case each node has a value associated with it. In this case generate an ordering from cheapest to dearest of the possible costs of selecting any number of nodes. The test each of these in succession until you find one that corresponds to having all the lines pass through at least one of the selected nodes associated with that particular cost.


In knowing details of the way in which the graph would look or the cost for certain locations it may be possible to modify the algorithm so it runs quicker, but this should do it for the information given.Best algorithm for finding minimum installation cost of multiple Quality Control stations in a complex network
A mod. made it run faster.ty..
.............