 Author
 Eline De Cuypere (UGent)
 Promoter
 Dieter Fiems (UGent) and Koen De Turck (UGent)
 Organization
 Abstract
 A queueing system is a mathematical abstraction of a situation where elements, called customers, arrive in a system and wait until they receive some kind of service. Queueing systems are omnipresent in real life. Prime examples include people waiting at a counter to be served, airplanes waiting to take off, traffic jams during rush hour etc. Queueing theory is the mathematical study of queueing phenomena. As often neither the arrival instants of the customers nor their service times are known in advance, queueing theory most often assumes that these processes are random variables. The queueing process itself is then a stochastic process and most often also a Markov process, provided a proper description of the state of the queueing process is introduced. This dissertation investigates numerical methods for a particular type of Markovian queueing systems, namely queueing systems with shared service. These queueing systems differ from traditional queueing systems in that there is simultaneous service of the headofline customers of all queues and in that there is no service if there are no customers in one of the queues. The absence of service whenever one of the queues is empty yields particular dynamics which are not found in traditional queueing systems. These queueing systems with shared service are not only beautiful mathematical objects in their own right, but are also motivated by an extensive range of applications. The original motivation for studying queueing systems with shared service came from a particular process in inventory management called kitting. A kitting process collects the necessary parts for an end product in a box prior to sending it to the assembly area. The parts and their inventories being the customers and queues, we get ``shared service'' as kitting cannot proceed if some parts are absent. Still in the area of inventory management, the decoupling inventory of a hybrid maketostock/maketoorder system exhibits shared service. The production process prior to the decoupling inventory is maketostock and driven by demand forecasts. In contrast, the production process after the decoupling inventory is maketoorder and driven by actual demand as items from the decoupling inventory are customised according to customer specifications. At the decoupling point, the decoupling inventory is complemented with a queue of outstanding orders. As customisation only starts when the decoupling inventory is nonempty and there is at least one order, there is again shared service. Moving to applications in telecommunications, shared service applies to energy harvesting sensor nodes. Such a sensor node scavenges energy from its environment to meet its energy expenditure or to prolong its lifetime. A rechargeable battery operates very much like a queue, customers being discretised as chunks of energy. As a sensor node requires both sensed data and energy for transmission, shared service can again be identified. In the Markovian framework, "solving" a queueing system corresponds to finding the steadystate solution of the Markov process that describes the queueing system at hand. Indeed, most performance measures of interest of the queueing system can be expressed in terms of the steadystate solution of the underlying Markov process. For a finite ergodic Markov process, the steadystate solution is the unique solution of $N1$ balance equations complemented with the normalisation condition, $N$ being the size of the state space. For the queueing systems with shared service, the size of the state space of the Markov processes grows exponentially with the number of queues involved. Hence, even if only a moderate number of queues are considered, the size of the state space is huge. This is the statespace explosion problem. As direct solution methods for such Markov processes are computationally infeasible, this dissertation aims at exploiting structural properties of the Markov processes, as to speed up computation of the steadystate solution. The first property that can be exploited is sparsity of the generator matrix of the Markov process. Indeed, the number of events that can occur in any state  or equivalently, the number of transitions to other states  is far smaller than the size of the state space. This means that the generator matrix of the Markov process is mainly filled with zeroes. Iterative methods for sparse linear systems  in particular the Krylov subspace solver GMRES  were found to be computationally efficient for studying kitting processes only if the number of queues is limited. For more queues (or a larger state space), the methods cannot calculate the steadystate performance measures sufficiently fast. The applications related to the decoupling inventory and the energy harvesting sensor node involve only two queues. In this case, the generator matrix exhibits a homogene blocktridiagonal structure. Such Markov processes can be solved efficiently by means of matrixgeometric methods, both in the case that the process has finite size and  even more efficiently  in the case that it has an infinite size and a finite block size. Neither of the former exact solution methods allows for investigating systems with many queues. Therefore we developed an approximate numerical solution method, based on Maclaurin series expansions. Rather than focussing on structural properties of the Markov process for any parameter setting, the series expansion technique exploits structural properties of the Markov process when some parameter is sent to zero. For the queues with shared exponential service and the service rate sent to zero, the resulting process has a single absorbing state and the states can be ordered such that the generator matrix is upperdiagonal. In this case, the solution at zero is trivial and the calculation of the higher order terms in the series expansion around zero has a computational complexity proportional to the size of the state space. This is a case of regular perturbation of the parameter and contrasts to singular perturbation which is applied when the service times of the kitting process are phasetype distributed. For singular perturbation, the Markov process has no unique steadystate solution when the parameter is sent to zero. However, similar techniques still apply, albeit at a higher computational cost. Finally we note that the numerical series expansion technique is not limited to evaluating queues with shared service. Resembling shared queueing systems in that a Markov process with multidimensional state space is considered, it is shown that the regular series expansion technique can be applied on an epidemic model for opinion propagation in a social network. Interestingly, we find that the series expansion technique complements the usual fluid approach of the epidemic literature.
Downloads

main.pdf
 full text
 
 open access
 
 
 1.69 MB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU5843703
 MLA
 De Cuypere, Eline. Numerical Methods for Queues with Shared Service. Ghent University. Faculty of Engineering and Architecture, 2014.
 APA
 De Cuypere, E. (2014). Numerical methods for queues with shared service. Ghent University. Faculty of Engineering and Architecture, Ghent, Belgium.
 Chicago authordate
 De Cuypere, Eline. 2014. “Numerical Methods for Queues with Shared Service.” Ghent, Belgium: Ghent University. Faculty of Engineering and Architecture.
 Chicago authordate (all authors)
 De Cuypere, Eline. 2014. “Numerical Methods for Queues with Shared Service.” Ghent, Belgium: Ghent University. Faculty of Engineering and Architecture.
 Vancouver
 1.De Cuypere E. Numerical methods for queues with shared service. [Ghent, Belgium]: Ghent University. Faculty of Engineering and Architecture; 2014.
 IEEE
 [1]E. De Cuypere, “Numerical methods for queues with shared service,” Ghent University. Faculty of Engineering and Architecture, Ghent, Belgium, 2014.
