STATE‐OF‐THE‐ART SURVEY: OPEN QUEUEING NETWORKS: OPTIMIZATION AND PERFORMANCE EVALUATION MODELS FOR DISCRETE MANUFACTURING SYSTEMS

Abstract

In this survey we review methods to analyze open queueing network models for discrete manufacturing systems. We focus on design and planning models for job shops. The survey is divided in two parts: in the first we review exact and approximate decomposition methods for performance evaluation models for single and multiple product class networks. The second part reviews optimization models of three categories of problems: the first minimizes capital investment subject to attaining a performance measure (WIP or lead time), the second seeks to optimize the performance measure subject to resource constraints, and the third explores recent research developments in complexity reduction through shop redesign and products partitioning.

Keywords

OPEN QUEUEING NETWORKS OPTIMIZATION AND PERFORMANCE EVALUATION DECOMPOSITION METHODS DISCRETE MANUFACTURING SYSTEMS JOB‐SHOP DESIGN

Get full access to this article

View all access options for this article.

References

Albin

S. L.

(1982), “Poisson Approximations for Superposition Arrival Processes in Queues,” Management Seienee, 28, 2, 126–137.

Albin

S. L.

(1984), “Approximating a Point Process by a Renewal Process, II: Superposition Arrival Processes of Queues,” Operations Research, 32, 5, 1133–1162.

Albin

S. L.

(1986), “Delays for Customers from Different Arrival Streams to a Queue.” Management Seienee, 32, 4, 329–340.

Baskett

Chandy

K. M.

Muntz

R. R.

, and Palacios

F. G.

(1975), “Open, Closed, and Mixed Networks of Queues with Different Classes of Customers,” Journal of the Association for Computing Machinery, 22, 2, 248–260.

Bazaraa

M. S.

Sherali

H. D.

, and Shetty

C. M.

(1993), Nonlinear Programming: Theory and Algorithms, 2nd. ed., John Wiley & Sons, New York.

Bitran

G. R.

and Dasu

(1992), “A Review of Open Queueing Network Models of Manufacturing Systems,” Queueing Systems, 12, 95–134.

Bitran

G. R.

and Morabito

(1995), “Manufacturing Systems Design: Trade‐off Curve Analysis,” Working Paper WP #3805–95, Sloan School of Management, MIT, Cambridge, MA (submitted to Production and Operations Management).

Bitran

G. R.

and Sarkar

(1994a), “Throughput Analysis in Manufacturing Networks,” European Journal of Operational Research, 74, 448–465.

Bitran

G. R.

and Sarkar

(1994b), “Targeting Problems in Manufacturing Queueing Networks‐An Iterative Scheme and Convergence,” European Journal of Operational Research, 76, 501–510.

10.

Bitran

G. R.

and Sarkar

(1994c), Focused Factory Design: Complexity, Capacity and Inventory Tradeoffs, Technical Memorandum, AT&T Bell Lab., Holmdel, NJ.

11.

Bitran

G. R.

and Tirupati

(1988), “Multiproduct Queueing Networks with Deterministic Routing: Decomposition Approach and the Notion of Interference,” Management Science, 34, 1, 75–100.

12.

Bitran

G. R.

and Tirupati

(1989a), “Tradeoff Curves, Targeting and Balancing in Manufacturing Queueing Networks.” Operations Research, 37, 4, 547–564.

13.

Bitran

G. R.

and Tirupati

(1989b), “Capacity Planning in Manufacturing Networks with Discrete Options,” Annals of Operations Research, 17, 119–136.

14.

Bitran

G. R.

and Tirupati

(1989c), “Approximations for Product Departures from a Single Server Station with Batch Processing in Multi‐product Queues,” Management Science, 35, 7, 851–878.

15.

Bitran

G. R.

and Tirupati

(1991), “Approximations for Network of Queues with Overtime,” Management Science, 37, 3, 282–300.

16.

Boxma

O. J.

Rinnooy Kan

, and Van Vliet

(1990), “Machine Allocation Problems in Manufacturing Networks,” European Journal of Operational Research, 45, 47–54.

17.

Brown

