Topological network design of general, finite, multi-server queueing networks.

*(English)*Zbl 1175.90114Summary: The topological network design of general service, finite waiting room, multi-server queueing networks is a complex optimization problem. Series, merge, and split topologies are examined using an approximation method to estimate the performance of these queueing networks and an iterative search methodology to find the optimal buffer allocation within the network. The coefficient of variation is shown to be a significant factor in the buffer allocation for multiple servers in uniform and bottleneck server networks. Extensive computational results are included to illustrate the symmetries and asymmetries in the buffer patterns which emerge from the series, merge, and splitting topologies.

##### MSC:

90B22 | Queues and service in operations research |

90B10 | Deterministic network models in operations research |

PDF
BibTeX
XML
Cite

\textit{J. M. Smith} et al., Eur. J. Oper. Res. 201, No. 2, 427--441 (2010; Zbl 1175.90114)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Altiok, T.; Stidham, S., The allocation of interstage buffer capacities in production lines, IIE transactions, 15, 251-261, (1983) |

[2] | Baker, K.R.; Powell, S.; Pyke, D., Buffered and unbuffered assembly systems with variable processing times, Journal of manufacturing and operations management, 3, 200-223, (1990) |

[3] | Carrasco, J.A., Two methods for computing bounds for the distribution of cumulative reward for large Markov models, Performance evaluation, 63, 12, 1165-1195, (2006) |

[4] | Choi, D.W.; Kim, N.K.; Chae, K.C., A two-moment approximation for the \(\mathit{GI} / G / c\) queue with finite capacity, INFORMS journal on computing, 17, 1, 75-81, (2005) · Zbl 1239.90029 |

[5] | Conway, R.; Maxwell, W.L.; McClain, J.O.; Thomas, L.J., The role of work-in-process inventories in serial production lines, Operations research, 36, 229-241, (1988) |

[6] | Cruz, F.R.B.; Duarte, A.R.; van Woensel, T., Buffer allocation in general single-server queueing network, Computers & operations research, 35, 11, 3581-3598, (2008) · Zbl 1170.90361 |

[7] | Cruz, F.R.B.; van Woensel, T.; Smith, J.M.; Lieckens, K., On the system optimum of traffic assignment in \(M / G / c / c\) state-dependent queueing networks, European journal of operational research, 201, 183-193, (2010) · Zbl 1177.90089 |

[8] | Dallery, Y.; Gershwin, S.B., Manufacturing flow line systems: A review of models and analytical results, Queueing systems, 12, 1-2, 3-94, (1992) · Zbl 0782.90048 |

[9] | de Nitto Persone, V., Topology related index for performance comparison of blocking symmetrical networks, European journal of operational research, 78, 3, 413-425, (1994) · Zbl 0812.90051 |

[10] | Eklin, M.; Arzi, Y.; Shtub, A., Model for cost estimation in a finite-capacity stochastic environment based on shop floor optimization combined with simulation, European journal of operational research, 194, 1, 294-306, (2009) · Zbl 1158.90004 |

[11] | Gaver, D.; Shedler, G.S., Approximate models for processor utilization in multiprogrammed computer systems, SIAM journal of computing, 2/3, 183-192, (1973) · Zbl 0286.68034 |

[12] | Gaver, D.; Shedler, G.S., Processor utilization in multi-programming systems via diffusion approximations, Operations research, 21, 569-576, (1973) |

[13] | Gelenbe, E., On approximate computer system models, Journal of the ACM, 22, 2, 261-269, (1975) · Zbl 0322.68035 |

[14] | Harris, J.H.; Powell, S.G., An algorithm for optimal buffer placement in reliable serial lines, IIE transactions, 31, 287-302, (1999) |

[15] | Hildebrand, D., On the capacity of tandem server, finite queue, service systems, Operations research, 16, 72-82, (1968) · Zbl 0157.25401 |

[16] | Hillier, F.S.; Boling, R.W., Finite queues in series with exponential or Erlang service times: A numerical approach, Operations research, 15, 286-303, (1967) · Zbl 0171.16302 |

[17] | Hillier, F.S.; So, K.C., The effect of the coefficient of variation of operation times on the allocation of storage space in production line systems, IIE transactions, 23, 2, 198-206, (1991) |

[18] | Himmelblau, D.M., Applied nonlinear programming, (1972), McGraw-Hill Book Company New York · Zbl 0521.93057 |

[19] | Ho, Y.C.; Eyler, M.A.; Chien, T., A gradient technique for general buffer storage design in a production line, International journal of production research, 17, 6, 557-580, (1979) |

[20] | Jafari, M.A.; Shanthikumar, J.G., Determination of optimal buffer storage capacities and optimal allocation in multistage automatic transfer lines, IIE transactions, 21, 2, 130-135, (1989) |

[21] | Kerbache, L.; Smith, J.M., The generalized expansion method for open finite queueing networks, European journal of operational research, 32, 448-461, (1987) · Zbl 0691.60088 |

[22] | Kerbache, L.; Smith, J.M., Asymptotic behavior of the expansion method for open finite queueing networks, Computers & operations research, 15, 2, 157-169, (1988) · Zbl 0662.60105 |

[23] | Kim, N.K.; Chae, K.C., Transform-free analysis of the \(\mathit{GI} / G / 1 / K\) queue through the decomposed little’s formula, Computers & operations research, 30, 3, 353-365, (2003) · Zbl 1029.90022 |

[24] | Kimura, T., Refining diffusion approximations for GI/G/1 queues: A tight discretization method, Teletraffic congress, 317-323, (1985) |

[25] | Kimura, T., Optimal buffer design of an \(M / G / s\) queue with finite capacity, Communications in statistics – stochastic models, 12, 1, 165-180, (1996) · Zbl 0846.60090 |

