Fast Discrete-Event Simulation of Markovian Queueing Networks through Euler Approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914687564644352 |
|---|---|
| author | Hong, L. Jeff Song, Yingda Wang, Tan |
| author_facet | Hong, L. Jeff Song, Yingda Wang, Tan |
| contents | The efficient management of large-scale queueing networks is critical for a variety of sectors, including healthcare, logistics, and customer service, where system performance has profound implications for operational effectiveness and cost management. To address this key challenge, our paper introduces simulation techniques tailored for complex, large-scale Markovian queueing networks. We develop two simulation schemes based on Euler approximation, namely the backward and forward schemes. These schemes can accommodate time-varying dynamics and are optimized for efficient implementation using vectorization. Assuming a feedforward queueing network structure, we establish that the two schemes provide stochastic upper and lower bounds for the system state, while the approximation error remains bounded over the simulation horizon. With the recommended choice of time step, we show that our approximation schemes exhibit diminishing asymptotic relative error as the system scales up, while maintaining much lower computational complexity compared to traditional discrete-event simulation and achieving speedups up to tens of thousands times. This study highlights the substantial potential of Euler approximation in simulating large-scale discrete systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13259 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Discrete-Event Simulation of Markovian Queueing Networks through Euler Approximation Hong, L. Jeff Song, Yingda Wang, Tan Methodology Computational Engineering, Finance, and Science Numerical Analysis Probability The efficient management of large-scale queueing networks is critical for a variety of sectors, including healthcare, logistics, and customer service, where system performance has profound implications for operational effectiveness and cost management. To address this key challenge, our paper introduces simulation techniques tailored for complex, large-scale Markovian queueing networks. We develop two simulation schemes based on Euler approximation, namely the backward and forward schemes. These schemes can accommodate time-varying dynamics and are optimized for efficient implementation using vectorization. Assuming a feedforward queueing network structure, we establish that the two schemes provide stochastic upper and lower bounds for the system state, while the approximation error remains bounded over the simulation horizon. With the recommended choice of time step, we show that our approximation schemes exhibit diminishing asymptotic relative error as the system scales up, while maintaining much lower computational complexity compared to traditional discrete-event simulation and achieving speedups up to tens of thousands times. This study highlights the substantial potential of Euler approximation in simulating large-scale discrete systems. |
| title | Fast Discrete-Event Simulation of Markovian Queueing Networks through Euler Approximation |
| topic | Methodology Computational Engineering, Finance, and Science Numerical Analysis Probability |
| url | https://arxiv.org/abs/2402.13259 |