(1988), “IBM Combines Rapid Modeling Technique and Simulation to Design PCB Factory‐of‐the‐Future,” Industrial Engineering, 20, 6, 23–90.

18.

Buzacott

J. A.

and Shanthikumar

J. G.

(1992), “Design of Manufacturing Systems Using Queueing Models,” Queueing Systems, 12, 135–214.

19.

Buzacott

J. A.

and Shanthikumar

J. G.

(1993), Stochastic Models of Manufacturing Systems, Prentice‐Hall, Englewood Cliffs, NJ.

20.

Buzacott

J. A.

and Yao

D. D.

(1986), “Flexible Manufacturing Systems: A Review of Analytical Models,” Management Science, 32, 7, 890–905.

21.

Calabrese

J. M.

(1992), “Optimal Workload Allocation in Open Networks of Multiserver Queues,” Management Science, 38, 12, 1792–1802.

22.

Chase

R. B.

and Aquilano

N. J.

(1992), Production and Operations Management‐A Life Cycle Approach, Irwin, Homewood, MA.

23.

Dallery

and David

(1986), “Operational Analysis of Multiclass Queueing Networks,” Proceedings of the 25th IEEE Conference Decision and Control, Athens, Greece, 1728–1732.

24.

Dallery

and Stecke

K. E.

(1990), “On The Optimal Allocation of Servers and Workloads in Closed Queueing Networks,” Operations Research, 38, 4, 694–703.

25.

Denning

P. J.

and Buzen

J. P.

(1978), “The Operational Analysis of Queueing Networks.” Association for Computing Machinery (ACM) Computing Surveys, 10, 3, 225–261.

26.

Disney

R. L.

and Konig

(1985), “Queueing Networks: A Survey of Their Random Processes,” Society for Industrial and Applied Mathematics (SIAM) Review 27, 3, 335–403.

27.

Erlang

A. K.

(1917), “Solution of Some Problems in the Theory of Probabilities of Some Significance in Automatic Telephone Exchanges,” Post Office Electrical Engineer's Journal, 10, 189–197.

28.

Frenk

Labbe

Van Vliet

, and Zhang

(1994), “Improved Algorithms for Machine Allocation in Manufacturing Systems,” Operations Research, 42, 3, 523–530.

29.

Gershwin

S. B.

(1994), Manufacturing Systems Engineering, Prentice Hall, Englewood Cliffs, NJ.

30.

Harel

and Zipkin

(1987), “Strong Convexity Results for Queueing Systems,” Operations Research, 35, 4, 405–418.

31.

Harrison

and Nguyen

(1990), “The QNET Method for Two‐Moment Analysis of Open Queueing Networks,” Queueing Systems, 6, 1–32.

32.

Harrison

and Nguyen

(1993), “Brownian Models of Multiclass Queueing Networks: Current Status and Open Problems,” Queueing Systems, 13, 5–40.

33.

Harrison

and Williams

(1987), “Brownian Models of Open Queueing Networks with Homogeneous Customer Populations,” Stochastic, 22, 77–115.

34.

Y. C.

(1987), “Performance Evaluation and Perturbation Analysis of Discrete Event Dynamic Systems,” IEEE Transactions on Automatic Control, 32, 7, 563–572.

35.

Y. C.

and Cao

(1983), “Perturbation Analysis and Optimization of Queueing Networks.” Journal Optimization Theory and Applications, 40, 4, 559–582.

36.

Hsu

L. F.

Tapiero

C. S.

, and Lin

(1993), “Network of Queues Modeling in Flexible Manufacturing Systems: A Survey,” Recherche Operationnelle l'Operations Research, 27, 2, 201–248.

37.

Jackman

and Johnson

(1993), “The Role of Queueing Network Models in Performance Evaluation of Manufacturing Systems,” Journal of the Operational Research Society, 44, 8, 797–807.

38.

Jackson

J. R.

(1957), “Networks of Waiting Lines,” Operations Research, 5, 4, 518–521.

39.

Jackson

J. R.

(1963), “Job Shop‐like Queueing Systems,” Management Science, 10, 1, 131–142.

40.

Karmarkar

U. S.