@phdthesis{5843703, abstract = {{A queueing system is a mathematical abstraction of a situation where elements, called customers, arrive in a system and wait until they receive some kind of service. Queueing systems are omnipresent in real life. Prime examples include people waiting at a counter to be served, airplanes waiting to take off, traffic jams during rush hour etc. Queueing theory is the mathematical study of queueing phenomena. As often neither the arrival instants of the customers nor their service times are known in advance, queueing theory most often assumes that these processes are random variables. The queueing process itself is then a stochastic process and most often also a Markov process, provided a proper description of the state of the queueing process is introduced. This dissertation investigates numerical methods for a particular type of Markovian queueing systems, namely queueing systems with shared service. These queueing systems differ from traditional queueing systems in that there is simultaneous service of the headofline customers of all queues and in that there is no service if there are no customers in one of the queues. The absence of service whenever one of the queues is empty yields particular dynamics which are not found in traditional queueing systems. These queueing systems with shared service are not only beautiful mathematical objects in their own right, but are also motivated by an extensive range of applications. The original motivation for studying queueing systems with shared service came from a particular process in inventory management called kitting. A kitting process collects the necessary parts for an end product in a box prior to sending it to the assembly area. The parts and their inventories being the customers and queues, we get ``shared service'' as kitting cannot proceed if some parts are absent. Still in the area of inventory management, the decoupling inventory of a hybrid maketostock/maketoorder system exhibits shared service. The production process prior to the decoupling inventory is maketostock and driven by demand forecasts. In contrast, the production process after the decoupling inventory is maketoorder and driven by actual demand as items from the decoupling inventory are customised according to customer specifications. At the decoupling point, the decoupling inventory is complemented with a queue of outstanding orders. As customisation only starts when the decoupling inventory is nonempty and there is at least one order, there is again shared service. Moving to applications in telecommunications, shared service applies to energy harvesting sensor nodes. Such a sensor node scavenges energy from its environment to meet its energy expenditure or to prolong its lifetime. A rechargeable battery operates very much like a queue, customers being discretised as chunks of energy. As a sensor node requires both sensed data and energy for transmission, shared service can again be identified. In the Markovian framework, "solving" a queueing system corresponds to finding the steadystate solution of the Markov process that describes the queueing system at hand. Indeed, most performance measures of interest of the queueing system can be expressed in terms of the steadystate solution of the underlying Markov process. For a finite ergodic Markov process, the steadystate solution is the unique solution of $N1$ balance equations complemented with the normalisation condition, $N$ being the size of the state space. For the queueing systems with shared service, the size of the state space of the Markov processes grows exponentially with the number of queues involved. Hence, even if only a moderate number of queues are considered, the size of the state space is huge. This is the statespace explosion problem. As direct solution methods for such Markov processes are computationally infeasible, this dissertation aims at exploiting structural properties of the Markov processes, as to speed up computation of the steadystate solution. The first property that can be exploited is sparsity of the generator matrix of the Markov process. Indeed, the number of events that can occur in any state  or equivalently, the number of transitions to other states  is far smaller than the size of the state space. This means that the generator matrix of the Markov process is mainly filled with zeroes. Iterative methods for sparse linear systems  in particular the Krylov subspace solver GMRES  were found to be computationally efficient for studying kitting processes only if the number of queues is limited. For more queues (or a larger state space), the methods cannot calculate the steadystate performance measures sufficiently fast. The applications related to the decoupling inventory and the energy harvesting sensor node involve only two queues. In this case, the generator matrix exhibits a homogene blocktridiagonal structure. Such Markov processes can be solved efficiently by means of matrixgeometric methods, both in the case that the process has finite size and  even more efficiently  in the case that it has an infinite size and a finite block size. Neither of the former exact solution methods allows for investigating systems with many queues. Therefore we developed an approximate numerical solution method, based on Maclaurin series expansions. Rather than focussing on structural properties of the Markov process for any parameter setting, the series expansion technique exploits structural properties of the Markov process when some parameter is sent to zero. For the queues with shared exponential service and the service rate sent to zero, the resulting process has a single absorbing state and the states can be ordered such that the generator matrix is upperdiagonal. In this case, the solution at zero is trivial and the calculation of the higher order terms in the series expansion around zero has a computational complexity proportional to the size of the state space. This is a case of regular perturbation of the parameter and contrasts to singular perturbation which is applied when the service times of the kitting process are phasetype distributed. For singular perturbation, the Markov process has no unique steadystate solution when the parameter is sent to zero. However, similar techniques still apply, albeit at a higher computational cost. Finally we note that the numerical series expansion technique is not limited to evaluating queues with shared service. Resembling shared queueing systems in that a Markov process with multidimensional state space is considered, it is shown that the regular series expansion technique can be applied on an epidemic model for opinion propagation in a social network. Interestingly, we find that the series expansion technique complements the usual fluid approach of the epidemic literature.}}, author = {{De Cuypere, Eline}}, isbn = {{9789085787303}}, language = {{eng}}, pages = {{var. p.}}, publisher = {{Ghent University. Faculty of Engineering and Architecture}}, school = {{Ghent University}}, title = {{Numerical methods for queues with shared service}}, year = {{2014}}, }