Mathematical programming models of closed tandem queueing networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Mathematical programming models of closed tandem queueing networks

Full text

Pdf (1.11 MB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 19 , Issue 1 (December 2008) table of contents

Article No. 3

Year of Publication: 2008

ISSN:1049-3301

Authors

Wai Kin Victor Chan	Rensselaer Polytechnic Institute, Troy, NY
Lee W. Schruben	University of California, Berkeley, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 180, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1456645.1456648 What is a DOI?

ABSTRACT

Closed tandem queueing networks are an important class of queueing models. Common approaches for analyzing these systems include Markov processes, renewal theory, and random walks. This article presents optimization models for sample paths of closed tandem queues. These mathematical models provide a new tool for analyzing these queueing systems using the techniques and algorithms from mathematical programming, and from graph theory in particular. We then apply operators from computer graphics (electronic picture manipulation) to graph theoretic representations of discrete-event system dynamics to establish some fundamental mathematical properties for these queueing systems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Askin, R. G. and Standridge, C. R. 1993. Modeling and Analysis of Manufacturing Systems, Wiley.
	2	Bouhchouch, A., Frein, Y., and Dallery, Y. 1996. Performance evaluation of closed tandem queueing networks with finite buffers. Perform. Eval. 26, 2, 115--132.
	3	Arnold H. Buss , Paul J. Sanchez, Modeling very large scale systems: building complex models with LEGOs (Listener Event Graph Objects), Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
	4	Buzacott, J. A. 1989. Queueing models of kanban and mrp controlled production systems. Engineering Cost and Production Economics, 3--20.
	5	Buzacott, J. A. and Shanthikumar, J. G. 1993. Stochastic Models of Manufacturing Systems, Prentice Hall, New Jersey.
	6	Wai Kin Chan , Lee W. Schruben, Special topics on simulation analysis: properties of discrete event systems from their mathematical programming representations, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	7	Chan, W. K. V. and Schruben, L. W. 2007. Optimization models of discrete-event system dynamics. Oper. Res. (to appear).
	8	Dinah W. Cheng, Line reversibility of tandem queues with general blocking, Management Science, v.41 n.5, p.864-873, May 1995 [doi>10.1287/mnsc.41.5.864]
	9	Cheng, D. W. and Righter, R. 1995. On the order of tandem queues. Queueing Syst. 21(1-2): 143--160.
	10	Cheng, D. W. and Yao, D. D. 1993. Tandem queues with general blocking: a unified model and comparison results. Discrete Event Dyn. Syst. 2 3--4, 207--234.
	11	Dallery, Y. and Towsley, D. 1991. Symmetry property of the throughput in closed tandem queueing networks with finite buffers. Oper. Res. Lett. 10, 9, 541--547.
	12	Yves Dallery , Zhen Liu , Don Towsley, Equivalence, reversibility, symmetry and concavity properties in fork-join queuing networks with blocking, Journal of the ACM (JACM), v.41 n.5, p.903-942, Sept. 1994 [doi>10.1145/185675.185776]
	13	Dattatreya, E. S. 1978. Tandem Queueing Systems with Blocking. University of California, Berkeley.
	14	Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
	15	Liberopoulos, G. and Dallery, Y. 2000. A unified framework for pull control mechanisms in multi-stage manufacturing systems. Baltzer. Annals of Operations Research, 325--355. Netherlands.
	16	Liu, X. G. and Buzacott, J. A. 1992. The reversibility of cyclic queues. Oper. Res. Lett. 11, 4, 233--242.
	17	Benjamin Melamed, A note on the reversibility and duality of some tandem blocking queueing systems, Management Science, v.32 n.12, p.1648-1650, Dec. 1986 [doi>10.1287/mnsc.32.12.1648]
	18	Debasis Mitra , Isi Mitrani, Analysis of a Kanban discipline for cell coordination in production lines, Management Science, v.36 n.12, p.1548-1566, Dec. 1990 [doi>10.1287/mnsc.36.12.1548]
	19	Debasis Mitra , Isi Mitrani, Analysis of a kanban discipline for cell coordination in production lines: II. Stochastic demands, Operations Research, v.39 n.5, p.807-823, Sept.-Oct. 1991 [doi>10.1287/opre.39.5.807]
	20	Muth, E. J. 1979. The reversibility property of production lines. Manag. Sci. 25, 2, 152--158.
	21	Onvural, R. O. 1990. Closed queueing networks with blocking. Stochastic Analysis of Computer and Communication Systems. Takagi, Hideaki, Elsevier Science Publishers B.V. (North-Holland), 499--528.
	22	Raif O. Onvural , H. G. Perros, Some equivalencies between closed queueing networks with blocking, Performance Evaluation, v.9 n.2, p.111-118, April 1989 [doi>10.1016/0166-5316(89)90036-9]
	23	C. Dennis Pegden, Introduction to SIMAN, Proceedings of the 17th conference on Winter simulation, p.66-72, December 11-13, 1985, San Francisco, California, United States [doi>10.1145/21850.253077]
	24	Perros, H. G. 1990. Approximation algorithms for open queueing networks with blocking. Stochastic Analysis of Computer and Communication Systems. North-Holland, 451--498.
	25	Michael L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer Publishing Company, Incorporated, 2008
	26	Eric L. Savage , Lee W. Schruben , Enver Yücesan, On the Generality of Event-Graph Models, INFORMS Journal on Computing, v.17 n.1, p.3-9, Winter 2005 [doi>10.1287/ijoc.1030.0053]
	27	Schruben, D. and Schruben, L. W. 2000. Graphical Simulation using SIGMA. Custom Simulation, Ithica, NY.
	28	Lee Schruben, Simulation modeling with event graphs, Communications of the ACM, v.26 n.11, p.957-963, Nov. 1983 [doi>10.1145/182.358460]
	29	Lee W. Schruben, Mathematical programming models of discrete event system dynamics, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
	30	Schruben, L. W. and Roeder, T. M. 2003. Fast simulations of large-scale highly congested systems. Simulation, Transactions of the Society for Modeling and Simulation International. 79, 3, 115--125.
	31	Seila, A. F., Ceric, V., and Tadikamalla, P. R. 2003. Applied Simulation Modeling, Thomson, Brooks/Cole, Belmont.
	32	Som, T. K. and Sargent, R. G. 1990. A formal development of event graphs as an aid to structured and efficient simulation programs. ORSA J. Comput. 1, 2, 107--125.
	33	Walrand, J. 1988. An Introduction to Queueing Networks, Prentice Hall, Englewood Cliffs, NJ.
	34	Wu, J. H. and Chung, C. N. 1991. Timed Finite Automata as the Theoretical Foundation for Simulation Modeling with Event Graphs. Tech. Rep., Dept. of Decision Sciences and Information Systems, University of Kentucky, Lexington.
	35	Yamazaki, G., Sakasegawa, H., and Kawashima, T. 1978. Production rate estimated with flow-shop reversibility. Bull. JSME. 21 167--171.
	36	Yamazaki, G., Kawashima, T. and Sakasegawa, H. 1985. Reversibility of tandem blocking queueing systems. Manag. Sci. 31, 1, 78--83.
	37	Genji Yamazaki , Hirotaka Sakasegawa , J. George Shanthikumar, On optimal arrangement of stations in a tandem queueing system with blocking, Management Science, v.38 n.1, p.137-153, Jan. 1992 [doi>10.1287/mnsc.38.1.137]