Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Queuing

    Uploaded by

    s17005832

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Queuing

    Uploaded by

    s17005832
    13 views15 pages

    Original Title

    queuing

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    13 views15 pages

    Queuing

    Uploaded by

    s17005832

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 15

    Operations Research

    MSU6502
    Queuing theory
     Queuing theory is the mathematical study of waiting
    lines, or queues. A queuing model is constructed so that
    queue lengths and waiting time can be predicted
    Queuing theory
     Kendall’s Notation Before starting the investigations of
    elementary queuing systems let us introduce a notation
    originated by Kendall to describe a queuing system. Let
    us denote a system by
    A / B / m / K / n/ D,
    Where,
     A: distribution function of the inter arrival times,
     B: distribution function of the service times,
     m: number of servers,
     K: capacity of the system, the maximum number of customers in
    the system including the one being serviced,
     n: population size, number of sources of customers,
     D: service discipline.
    Queuing theory

     distribution function of the inter arrival times


    To characterize a queuing system we have to identify the
    probabilistic properties of the incoming flow of requests,
    service times and service disciplines. The arrival process
    can be characterized by the distribution of the inter arrival
    times of the customers, denoted by A(t),
    that is A(t) = P( inter arrival time < t).
    Queuing theory

     distribution function of the service times


    In queuing theory these inter arrival times are usually
    assumed to be independent and identically distributed
    random variables. The other random variable is the service
    time, sometimes it is called service request, work. Its
    distribution function is denoted by B(x),
    that is B(x) = P( service time < x).
    The service times, and inter arrival times are commonly
    supposed to be independent random variables.
    Queuing theory

    service discipline
    The service discipline determines the rule
    according to the next customer is selected. The
    most commonly used laws are
    FIFO - First In First Out: who comes earlier leaves
    earlier
    LIFO - Last Come First Out: who comes later leaves
    earlier
    Queuing theory

     Let Ø, called traffic intensity, be defined as


     Ø =mean service time /mean inter arrival time.
     Assuming an infinity population system with arrival
    intensity λ, which is reciprocal of the mean inter arrival
    time, and let the mean service denote by 1/µ.
     Then we have
    Ø = arrival intensity ∗ mean service time
    = λ /µ
    Queuing theory

    M/M/1 Queuing Models


    M/M/1 : ∞/FCFS/∞ (Generalized Queuing Model)
     The development of this model is based on the long run or steady state
    behavior of the queuing situation, which is achieved after the system is in
    operation for a sufficiently long period.
     The generalized model assumes that both the arrival and departure rates
    are state dependent.
     The management of a queuing system will decide to have more service
    counters as the number of customers increases. (Example: banks,
    supermarkets etc.)
    Queuing theory

    Definitions:
     𝒏 - number of customers in the system ( in queue and in service)
     𝝀𝒏 - arrival rate when there are “n” customers in the system
     𝝁𝒏 - departure rate when there are “n” customers in the system
     𝑷𝒏 - steady state probability of having “n” customers in the system
    Queuing theory

    Steady State:
     Leaving a certain state = entering that state
    Or
     Expected rate of flow into state n = expected rate of flow out of state n

    Examples for the probabilities of possible events leading to transitions:


     𝑛 units in the system and 1 arrival occurs in (0,h): 𝑃𝑛 ℎ . 𝜆𝑛 ℎ
     𝑛 units in the system and 1 service occurs in (0,h): 𝑃𝑛 ℎ . 𝜇𝑛 ℎ
     (𝑛 − 1) units in the system and 1 arrival occurs in (0,h): 𝑃𝑛−1 ℎ . 𝜆𝑛−1 ℎ
     𝑛 + 1 units in the system and 1 service occurs in (0,h): 𝑃𝑛+1 ℎ . 𝜇𝑛+1 ℎ
    Queuing theory

    First, consider an M/M/1 queuing system where the arrival and service rates
    are independent of the state. (i.e. λ and 𝜇 do not depend on the state):
     State Transition Diagram:
    Queuing theory

     At Steady State;
    Queuing theory

     The values of 𝑃0 can be determined by σ∞


    𝑛=0 𝑃𝑛 = 1
     These 𝑃𝑛 ’s can be used to evaluate the measures of
    performance such as average queue length, average
    waiting time, average utilization of the facility etc.
    Queuing theory
     Example:
    A bank operates with 2 counters. The manager uses the
    following schedule to determine the number of counters in
    operation depending on the number of customers in the
    bank. Customers arrive according to a Poisson distribution
    with mean rate of 10 per hour, and the service time per
    customer is exponential with mean 12 minutes.
    No.of customers in the No.of counters in
    bank operation
    1-3 1
    4-6 2
    >6 3

     Show that 𝑃0 = 1Τ55


     Find the expected number of idling counters
    Queuing theory

    Steady state measures of performance


    The most commonly used measures of a queuing system are:
     𝐿𝑠 - expected no. of customers in the system
     𝐿𝑞 - expected no. of customers in the queue
     𝑊𝑠 - expected waiting time in the system
     𝑊𝑞 - expected waiting time in the queue
     𝐶 ′ - expected number of busy servers

    You might also like