Article ID: | iaor1998895 |
Country: | United Kingdom |
Volume: | 35 |
Issue: | 5 |
Start Page Number: | 1413 |
End Page Number: | 1430 |
Publication Date: | May 1997 |
Journal: | International Journal of Production Research |
Authors: | MacGregor Smith J., Gosavi H.D. |
Keywords: | queues: theory |
The optimal routeing problem of maximizing system throughput in series-parallel networks with finite buffers is studied in this paper. The problem is extremely difficult to solve since closed form expressions are not easily constructed for throughput in finite networks. A piece-wise linear upper bound on the throughput of a tandem network is used to develop a throughput approximation in series-parallel networks. Based on this approximation we are able to specify a sub-optimal range for routeing probabilities at each junction in the network as a function of the arrival rate to this junction. We also specify a unique value for the routeing probability at each junction, independent of the arrival rate to that junction. We then construct an O(N) algorithm to analyse general series-parallel networks with more than one junction and specify the sub-optimal routeing probabilities at each junction.