Simulation Optmization

Queueing Network Simulator

Queueing Network Details

This simulator can simulate open queueing network that consists of a finite number of G/G/s/K stations to provide service. External customers may enter the network via each station. A customer that completes the service at one station may be routed to another to receive further service or leave the network subject to probability.

The notations and more details

The network has ${N}$ stations.
Station ${i}$ has ${s_i}$ identical servers, each of which has the service rate ${\mu_i>0}$ , for ${i=1,\ldots,N}$ . All the stations follow the first-in-first-out (FIFO) discipline. And there is only one queue for each station.
The arrival rate of external customers to station ${i}$ is ${\lambda_i\geq 0}$ , for ${i=1,\ldots,N}$ . There exists some ${i}$ for which ${\lambda_i>0}$ .
A customer that completes the service at station ${i}$ is routed to station ${j}$ with probability ${P_{ij}}$ and leaves the network with probability $P_{i0}=1-\sum_{j=1}^N P_{ij}$ , for ${i,j=1,\ldots,N}$ . There exists some ${i}$ for which ${P_{i0}>0}$ . Moreover, it is allowed that a customer finishing service is routed to the same station (re-enter), i.e., ${P_{ii}}$ can be nonzero. In this case, the customer will join the end of the queue (if any) of this station while the first customer in queue (if any) move into the vacated server simultaneously.
Station ${i}$ has capacity ${K_i}$ , i.e. the maximum number of customers allowed in the station, including those waiting in queue and those in the servers, for ${i=1,\ldots,N}$ . The capacity can be finite or infinite.

Customers’ behavior when a station is at full capacity

If an external customer arrives at a station when it is full, then the customer will not enter the network and is lost permanently.
If an internal customer who finishes the service at station ${i}$ and is routed to station ${j}$ finds that station ${j}$ is full, then the customer is blocked at station ${i}$ and occupy the original server until there is a place at station ${j}$ . The blocked customers, either at the same station or at different stations, are unblocked with a FIFO discipline. This blocking mechanism is known as blocking-after-service (BAS).

About deadlock

For queueing network with closed loop and finite capacity, deadlock phenomenon may occur. In this simulator, when deadlock occurs, it is solved by swapping instantaneously. Besides, when a customer re-enters a station, he has higher priority than those blocked in other stations.

Code Details

The codes were written in MATLAB R2015a. They (except for the third-party functions mentioned below) can be freely redistributed and used under the terms of the BSD 3-Clause License.

Download the entire package with an example in it.

Structure

Before calling the simulator, we first need to find all the closed loop in the network (in order to handle the potential deadlock). It is achieved by a third-party function “find_elem_circuits.m” (author: Chris Maes gist.github.com/cmaes/1260153). Moreover, the function “find_elem_circuits.m” relies on a function “components.m”, which is a function in the graph package MatlabBGL (author: David Gleich dgleich.github.io/matlab-bgl). The identified closed loops are then passed into the simulator together with all other network parameters.

Inputs and outputs

Input: QueuePra - queueing network parameters
- total station number
- arrival rate and distribution (needs to modify “inter_arrival_time.m”) to each station
- server number at each station
- service rate and distribution (needs to modify “service_time.m”) of a server in each station
- transition (routing) probability matrix
- capacity (wating space + server number) of each station
- the list of all loops of the network (where the deadlock may happen) identified by “find_elem_circuits.m”
Inputs: SimPra - simulation parameters
- time length for one replication
- warm up length to let the queue be steady
- number of simulation replication
- random seed
Outputs:
- stationary distribution for each station
- averaged number of customers in each station¹ & the whole system, and the variance of the AVERAGED number
- averaged number of customers waiting in each station queue & the whole system², and the variance of the AVERAGED number
- averaged sojourn time³ in each station & the whole system (waiting + serving), and the variance of the AVERAGED number
- averaged waiting time^3,4 in each station queue & the whole system, and the variance of the AVERAGED number

Notes:

¹ It includes the customers waiting in the queue + customers under service + customers who have finished service but still occupy the server because the destination station is full.
² Customers who have finished service but still occupy the server because the destination station is full are not included.
³ When calculating the averaged sojourn time and waiting time, only consider the customers ever enter the system and leave the system before simulation terminates, i.e., the rejected customers are not counted; the customers who are still in the system when simulation terminates are not counted. Besides, if a customer never enters station 1, he will not be counted when calculating averaged sojourn time and waiting time for station 1. (It is not difficult to modify the code to count all arrivals.) If a customer enters station 1 more than once, he is still regarded as one customer.
⁴ When a customer finishes service but still occupies the server because the destination station is full, such time period is not considered as waiting time. The waiting time only means the time a customer spends in the queue.

» Go back to the homepage