M/G/k queue: Difference between revisions

Revision as of 20:47, 19 December 2023

Revision as of 14:58, 20 December 2023

Line 32:

For an M/G/2 queue (the model with two servers) the problem of determining marginal probabilities can be reduced to solving a pair of [[integral equation]]s<ref>{{Cite journal | last1 = Knessl | first1 = C. | last2 = Matkowsky | first2 = B. J. | last3 = Schuss | first3 = Z. | last4 = Tier | first4 = C. | title = An Integral Equation Approach to the M/G/2 Queue | doi = 10.1287/opre.38.3.506 | journal = [[Operations Research (journal)|Operations Research]]| volume = 38 | issue = 3 | pages = 506 | year = 1990 | jstor = 171363}}</ref> or the Laplace transform of the distribution when the service time distribution is a mixture of exponential distributions.<ref>{{Cite journal | last1 = Cohen | first1 = J. W. | author-link1 = Wim Cohen| title = On the M/G/2 queueing model | doi = 10.1016/0304-4149(82)90046-1 | journal = Stochastic Processes and Their Applications | volume = 12 | issue = 3 | pages = 231–248 | year = 1982 | doi-access = free }}</ref> The Laplace transform of queue length<ref>{{cite journal | last1 = Hokstad | first1 = Per | year = 1979 | title = On the Steady-State Solution of the M/G/2 Queue | journal = Advances in Applied Probability | volume = 11 | issue = 1 | pages = 240–255 | publisher = Applied Probability Trust | doi = 10.2307/1426776 | jstor = 1426776| s2cid = 125014523 }}</ref> and waiting time distributions<ref>{{Cite journal | last1 = Boxma | first1 = O. J. | author-link1 = Onno Boxma| last2 = Deng | first2 = Q. | last3 = Zwart | first3 = A. P. | journal = [[Queueing Systems]]| volume = 40 | pages = 5–31 | year = 2002 | doi = 10.1023/A:1017913826973 | title = Waiting-Time Asymptotics for the M/G/2 Queue with Heterogeneous Servers| s2cid = 2513624 }}</ref> can be computed when the waiting time distribution has a rational Laplace transform.

== Software ==

=== Ciw ===

Ciw is a Python package for simulating queueing networks.<ref>{{Cite web |title=Welcome to Ciw’s documentation! — Ciw 3.1.0 documentation |url=https://ciw.readthedocs.io/en/latest/ |access-date=2023-12-19 |website=ciw.readthedocs.io}}</ref> Since G in M/G/k can be any distribution with non-negative support, we will use a [[gamma distribution]] for the sake of example. A gamma distribution is the result of a sum of independent [[Exponential distribution|exponentially-distributed]] [[random variable]], and thus for this example we have an interpretation that the servicing is implicitly a multi-step process where each step has an exponentially-distributed completion time.

A M/G/k queue can be implemented and simulated using Ciw in the following way.<syntaxhighlight lang="python3" line="1">

import ciw

ciw.seed(2018)

ARRIVAL_TIME = 1

SERVICE_SHAPE = 6 / 10

SERVICE_SCALE = 12 / 10

NUM_SERVERS = 2

HORIZON = 365

network = ciw.create_network(

arrival_distributions = [ciw.dists.Exponential(ARRIVAL_TIME)],

service_distributions = [ciw.dists.Gamma(shape=SERVICE_SHAPE, scale=SERVICE_SCALE)],

number_of_servers = [NUM_SERVERS]

)

simulation = ciw.Simulation(network)

simulation.simulate_until_max_time(HORIZON)

records = simulation.get_all_records()

</syntaxhighlight>

==References==