[26] | Kimura, T., A transform-free approximation for the finite capacity \(M / G / s\) queue, Operations research, 44, 6, 984-988, (1996) · Zbl 0879.90098 |

[27] | Kleinrock, L., Queueing systems. vol. I: theory, () · Zbl 0334.60045 |

[28] | Kubat, P.; Sumita, U., Buffers and backup machines in automatic transfer lines, International journal of production research, 23, 6, 1259-1280, (1985) |

[29] | Labetoulle, J.; Pujolle, G., Isolation method in a network of queues, IEEE transactions on software engineering SE-6, 4, 373-381, (1980) |

[30] | Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (1991), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA |

[31] | Lemaréchal, C., The omnipresence of Lagrange, Annals of operations research, 153, 1, 9-27, (2007) · Zbl 1157.90509 |

[32] | Menasce, D.A., QoS issues in web services, IEEE Internet computing, 6, 6, 72-75, (2002) |

[33] | Muth, E.; Alkaff, A., The throughput rate of three-station production lines: A unifying solution, International journal of production research, 25, 1405-1413, (1987) · Zbl 0623.90031 |

[34] | Neuts, M.F., Matrix geometric solution in stochastic models: an algorithmic approach, (1995), Dover Publications New York, NY |

[35] | Onvural, R.O., Survey of closed queueing networks with blocking, ACM computing surveys, 22, 2, 83-121, (1990) |

[36] | Pla, V.; Casares-Giner, V., Analysis of priority channel assignment schemes in mobile cellular communication systems: A spectral theory approach, Performance evaluation, 59, 2-3, 199-224, (2005) |

[37] | Powell, S.G., 1992. Buffer allocation in unbalanced serial lines. Working Paper #289, The Amos Tuck School of Business Administration, Dartmouth College, Hanover, N.H. 03755. |

[38] | Rao, N., A generalization of the bowl phenomenon in series production systems, International journal of production research, 14, 4, 437-443, (1976) |

[39] | Rao, N., A viable alternative to the method of stages solution of series production systems with Erlang service times, International journal of production research, 14, 6, 699-702, (1976) |

[40] | Robinson, S., A statistical process control approach to selecting a warm-up period for a discrete-event simulation, European journal of operational research, 176, 1, 332-346, (2007) · Zbl 1137.90470 |

[41] | Sakasegawa, H.; Miyazawa, M.; Yamazaki, G., Evaluating the overflow probability using the infinite queue, Management science, 39, 10, 1238-1245, (1993) · Zbl 0792.60095 |

[42] | Schweitzer, P.J.; Konheim, A.G., Buffer overflow calculations using an infinite-capacity model, Stochastic processes and their applications, 6, 3, 267-276, (1978) · Zbl 0373.60123 |

[43] | Seong, D.; Chang, S.Y.; Hong, Y., Heuristic algorithms for buffer allocation in a production line with unreliable machines, International journal of production research, 33, 7, 1989-2005, (1995) · Zbl 0913.90146 |

[44] | Smith, J.M., \(M / G / c / K\) blocking probability models and system performance, Performance evaluation, 52, 4, 237-267, (2003) |

[45] | Smith, J.M., Optimal design and performance modelling of \(M / G / 1 / K\) queueing systems, Mathematical and computer modelling, 39, 9-10, 1049-1081, (2004) · Zbl 1112.90319 |

[46] | Smith, J.M.; Chikhale, N., Buffer allocation for a class of nonlinear stochastic knapsack problems, Annals of operations research, 58, 323-360, (1995) · Zbl 0836.90124 |

[47] | Smith, J.M.; Cruz, F.R.B., The buffer allocation problem for general finite buffer queueing networks, IIE transactions, 37, 4, 343-365, (2005) |

[48] | Smith, J.M.; Daskalaki, S., Buffer space allocation in automated assembly lines, Operations research, 36, 2, 343-358, (1988) |

[49] | Soyster, A.L.; Schmidt, J.W.; Rohrer, M.W., Allocation of buffer capacities for a class of fixed cycle production lines, IIE transactions, 11, 2, 140-146, (1979) |

[50] | Spieckermann, S.; Gutenschwager, K.; Heinzel, H.; Voß, S., Simulation-based optimization in the automotive industry a case study on body shop design, Simulation, 75, 5, 276-286, (2000) |

[51] | Spinellis, D.; Papadopoulos, C.T.; Smith, J.M., Large production line optimization using simulated annealing, International journal of production research, 38, 3, 509-541, (2000) · Zbl 0944.90518 |

[52] | Tijms, H.C., Stochastic modelling and analysis: A computational approach, (1987), John Wiley & Sons New York |

[53] | Tijms, H.C., Heuristics for finite-buffer queues, Probability in the engineering and informational sciences, 6, 267-276, (1992) |

[54] | Tijms, H.C., Stochastic models: an algorithmic approach, (1994), John Wiley & Sons New York · Zbl 0838.60075 |

[55] | Yamashita, H.; Altiok, T., Buffer capacity allocation for a desired throughput in production lines, IIE transactions, 30, 10, 883-892, (1998) |

[56] | Yamashita, H.; Onvural, R., Allocation of buffer capacities in queueing networks with arbitrary topologies, Annals of operations research, 48, 313-332, (1994) · Zbl 0816.90063 |

[57] | Yamashita, H.; Suzuki, S., An approximate solution method for optimal buffer allocation in serial n-stage automatic production lines, Transactions of the Japanese society of mechanical engineers, 807-817, (1987) |

[58] | Yao, D.D.W.; Buzacott, J.A., Queueing models for a flexible machining station part I: the diffusion approximation, European journal of operational research, 19, 2, 233-240, (1985) · Zbl 0553.90049 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.