Article ID: | iaor20073237 |
Country: | Netherlands |
Volume: | 150 |
Issue: | 1 |
Start Page Number: | 31 |
End Page Number: | 46 |
Publication Date: | Mar 2007 |
Journal: | Annals of Operations Research |
Authors: | Alfieri Arianna, Nicosia Gaia |
Keywords: | networks: path |
In this paper, the problem of finding the minimum cost flow line able to produce different products is considered. This problem can be formulated as a shortest path problem on an acyclic di-graph when the machines graph associated with each product family is a chain or a comb. These graphs are relevant in production planning when dealing with pipelined assembly systems. We solve the problem using A* algorithm which can be efficiently exploited when there is a good estimate on the value of an optimal solution. Therefore, we adapt a known bound for the Shortest Common Supersequence problem to our case and show the effectiveness of the approach by presenting an extensive computational experience.