×

Multi-objective routing within large scale facilities using open finite queueing networks. (English) Zbl 0971.90014

Summary: The major objective of this paper is to examine the optimal routing in layout and location problems from a network optimization perspective where manufacturing facilities are modelled as open finite queueing networks with a multiobjective set of performance measures. The overall material handling system is broken down into a set of layout topologies. For each one of these topologies the optimal routing is determined so that the product throughput is maximized while minimizing the average sojourn time and holding costs. An approximate analytical decomposition technique for modelling open finite queueing networks, called the Generalized Expansion Method (GEM), developed by the authors, is utilized to calculate the desired outputs. A mathematical optimization procedure which is described in this paper is then used to determine the optimal routes. As will be demonstrated, the design methodology of combining the optimization and analytical queueing network models provides a very effective procedure for evaluating alternative topologies while simultaneously determining the average sojourn times and the maximum throughputs of the best routes.

MSC:

90B22 Queues and service in operations research
90C35 Programming involving graphs or networks
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlberg, J., 1988. Stochastic queueing network program for evacuation planning. Master’s Project, IEOR Department, University of Massachusetts, Amherst, MA; Ahlberg, J., 1988. Stochastic queueing network program for evacuation planning. Master’s Project, IEOR Department, University of Massachusetts, Amherst, MA
[2] Altiok, T., 1997. Performance Analysis of Manufacturing Systems. Springer, New York; Altiok, T., 1997. Performance Analysis of Manufacturing Systems. Springer, New York · Zbl 0942.90003
[3] Altiok, T.; Perros, H. G., Approximate analysis of arbitrary configurations of open queueing networks with blocking, Annals of Operations Research, 9, 481-509 (1987)
[4] Bakuli, D.; Smith, J. M., Resource allocation in state-dependent emergency evacuation networks, European Journal of Operational Research, 89, 543-555 (1996) · Zbl 0915.90110
[5] Brown, K.M., 1969. A quadratically convergent Newton-like method based upon Gaussian elimination. SIAM Journal on Numerical Analysis 6 (4), 560-569; Brown, K.M., 1969. A quadratically convergent Newton-like method based upon Gaussian elimination. SIAM Journal on Numerical Analysis 6 (4), 560-569 · Zbl 0245.65023
[6] Buzacott, J.A., Shanthikumar, J.G., 1993. Stochastic Models of Manufacturing Systems. Prentice-Hall, Englewood Cliffs, NJ; Buzacott, J.A., Shanthikumar, J.G., 1993. Stochastic Models of Manufacturing Systems. Prentice-Hall, Englewood Cliffs, NJ · Zbl 0769.90043
[7] Cassandras, C., 1984. Hierarchical routing control scheme for MHS. In: Proceedings of ORSA/TIMS Meeting on FMS, University of Michigan, Ann Arbor, MA; Cassandras, C., 1984. Hierarchical routing control scheme for MHS. In: Proceedings of ORSA/TIMS Meeting on FMS, University of Michigan, Ann Arbor, MA
[8] Chankong, V., Haimes, Y.Y., 1983. Multiobjective Decision Making: Theory and Methodology. North-Holland, New York; Chankong, V., Haimes, Y.Y., 1983. Multiobjective Decision Making: Theory and Methodology. North-Holland, New York · Zbl 0622.90002
[9] Dallery, Y.; Frein, D., On decomposition methods for tandem queueing networks with blocking, Operations Research, 41, 2, 386-399 (1993) · Zbl 0771.90046
[10] Dallery, Y.; Gershwin, S. B., Manufacturing flow line systems: A review of models and analytical results, Queueing Systems, 12, 1, 3-94 (1992) · Zbl 0782.90048
[11] Daskalaki, S., Smith, J.M., 1986. The static routing problem in open finite queueing networks. Paper presented at the ORSA/TIMS Meeting, Miami, FL; Daskalaki, S., Smith, J.M., 1986. The static routing problem in open finite queueing networks. Paper presented at the ORSA/TIMS Meeting, Miami, FL
[12] Daskalaki, S., Smith, J.M., 1987. Real time routing in open finite queueing networks. Paper presented at the Queueing Networks and their Applications Conference, New Brunswick, NJ; Daskalaki, S., Smith, J.M., 1987. Real time routing in open finite queueing networks. Paper presented at the Queueing Networks and their Applications Conference, New Brunswick, NJ
[13] Daskalaki, S., Smith, J.M., 1989. Real time routing in finite queueing networks. In: Perros, H.G., Altiok, T. (Eds.), Queueing Networks with Blocking. Elsevier, New York, pp. 313-324; Daskalaki, S., Smith, J.M., 1989. Real time routing in finite queueing networks. In: Perros, H.G., Altiok, T. (Eds.), Queueing Networks with Blocking. Elsevier, New York, pp. 313-324
[14] De Koster, M. B.M., Approximate analysis of production systems, European Journal of Operational Research, 25, 615-626 (1988)
[15] Fischer, L., 1981. The Lagrangean relaxation method for solving integer programming problems. Management Science 27 (1); Fischer, L., 1981. The Lagrangean relaxation method for solving integer programming problems. Management Science 27 (1)
[16] Garey, M., Johnson, D.S., 1979. Computers and Intractability: A Guide to The Theory of NP-Completeness. Freeman, San Francisco, CA; Garey, M., Johnson, D.S., 1979. Computers and Intractability: A Guide to The Theory of NP-Completeness. Freeman, San Francisco, CA · Zbl 0411.68039
[17] Garfinkel, R., Newhauser, G., 1972. Integer Programming. Wiley, New York; Garfinkel, R., Newhauser, G., 1972. Integer Programming. Wiley, New York
[18] Gershwin, S. B., Assembly/disassembly systems: An efficient decomposition algorithm for tree-structured networks, IIE Transactions, 23, 302-314 (1991)
[19] Gershwin, S.B., 1994. Manufacturing Systems Engineering. Prentice-Hall, Englewood Cliffs, NJ; Gershwin, S.B., 1994. Manufacturing Systems Engineering. Prentice-Hall, Englewood Cliffs, NJ · Zbl 0903.90070
[20] Girard, A., 1990. Routing and Dimensioning in Circuit-Switched Networks. Addison-Wesley, New York; Girard, A., 1990. Routing and Dimensioning in Circuit-Switched Networks. Addison-Wesley, New York
[21] Gosavi, H.D., Smith, J.M., 1995. Static routing in open, finite queueing networks with blocking. Technical Report, Umass, Amherst, MA; Gosavi, H.D., Smith, J.M., 1995. Static routing in open, finite queueing networks with blocking. Technical Report, Umass, Amherst, MA
[22] Gosavi, H. D.; Smith, J. M., An algorithm for sub-optimal routeing in series-parallel queueing networks, International Journal of Production Research, 35, 5, 1413-1430 (1997) · Zbl 0939.90509
[23] Gosavi, H.D., Smith, J.M., 1998. Optimal routing in M/M/1/K and M/M/C/K queueing networks with production blocking. Paper presented at the International Workshop on Performance Evaluation and Optimization of Production Lines, Samos, Greece (in Review); Gosavi, H.D., Smith, J.M., 1998. Optimal routing in M/M/1/K and M/M/C/K queueing networks with production blocking. Paper presented at the International Workshop on Performance Evaluation and Optimization of Production Lines, Samos, Greece (in Review)
[24] Gupta, S.M., Kavusturucu, A., 1997. Production Systems with Interruptions, Arbitrary Topology and Finite Buffers. Working Paper, Northeastern University, Boston; Gupta, S.M., Kavusturucu, A., 1997. Production Systems with Interruptions, Arbitrary Topology and Finite Buffers. Working Paper, Northeastern University, Boston · Zbl 0953.90019
[25] Ignizio, J.M., 1976. Goal Programming and Extensions. Heath, Lexington, MA; Ignizio, J.M., 1976. Goal Programming and Extensions. Heath, Lexington, MA
[26] Jain, S., Smith, J.M., 1984. Finite queueing networks with M/M/C/K parallels servers. Computers and Operations Research 21 (3), 297-317; Jain, S., Smith, J.M., 1984. Finite queueing networks with M/M/C/K parallels servers. Computers and Operations Research 21 (3), 297-317
[27] Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H.G., The complexity of the network design problem, Networks, 8, 279-285 (1978) · Zbl 0395.94048
[28] Keeney, R.L., Raiffa, H., 1976. Decisions with Multiple Objectives: Preference and Value Trade-offs. Wiley, New York; Keeney, R.L., Raiffa, H., 1976. Decisions with Multiple Objectives: Preference and Value Trade-offs. Wiley, New York
[29] Kerbache, L., 1984. Analysis of Open Finite Queueing Networks. Ph.D. Dissertation in IEOR, University of Massachusetts, Amherst, MA; Kerbache, L., 1984. Analysis of Open Finite Queueing Networks. Ph.D. Dissertation in IEOR, University of Massachusetts, Amherst, MA
[30] Kerbache, L., Smith, J.M., 1982. Optimization techniques in finite queueing networks. ORSA Meeting, San Diego, CA; Kerbache, L., Smith, J.M., 1982. Optimization techniques in finite queueing networks. ORSA Meeting, San Diego, CA
[31] Kerbache, L.; Smith, J. M., Asymptotic behavior of the expansion method, Computers and Operations Research, 15, 2, 157-169 (1988) · Zbl 0662.60105
[32] Kerbache, L.; Smith, J. M., The generalized expansion method, European Journal of Operational Research, 32, 448-461 (1987) · Zbl 0691.60088
[33] Kleinrock, L., 1975. Queueing Systems: Computer Applications, vol. 1. Wiley, New York; Kleinrock, L., 1975. Queueing Systems: Computer Applications, vol. 1. Wiley, New York · Zbl 0334.60045
[34] Kleinrock, L., 1976. Queueing Systems: Computer Applications, vol. 2. Wiley, New York; Kleinrock, L., 1976. Queueing Systems: Computer Applications, vol. 2. Wiley, New York · Zbl 0361.60082
[35] Labetoulle, J., Pujolle, G., 1980. Isolation method in a network of queues. IEEE Transactions on Software Engineering SE-6 (4); Labetoulle, J., Pujolle, G., 1980. Isolation method in a network of queues. IEEE Transactions on Software Engineering SE-6 (4) · Zbl 0349.68026
[36] Lee, H. S.; Pollock, S. M., Approximation analysis of open acyclic exponential queueing networks with blocking, Operations Research, 38, 2, 1123-1134 (1990) · Zbl 0721.60104
[37] Mitchell, D.H., 1995. Topological network design and analysis of M/G/C/C state-dependent queueing networks. M.Sc. Thesis in IEOR, University of Massachusetts, Amherst, MA; Mitchell, D.H., 1995. Topological network design and analysis of M/G/C/C state-dependent queueing networks. M.Sc. Thesis in IEOR, University of Massachusetts, Amherst, MA
[38] Papadopoulos, H.T., Heavey, C., Browne, J., 1993. Queueing Theory in Manufacturing Systems Analysis and Design. Chapman & Hall, London; Papadopoulos, H.T., Heavey, C., Browne, J., 1993. Queueing Theory in Manufacturing Systems Analysis and Design. Chapman & Hall, London
[39] Perros, H.G., 1994. Queueing Networks with Blocking: Exact and Approximate Solutions. Oxford University Press, New York; Perros, H.G., 1994. Queueing Networks with Blocking: Exact and Approximate Solutions. Oxford University Press, New York · Zbl 0849.90064
[40] Pollock, S., Birge, J.R., Alden, J.M., 1985. Approximation analysis for open tandem queues with blocking: Exponential and general service distribution. T.C. 85-90, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI; Pollock, S., Birge, J.R., Alden, J.M., 1985. Approximation analysis for open tandem queues with blocking: Exponential and general service distribution. T.C. 85-90, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI
[41] Smith, J.M., 1981. The use of open queueing networks and mixed integer programming to allocate resources optimally within a library Layout. Journal of the American Society for Information Sciences; Smith, J.M., 1981. The use of open queueing networks and mixed integer programming to allocate resources optimally within a library Layout. Journal of the American Society for Information Sciences
[42] Smith, J.M., 1987. QNET-C: An interactive graphics computer program for evacuation planning. In: Proceedings of The Conference on Emergency Planning, SCS Multiconference, 19-24 January; Smith, J.M., 1987. QNET-C: An interactive graphics computer program for evacuation planning. In: Proceedings of The Conference on Emergency Planning, SCS Multiconference, 19-24 January
[43] Smith, J. M.; Daskalaki, S., Buffer space allocation in automated assembly lines, Operations Research, 36, 2, 343-358 (1988)
[44] Smith, J. M.; Towsley, The use of queueing networks in the evacuation of egress from buildings, Environment and Planning, 8, 125-139 (1981)
[45] Steenstrup, M., 1995. Routing in Communications Networks. Prentice-Hall, Englewood Cliffs, NJ; Steenstrup, M., 1995. Routing in Communications Networks. Prentice-Hall, Englewood Cliffs, NJ · Zbl 0833.68008
[46] Takahashi, Y., 1989. Aggregate Approximation for Acyclic Queueing Networks With Communication Blocking. Proceedings 1st International Workshop on Queueing Networks With Blocking, Raleigh, NC; Takahashi, Y., 1989. Aggregate Approximation for Acyclic Queueing Networks With Communication Blocking. Proceedings 1st International Workshop on Queueing Networks With Blocking, Raleigh, NC
[47] Talebi, K., 1985. Stochastic network evacuation models. Ph.D. Thesis, Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, MA; Talebi, K., 1985. Stochastic network evacuation models. Ph.D. Thesis, Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, MA
[48] Whitt, W., Approximating a point process by a renewal process: The view through a queue, an indirect approach, Management Science, 27, 6, 619-636 (1982) · Zbl 0457.60073
[49] Whitt, W., The queueing network analyzer, The Bell System Technical Journal, 62, 9, 2779-2815 (1983)
[50] Yannopoulos, E., 1993. Approximate analysis of open queueing networks with blocking. Ph.D. Thesis, MIE Department, University of Manitoba, Winnipeg; Yannopoulos, E., 1993. Approximate analysis of open queueing networks with blocking. Ph.D. Thesis, MIE Department, University of Manitoba, Winnipeg
[51] Yao, D. 1984. A FMS network model with state-dependent routing. In: Proceedings of The ORSA/TIMS Meeting on FMS, University of Michigan, Ann Arbor, MI; Yao, D. 1984. A FMS network model with state-dependent routing. In: Proceedings of The ORSA/TIMS Meeting on FMS, University of Michigan, Ann Arbor, MI
[52] Zeleny, M., 1982. Multiple Criteria Decision Making. McGraw-Hill, New York; Zeleny, M., 1982. Multiple Criteria Decision Making. McGraw-Hill, New York · Zbl 0588.90019
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.