(1993), “Manufacturing Lead Times, Order Release and Capacity Loading,” in Handbooks in OR/MS, Graves

S. C.

(ed.). Vol. 4, Elsevier, North‐Holland, Amsterdam.

41.

Kelly

F. P.

(1975), “Networks of Queues with Customers of Different Types,” Journal of Applied Probability, 12, 542–554.

42.

Kelly

F. P.

(1979), Reversibility and Stochastic Processes, John Wiley & Sons, New York.

43.

Kleinrock

(1964), Communication Nets: Stochastic Message Flow and Delay, Dover Publishing, New York.

44.

Kleinrock

(1975), Queueing Systems, Vol. I, Computer Applications, John Wiley & Sons, Inc., New York.

45.

Kleinrock

(1976), Queueing Systems, Vol. 2, Computer Applications, John Wiley & Sons, Inc., New York.

46.

Kobayashi

(1974), “Application of the Diffusion Approximation to Queueing Networks I: Equilibrium Queue Distributions,” Journal of the Association for Computing Machinery, 21, 2, 316–328.

47.

Koenigsberg

(1982), “Twenty Five Years of Cyclic Queues and Closed Queue Networks: A Review,” Journal of the Operational Research Society, 33, 7, 605–619.

48.

Kouvelis

and Tirupati

(1991), “Approximate Performance Modeling and Decision Making for Manufacturing Systems: A Queueing Network Optimization Framework,” Journal of Intelligent Manufacturing, 2, 107–134.

49.

Kuehn

P. J.

(1979), “Approximate Analysis of General Networks by Decomposition,” IEEE Transactions Commun, 27, 1, 113–126.

50.

Law

A. M.

and Haider

S. W.

(1989), “Selecting Simulation Software for Manufacturing Applications: Practical Guidelines & Software Survey,” Industrial Engineering, May 89, 33–46.

51.

Law

A. M.

and Mccomas

M. G.

(1989), “Pitfalls to Avoid in the Simulation of Manufacturing Systems,” Industrial Engineering, May 89, 28–69.

52.

Lemoine

A. J.

(1977), “Networks of Queues‐A Survey of Equilibrium Analysis,” Management Science, 24, 4, 464–481.

53.

Pujolle

and Ai

(1986), “A Solution for Multiserver and Multiclass Open Queueing Networks,” Information Systems and Operations Research, 24, 3, 221–230.

54.

Reiman

M. I.

(1984), “Open Queueing Networks in Heavy‐Traffic,” Mathematics of Operational Research, 9, 441–458.

55.

Reiman

M. I.

(1990), “Asymptotically Exact Decomposition Approximations for Open Queueing Networks,” Operations Research Lett., 9, 6, 363–370.

56.

Reiser

and Kobayashi

(1974), “Accuracy of Diffusion Approximations for Some Queueing Systems,” IBM Journal of Research and Development, 18, 110–124.

57.

Sevcik

K. C.

Levy

A. I.

Tripathi

S. K.

, and Zahorjan

J. L.

(1977), “Improving Approximations of Aggregated Queueing Network Systems,” in Computer Performance, Chandy

and Reiser

(eds.), North‐Holland., 1–22.

58.

Segal

and Whitt

(1989), “A Queueing Network Analyzer for Manufacturing,” in Teletraffic Science for New Cost‐Effective System, Networks and Services, ITC‐12, Bonatti

(ed.), Elsevier, North‐Holland, Amsterdam, 1146–1152.

59.

Seidmann

Schweitzer

P. J.

, and Shalev‐Oren

(1987), “Computerized Closed Queueing Network Models of Flexible Manufacturing Systems: A Comparative Evaluation,” Large Scale Systems, 12, 91–107.

60.

Shanthikumar

J. G.

and Buzacott

J. A.

(1981), “Open Queueing Network Models of Dynamic Job Shops,” International Journal of Production Research, 19, 3, 255–266.

61.

Shanthikumar

J. G.

and Buzacott

J. A.

(1984), “The Time Spent in a Dynamic Job Shop,” European Journal of Operational Research, 17, 215–226.

62.

Shanthikumar

J. G.

