×

Polling systems with batch service. (English) Zbl 1244.90064

Summary: Motivated by applications in production and computer-communication systems, we study an \(N\)-queue polling system, consisting of an inner part and an outer part, and where products receive service in batches. Type-\(i\) products arrive at the outer system according to a renewal process and accumulate into a type-\(i\) batch. As soon as \(D_{i}\) products have accumulated, the batch is forwarded to the inner system where the batch is processed. The service requirement of a type-\(i\) batch is independent of its size \(D_{i}\). For this model, we study the problem of determining the combination of batch sizes \({\vec{D}}^{(\text{opt})}\) that minimizes a weighted sum of the mean waiting times. This model does not allow for an exact analysis. Therefore, we propose a simple closed-form approximation for \({\vec{D}}^{(\text{opt})}\), and present a numerical approach, based on the recently proposed mean waiting-time approximation of M. A. A. Boon et al. [Perform Eval 68, 290–306 (2011)]. Extensive numerical experimentation shows that the numerical approach is slightly more accurate than the closed-form solution, while the latter provides explicit insights into the dependence of the optimal batch sizes on the system parameters and into the behavior of the system. As a by-product, we observe near-insensitivity properties of \({\vec{D}}^{(\text{opt})}\), e.g. to higher moments of the interarrival and switch-over time distributions.

MSC:

90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boon MAA, Winands EMM, Adan IJBF, van Wijk ACC (2011) Closed-form waiting time approximations for polling systems. Perform Eval 68: 290–306 · Zbl 05842049 · doi:10.1016/j.peva.2010.12.004
[2] Boxma OJ, Van der Wal J, Yechiali U (2008) Polling with batch service. Stoch Models 24: 604–625 · Zbl 1158.60040 · doi:10.1080/15326340802427497
[3] Deb RK, Serfozo RF (1973) Optimal control of batch service queues. Adv Appl Probab 5: 340–361 · Zbl 0264.60066 · doi:10.2307/1426040
[4] Dorsman JL, Van der Mei RD, Winands EMM (2011) A new method for deriving waiting-time approximations in polling systems with renewal arrivals. Stoch Models 27: 318–332 · Zbl 1225.60144 · doi:10.1080/15326349.2011.567933
[5] Down D (1998) On the stability of polling models with multiple servers. J Appl Probab 35: 925–935 · Zbl 0938.60096 · doi:10.1239/jap/1032438388
[6] Gold H, Tran-Gia P (1993) Performance analysis of a batch service queue arising out of manufacturing system modelling. Queueing Syst 14: 413–426 · Zbl 0798.90067 · doi:10.1007/BF01158876
[7] Henderson W, Taylor PG (1990) Product form in networks of queues with batch arrivals and batch service. Queueing syst 6: 71–88 · Zbl 0699.60089 · doi:10.1007/BF02411466
[8] Levy H, Sidi M (1990) Polling systems: applications, modeling, and optimization. IEEE Trans Commun 38: 1750–1760 · doi:10.1109/26.61446
[9] Liu Z, Nain P (1992) Optimal scheduling in some multiqueue single-server systems. IEEE Trans Autom Control 37: 247–252 · doi:10.1109/9.121629
[10] Olsen TL, Van der Mei RD (2005) Polling systems with periodic server routing in heavy-traffic: renewal arrivals. Oper Res Lett 33: 17–25 · Zbl 1076.90011 · doi:10.1016/j.orl.2004.05.003
[11] Resing JAC (1993) Polling systems and multitype branching processes. Queueing Syst 13: 409–426 · Zbl 0772.60069 · doi:10.1007/BF01149263
[12] Schnabel RB, Koontz JE,Weiss BE (1985) A modular system of algorithms for unconstrained minimization. ACM Trans Math Softw 11:419–440 · Zbl 0591.65045 · doi:10.1145/6187.6192
[13] Takagi H (1985) Analysis of polling systems. MIT Press, Cambridge · Zbl 0571.68027
[14] Van der Mei RD (2002) Waiting-time distributions in polling systems with simultaneous batch arrivals. Ann Oper Res 113: 157–173 · Zbl 1013.90019
[15] Van der Mei RD, Roubos A (2011) Polling models with multi-phase gated service. Ann Oper Res (to appear) · Zbl 1259.90029
[16] Van der Mei RD, Winands EMM (2008) A note on polling models with renewal arrivals and nonzero switch-over times. Oper Res Lett 36: 500–505 · Zbl 1155.90357 · doi:10.1016/j.orl.2008.01.008
[17] Van der Wal J, Yechiali U (2003) Dynamic visit-order rules for batch-service polling. Probab Eng Inf Sci 17: 351–367 · Zbl 1336.90027
[18] Van Oyen MP, Teneketzis D (1996) Optimal batch service of a polling system under partial information. Math Methods Oper Res 44: 401–419 · Zbl 0867.90056 · doi:10.1007/BF01193939
[19] Vishnevskii VM, Semenova OV (2006) Mathematical methods to study the polling systems. Autom Remote Control 67(2): 173–220 · Zbl 1126.60321 · doi:10.1134/S0005117906020019
[20] Vlasiou M, Yechiali U (2008) M/G/polling systems with random visit times. Probab Eng Inf Sci 22: 81–105 · Zbl 1137.90432
[21] Weiss HJ (1979) The computation of optimal control limits for a queue with batch services. Manag Sci 25: 320–328 · Zbl 0426.90032 · doi:10.1287/mnsc.25.4.320
[22] Winands EMM (2011) Branching-type polling systems with large setups. OR Spectrum 33: 77–97 · Zbl 1231.90144 · doi:10.1007/s00291-009-0174-7
[23] Winands EMM, Adan IJBF, van Houtum GJ (2011) The stochastic economic lot scheduling problem: a survey. Eur J Oper Res 210: 1–9 · Zbl 1207.90063 · doi:10.1016/j.ejor.2010.06.011
[24] Winands EMM, de Kok AG, Timpe C (2009) Case study of a batch-production and inventory system. Interfaces 39: 552–554 · doi:10.1287/inte.1090.0431
[25] Zipkin PH (1985) Models for design and control of stochastic multi-item batch production systems. Oper Res 34: 91–104 · Zbl 0594.90041 · doi:10.1287/opre.34.1.91
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.