Harrison, J. Michael; Wein, Lawrence M. Scheduling networks of queues: Heavy traffic analysis of a simple open network. (English) Zbl 0684.90034 Queueing Syst. 5, No. 4, 265-280 (1989). Summary: We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system. The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit. Cited in 26 Documents MSC: 90B22 Queues and service in operations research 90B35 Deterministic scheduling theory in operations research 60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.) 90B10 Deterministic network models in operations research 60K25 Queueing theory (aspects of probability theory) Keywords:Brownian approximations; heavy traffic analysis; dynamic priority; pathwise solution; queueing network; two single-server stations; two types of customers; dynamic sequencing policy; long-run average expected number of customers; dynamic control PDFBibTeX XMLCite \textit{J. M. Harrison} and \textit{L. M. Wein}, Queueing Syst. 5, No. 4, 265--280 (1989; Zbl 0684.90034) Full Text: DOI References: [1] J.M. Harrison,Brownian Motion and Stochastic Flow Systems (John Wiley and Sons, New York, 1985). · Zbl 0659.60112 [2] J.M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, In:Stochastic Differential Systems, Stochastic Control Theory and Applications, eds. W. Fleming and P.L. Lions, IMA Vol. 10 (Springer-Verlag, New York, 1988) 147-186. [3] J.M. Harrison and L.M. Wein, Scheduling networks of queues: heavy traffic analysis of a two-station closed network, Operations Research (1989) to appear. · Zbl 0684.90034 [4] F.P. Kelly,Reversibility and Stochastic Networks (John Wiley and Sons, New York, 1979). [5] C.N. Laws and G.M. Louth, Dynamic scheduling of a four station network, Probability in the Engr. and Inf. Sciences (1988) submitted. · Zbl 1134.90408 [6] M. Moustafa, Optimal scheduling in networks of queues, unpublished Ph. D. disseration, Program in Operations Research, North Carolina State University, Raleigh, NC, 1987. [7] L.M. Wein, Optimal control of a two-station Brownian network, Math. of Operations Research (1988) to appear. [8] L.M. Wein, Scheduling networks of queues: heavy traffic analysis of a two-station network with controllable inputs, Operations Research (1989) to appear. · Zbl 0724.90025 [9] P. Yang, Pathwise solutions for a class of linear stochastic systems, unpublished Ph.D. thesis, Dept. of Operations Research, Stanford University, Stanford, CA, 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.