Queuing Notation

• Recognizing the diversity of queuing systems, Kendall [ 1953] proposed a notational system for parallel server systems which has been widely adopted. An abridged version of this convention is based on the format A/B/c/N/K.

• These letters represent the following system characteristics:

  A represents the inter arrival-time distribution.

  B represents the service-time distribution.

  c represents the number of parallel servers.

  N represents the system capacity.

  K represents the size of the calling population.

  Common symbols for A and B include

  M (exponential or Markov),

  D (constant or deterministic),

  Ek (Erlang of order k),

  PH (phase-type),

  H (hyper exponential),

  G (arbitrary or general),

  and Gl (general independent).

• For example, M/M /1/∞/∞ indicates a single-server system that has unlimited queue capacity and an infinite population of potential arrivals.

• The inter arrival times and service times are exponentially distributed.

• When N and K are infinite, they may be dropped from the notation. For example, M/M/1/∞/∞ is often shortened to M/M/1 . The tire-curing system can be initially represented by G/G/1/5/5. FIFO queue discipline.

Queue Discipline

• Queue discipline refers to the logical ordering of customers in a queue and determines which customer will be chosen for service when a server becomes free. OR

• Queue discipline refers to the rule that a server uses to choose the next customer from the queue when the server completes the service of the current customer.

• Common queue disciplines include first-in-first-out (FIFO); last-in-first-out (LIFO); service in random order (SIRO); shortest processing time first (SPT); and service according to priority (PR).

• First in first out :This principle states that customers are served one at a time and that the customer that has been waiting the longest is served first.

• Last in first out : This principle also serves customers one at a time, however the customer with the shortest waiting time will be served first. Also known as a stack.

• Processor sharing: Service capacity is shared equally between customers.

• Priority : Customers with high priority are served first.[17] Priority queues can be of two types, Non-pre emptive (where a job in service cannot be interrupted) and pre emptive (where a job in service can be interrupted by a higher priority job). No work is lost in either model.

• Shortest job first: The next job to be served is the one with the smallest size

• Pre emptive shortest job first:The next job to be served is the one with the original smallest size.

• Shortest remaining processing time: The next job to serve is the one with the smallest remaining processing requirement.

Poisson process

• Consider random events such as the arrival of jobs at a job shop, the arrival of e-mail to a mail server, the arrival of boats to a dock, the arrival of calls to a call center, the breakdown of machines in a large factory, and so on.

• These events may be described by a counting function N(t) defined for all t≥0. This counting function will represent the number of events that occurred in [0, t].

• Time zero is the point at which the observation began, regardless of whether an arrival occurred at that instant.

• For each interval [0, t], the value N(t) is an observation of a random variable where the only possible values that can be assumed by N(t) are the integers 0, 1 , 2, . . . .

• The counting process, { N(t), t ≥ 0 }, is said to be a Poisson process with mean rate lamda if the following assumptions are fulfilled:

1. Arrivals occur one at a time.

2. { N(t), t ≥ 0 } has stationary increments: The distribution of the number of arrivals between t and t + s depends only on the length of the interval s, not on the starting point t. Thus, arrivals are completely at random without rush or slack periods.

3. {N(t), t ≥0) has independent increments: The number of arrivals during non overlapping time intervals are independent random variables. Thus, a large or small number of arrivals in one time interval has no effect on the number of arrivals in subsequent time intervals. Future arrivals occur completely at random, independent of the number of arrivals in past time intervals.

• If arrivals occur according to a Poisson process, meeting the three preceding assumptions, it can be shown that the probability that N(t) is equal to n is given by

• Thus its mean and variance are given by