and Yao

D. D.

(1987), “Optimal Server Allocation in a System of Multi‐Server Stations,” Management Science, 33, 9, 1173–1180.

63.

Shanthikumar

J. G.

and Yao

D. D.

(1988), “On Server Allocation in Multiple Center Manufacturing Systems,” Operations Research, 36, 2, 333–342.

64.

Sundarraj

R. P.

Sundararaghavan

P. S.

, and Fox

D. R.

(1994), “Optimal Server Acquisition in Open Queueing Networks,” Journal of the Operational Research Society, 45, 5, 549–558.

65.

Suresh

and Whitt

(1990), “The Heavy‐Traffic Bottleneck Phenomenon in Open Queueing Networks,” Operations Research Letters, 9, 6, 355–362.

66.

Suri

(1989), “Perturbation Analysis: The State of the Art and Research Issues Explained Via the G/G/1 Queue,” Proceedings IEEE, 77, 114–137.

67.

Suri

and De Treville

(1991), “Full Speed Ahead: A Look at Rapid Modeling Technology in Operations Management,” OR/MS Today, 18, June 1991, 34–42.

68.

Suri

Diehl

G. W.

, and Dean

(1986), “Quick and Easy Manufacturing Systems Analysis Using ManuPlan.” Proceedings Spring IIE Conference, Dallas, TX, 195–205.

69.

Suri

Sanders

J. L.

, and Kamath

(1993), “Performance Evaluation of Production Networks,” in Handbooks in OR/MS, Graves

S. C.

(ed.), Vol. 4, Elsevier, North‐Holland, Amsterdam, 199–286.

70.

Tang

C. S.

and Yoo

(1991), “System Planning and Configuration Problems for Optimal System Design,” European Journal of Operational Research, 54, 163–175.

71.

Tijms

H. C.

(1986), Stochastic Modeling and Analysis: A Computational Approach, John Wiley & Sons, Inc., New York.

72.

Van Vliet

and Rinnooy Kan

(1991), “Machine Allocation Algorithms for Job Shop Manufacturing,” Journal of Intelligent Manufacturing, 2, 83–94.

73.

Walrand

(1990), “Queueing Networks,” in Handbooks in OR/MS, Heyman

D. P.

and Sobel

M. J.

(ed.). Vol. 2, Elsevier, North‐Holland, Amsterdam, 519–590.

74.

Wein

L. M.

(1990a), “Capacity Allocation in Generalized Jackson Networks,” Operations Research Letters, 15, 215–242.

75.

Wein

L. M.

(1990b), “Scheduling Networks of Queues: Heavy Traffic Analysis of a Two‐Station Network with Controllable Inputs,” Operations Research, 38, 6, 1065–1078.

76.

Whitt

(1982), “Approximating a Point Process by a Renewal Process, I: Two Basic Methods,” Operations Research, 30, 1, 125–147.

77.

Whitt

(1983a), “The Queueing Network Analyzer,” The Bell System Technical Journal, 62, 9, 2779–2815.

78.

Whitt

(1983b), “Performance of the Queueing Network Analyzer,” The Bell System Technical Journal, 62, 9, 2817–2843.

79.

Whitt

(1984), “Open and Closed Models for Networks of Queues,” AT&T Bell Laboratories Technical Journal, 63, 9. 1911–1979.

80.

Whitt

(1988), “A Light‐Traffic Approximation for Single‐Class Departures from Multi‐class Queues.” Management Science, 34, 11, 1333–1346.

81.

Whitt

(1992), “Understanding the Efficiency of Multi‐server Service Systems,” Management Science, 38, 5, 708–723.

82.

Whitt

(1993), “Approximations for the GI/G/m Queue,” Production and Operations Management, 2, 2, 114–161.

83.

Whitt

(1994), “Towards Better Multi‐class Parametric‐Decomposition Approximations for Open Queueing Networks,” Annals of Operations Research, 48, 221–248.

84.

Yao

D. D.

and Buzacott

J. A.

(1986), “The Exponentialization Approach to Flexible Manufacturing System Models with General Processing Times,” European Journal of Operational Research, 24, 410–416.