×

Performance evaluation of scheduling control of queueing networks: Fluid model heuristics. (English) Zbl 0858.90052

Summary: Motivated by dynamic scheduling control for queueing networks, the second author and D. D. Yao [Oper. Res. 41, No. 6, 1104-1115 (1993; Zbl 0791.90023)] developed a systematic method to generate dynamic scheduling control policies for a fluid network, a simple and highly aggregated model that approximates the queueing network. This study addresses the question of how good these fluid policies are as heuristic scheduling policies for queueing networks. Using simulation on some examples these heuristic policies are compared with traditional simple scheduling rules. The results show that the heuristic policies perform at least comparably to classical priority rules, regardless of the assumptions made about the traffic intensities and the arrival and service time distributions. However, they are certainly not always the best and, even when they are, the improvement is seldom dramatic. The comparative advantage of these policies may lie in their application to nonstationary situations such as might occur with unreliable machines or nonstationary demand patterns.

MSC:

90B22 Queues and service in operations research
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
90B18 Communication networks in operations research
90B10 Deterministic network models in operations research

Citations:

Zbl 0791.90023
Full Text: DOI

References:

[1] D. Bertsimas, I.Ch. Paschalidis and J.N. Tsitsiklis, Optimisation of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance, Working Paper of the Operations Research Center, MIT (1992). · Zbl 0797.60079
[2] G.R. Bitran and D. Tirupati, Multiproduct queueing networks with deterministic routing: Decomposition approach and the notion of interference, Manag. Sci. 34 (1988) 75-100. · Zbl 0636.60101 · doi:10.1287/mnsc.34.1.75
[3] J.A. Buzacott and J.G. Shantikumar,Stochastic Models of Manufacturing Systems (PrenticeHall, New Jersey, 1992). · Zbl 1094.90518
[4] H. Chen, Optimal intensity control of a multi-class queue, Queueing Systems 5 (1989) 281-294. · Zbl 0684.60070 · doi:10.1007/BF01225320
[5] H. Chen, J.M. Harrison, A. Mandelbaum, A. van Ackere and L. Wein, Empirical evaluation of a queueing network model for semiconductor wafer fabrication, Oper. Res. 36 (1988) 202-215. · doi:10.1287/opre.36.2.202
[6] H. Chen and A. Mandelbaum, Discrete flow networks: bottleneck analysis and fluid approximations, Math. Oper. Res. 16 (1991) 408-446. · Zbl 0735.60095 · doi:10.1287/moor.16.2.408
[7] H. Chen, P. Yang and D.D. Yao, Control and scheduling in a two-station queueing network: optimal policies and heuristics, to appear in Queueing Systems. · Zbl 0836.90073
[8] H. Chen and D.D. Yao, Dynamic scheduling of a multi-class fluid network, Oper. Res. 41 (1993) 1104-1115. · Zbl 0791.90023 · doi:10.1287/opre.41.6.1104
[9] D. Connors, G. Feigin and D.D. Yao, Scheduling semiconductor lines using a fluid network model, submitted to IEEE Trans. Robotics Autom., Special Section on Computer Integrated Manufacturing.
[10] D. Cox and W. Smith,Queues (Methuen, London, 1961).
[11] G. Feigin, Comparing scheduling policies for semiconductor manufacturing, presented atWorkshop on Hierarchical Control for Real-time Scheduling of Manufacturing Systems, Lincoln, New Hampshire (1992).
[12] J.M. Harrison, Dynamic scheduling of a multiclass queue: discount optimality, Oper. Res. 23 (1975) 270-282. · Zbl 0321.60073 · doi:10.1287/opre.23.2.270
[13] J.M. Harrison and V. Nyugen, The QNET method for two-moment analysis of open queueing networks, Queueing Systems 6 (1990) 1-32. · Zbl 0702.60082 · doi:10.1007/BF02411463
[14] J.M. Harrison and L.W. Wein, Scheduling networks of queues: heavy traffic analysis of a simple open network, Queueing Systems 5 (1989) 265-280. · Zbl 0684.90034 · doi:10.1007/BF01225319
[15] L. Kleinrock,Queueing Systems, Vol. II: Computer Applications (Wiley, 1976). · Zbl 0361.60082
[16] G.P. Klimov, Time sharing service systems I, Theor. Prob. Appl. 19 (1974) 532-551. · Zbl 0378.60102 · doi:10.1137/1119060
[17] P.R. Kumar, Re-entrant lines, Queueing Systems 13 (1993) 87. · Zbl 0772.90049 · doi:10.1007/BF01158930
[18] T.L. Lai and Z. Ying, Open bandit problems and optimal scheduling of queueing networks, Adv. Appl. Prob. 20 (1988) 447-472. · Zbl 0645.90027 · doi:10.2307/1427399
[19] G.F. Newell,Applications of Queueing Theory (Chapman and Hall, 1982). · Zbl 0503.60094
[20] S.S. Panwalkar and W. Iskander, A survey of scheduling rules, Oper. Res. 25 (1977) 45-61. · Zbl 0369.90054 · doi:10.1287/opre.25.1.45
[21] J. Perkins and P.R. Kumar, Stable, distributed, real-time scheduling of flexible manufacturing/ assembly/disassembly systems, IEEE Trans. Autom. Contr. 34 (1989) 139-148. · Zbl 0674.90041 · doi:10.1109/9.21085
[22] K.W. Ross and D.D. Yao, Optimal dynamic scheduling in Jackson networks, IEEE Trans. Autom. Contr. 34 (1989) 47-53. · Zbl 0674.90024 · doi:10.1109/9.8648
[23] S. Stidham, Scheduling, routing and flow control in stochastic networks,Stochastic Differential Systems, Stochastic Control Theory and Applications, eds. W. Fleming and P.L. Lions, IMA Vol. 10 (Springer, New York, 1988). · Zbl 0656.90032
[24] J.J. Solberg, A mathematical model of computerized manufacturing systems,Proc. 4th Int. Conf. Prod. Res., Tokyo, Japan (1977).
[25] R. Suri, J.L. Sanders and M. Kamath, Performance evaluation of production networks,Logistics of Production and Inventory, Handbooks in OR and MS, Vol. 4, eds. S.C. Graves et al. (North-Holland, Amsterdam, 1993).
[26] D.W. Tcha and S.R. Pliska, Optimal control of single-server queueing networks and multi-classM/G/1 queues with feedback, Oper. Res. 25 (1977) 248-258. · Zbl 0372.60137 · doi:10.1287/opre.25.2.248
[27] P.P. Varaiya, J. Walrand and C. Buyukkoc, Extensions of the multi-armed bandit problem: the discounted case, IEEE Trans. Autom. Contr. 30 (1985) 426-439. · Zbl 0566.90096 · doi:10.1109/TAC.1985.1103989
[28] L. Wein, Scheduling networks of queues: heavy traffic analysis of a two-station network with controllable inputs, Oper. Res. 38 (1990) 1065-1078. · Zbl 0724.90025 · doi:10.1287/opre.38.6.1065
[29] W. Whitt, The queueing network analyzer, Bell Syst. Tech. J. 62 (1983) 2779-2815.
[30] P. Whittle,Optimization over Time, Vol. I (Wiley, New York, 1982). · Zbl 0557.93001
[31] P. Yang, Pathwise solutions for a class of linear stochastic systems, Ph.D. Dissertation, Department of Operations Research, Stanford University (1988).
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.