University:
California State University, Northridge
Course:
MSE 606 | Production and Operations Management for Engineers
Academic year:

2024
Views:

308

Pages:

30
Author:

Kyleigh Bartlett

Queuing Systems Chapter 17 Overview  People and products spent significant amount of time in waiting lines  Providing quick service is an important aspect of customer service  Trade-off between the cost of improving service and the costs associated with making customers wait  A probabilistic form of analysis  Results are referred to as operating characteristics  Results are used to make decisions Elements of Waiting Line Analysis  Waiting lines form because people arrive at a service faster than they can be served  Not arrive at a constant rate nor are they served in an equal amount of time  Have an average rate of customer arrivals and an average service time  Decisions are based on these averages for customer arrivals and service times  Formulas are used to compute operating characteristics Single-Server Waiting Line System  Components include:  Arrivals (customers), servers, (cash register/operator), customers in line form a waiting line  Factors to consider:  queue discipline.  nature of the calling population  arrival rate  service rate. Component Definitions  Queue Discipline: order in which customers are served (FIFO, LIFO, or randomly)  Calling Population: source of customers (infinite or finite)  Arrival Rate: Frequency at which customers arrive at a waiting line according to a probability distribution (Poisson distribution)  Service Rate: Average number of customers that can be served during a time period (negative exponential distribution) Single-Server Waiting Line System Single-Server Model  Assumptions:  An infinite calling population  A first-come, first-served queue discipline  Poisson arrival rate  Exponential service times  Symbology:  λ = the arrival rate (average number of arrivals/time period)  µ = the service rate (average number served/time period)  Customers must be served faster than they arrive (λ < µ) Single-Server Queuing Formulas Probability that no customers are in the waiting line:  λ Po = 1− µ        Probability that n customers are in the waiting line: n n      λ λ   λ   Pn = µ  ⋅ Po =  µ  1− µ            Average number of customers in system: waiting line: 2 λ Lq =  µ  µ − λ  L= λ µ −λ and SSingle-Server Queuing Formulas Average time customer spends waiting and being served: W = 1 =L µ −λ λ Average time customer spends waiting in the queue: Wq = λ µ  µ − λ  Probability that server is busy (utilization factor): Probability that server is idle: I =1−U =1− λ µ U =λ µ Characteristics for Fast Shop Market λ = 24 customers per hour arrive at checkout counter µ = 30 customers per hour can be checked out λ  = (1 - 24/30) Po = 1− µ      = .20 probabilit y of no customers in the system L = λ = 24/(30 - 24) = 4 customers on the avg in the system µ −λ 2 λ Lq =  µ  µ − λ  = (24)2/[30(30 - 24)] = 3.2 customers on the avg in the waiting line Characteristics for Fast Shop Market W = 1 = L = 1/[30 - 24] µ −λ λ = 0.167 hour (10 min) avg time in the system per customer Wq = λ = 24/[30(30 - 24)] µ  µ − λ  = 0.133 hour (8 min) avg time in the waiting line λ = 24/30 U =µ = .80 probabilit y server busy, .20 probabilit y server will be idle Steady-State Operating Characteristics  Utilization factor, U, must be less than one:  U < 1,or λ / µ < 1 and λ < µ.  Ratio of the arrival rate to the service rate must be less than one or, the service rate must be greater than the arrival rate  Server must be able to serve customers faster than the arrival rate in the long run, or waiting line will grow to infinite size. Single-Server Waiting Line System Effect of Operating Characteristics (1 of 6)  Wish to test several alternatives for reducing customer waiting time:  Addition of another employee to pack up purchases  Addition of another checkout counter.  Alternative 1: Addition of an employee raises service rate from µ = 30 to µ = 40 customers  Cost $150 per week, avoids loss of $75 per week for each minute of reduced customer waiting time  System operating characteristics with new parameters:  Po = .40 probability of no customers in the system  L = 1.5 customers on the average in the queuing system Effect of Operating Characteristics  System operating characteristics with new parameters (continued): Lq = 0.90 customer on the average in the waiting line W = 0.063 hour average time in the system per customer Wq = 0.038 hour average time in the waiting line per customer U = .60 probability that server is busy and customer must wait I = .40 probability that server is available Average customer waiting time reduced from 8 to 2.25 minutes worth $431.25 =(8-2.25)($75) per week. Effect of Operating Characteristics  Alternative 2: Addition of a new checkout counter ($6,000 plus $200 per week for additional cashier).  λ = 24/2 = 12 customers per hour per checkout counter  µ = 30 customers per hour at each counter  System operating characteristics with new parameters: Po = .60 probability of no customers in the system L = 0.67 customer in the queuing system Lq = 0.27 customer in the waiting line W = 0.055 hour per customer in the system Wq = 0.022 hour per customer in the waiting line U = .40 probability that a customer must wait I = .60 probability that server is idle Effect of Operating Characteristics Savings from reduced waiting time worth $500= (81.33)($75) per week - $200 = $300 net savings per week. After $6,000 recovered, alternative 2 would provide $300 281.25 = $18.75 more savings per week. Undefined and Constant Service Times  Constant occurs with machinery and automated equipment  Constant service times are a special case of the singleserver model with undefined service times  Queuing formulas: Wq = Lq λ Po =1− µ Lq = λ 2   2 2 λ σ +  λ / µ   21− λ / µ   λ L = Lq + µ  1 W =Wq + µ  λ U =µ Undefined Service Times Example  Data: Arrival rate of 20 customers per hour (Poisson distributed); undefined service time with mean of 2 minutes, standard deviation of 4 minutes.  Operating characteristics: 20 = .33 probability that machine not in use Po =1− λ = − 1 µ 30 2   2 2   λ σ + λ / µ  2  2 2       20 1/15 +  20 / 30       Lq = = 21− λ / µ  21− 20 / 30     = 3.33 employees waiting in line         L = Lq + λ µ = 3.33+ (20/ 30) = 4.0 employees in line and using the machine Undefined Service Times Example (2 of 2)  Operating characteristics (continued): Wq = Lq = 3.33 = 0.1665 hour = 10 minutes waiting time λ 20 1 = 0.1665 + 1 = 0.1998 hour W =Wq + µ 30 = 12 minutes in the system λ = 20 = 67% machine utilizatio n U =µ 30 Constant Service Times Formulas  No variability in service times; σ = 0.  Substituting σ = 0 into equations: 2  2 2 2 2      2 2  λ / µ  λ σ +  λ / µ  λ 0 +  λ / µ  2 λ   = = = = Lq 21− λ / µ  21− λ / µ  2µ  µ − λ  21− λ / µ         All remaining formulas are the same Constant Service Times Example  Inspecting one car at a time; constant service time of 4.5 minutes; arrival rate of customers of 10 per hour (Poisson distributed).  Determine average length of waiting line and average waiting time  λ = 10 cars per hour, µ = 60/4.5 = 13.3 cars per hour 2 2 ( 10 ) λ = = 1.14 cars waiting Lq = 2µ (µ − λ ) 2(13.3)(13.3 −10) Wq = Lq = 1.14 = 0.114 hour or 6.84 minutes waiting time λ 10 Finite Queue Length  Length of the queue is limited.  Operating characteristics:  M is the maximum number in the system: n   µ λ 1 − / λ  for n ≤ M Po = Pn = (Po) µ    1− (λ / µ )M +1 M +1 λ µ λ µ + 1 M / ( )( / ) − L= 1− λ / µ 1− (λ / µ )M +1 W= L λ (1− PM ) Lq = L − λ (1−µPM ) 1 Wq =W − µ Finite Queue Length Example  Limited parking space (one vehicle in service and three waiting for service)  Mean time between arrivals of customers is 3 minutes and mean service time is 2 minutes (both inter-arrival times and service times are exponentially distributed)  Maximum number of vehicles in the system equals 4.  Operating characteristics for λ = 20, µ = 30, M = 4: Po = 1− λ / µ = 1− 20 / 30 = .38 prob. that system is empty 1− (λ / µ )M +1 1− (20 / 30)5  λ PM = (Po) µ         n=M 4   20 = (.38)  = .076 prob. that system is full 30       Example-Cont.  Average queue lengths and waiting times: M +1 1 + / ) ( )( / µ λ λ µ M − L= 1− λ / µ 1− (λ / µ )M +1 5 30 20 5 ) )( / ( 30 20 / = 1.24 cars in the system − L= 1− 20 / 30 1− (20 / 30)5 Lq = L − λ (1−µPM ) =1.24 − 20(1−.076) = 0.62 cars waiting 30 W= L = 1.24 = 0.067 hours waiting in the system λ (1− PM ) 20(1−.076) 1 = 0.067 − 1 = 0.033 hour waiting in line Wq =W − µ 30 Finite Calling Population  There is a limited number of potential customers that can call on the system.  Operating characteristics (Poisson arrival and exponential service times): 1 Po = n N N!  λ  ∑ ( N − n)! µ    n=0 where N = population size, and n = 1, 2,...N n   N ! λ  Pn =  µ  Po ( N − n)!  L = Lq + (1− Po)  λ µ −  Lq = N − (1− Po) λ       Wq = Lq ( N − L)λ 1 W =Wq + µ Finite Calling Population Example  20 machines; each machine operates an average of 200 hours before breaking down; average time to repair is 3.6 hours; breakdown rate is Poisson distributed, service time is exponentially distributed.  Is repair staff sufficient?  λ = 1/200 hour = .005 per hour  µ = 1/3.6 hour = .2778 per hour  N = 20 machines Finite Calling Population Example Po = 1 = .652 n  20 20!  .005  ∑ (20 − n)!.2778    n=0 Lq = 20 − .005 + .2778 1−.652 = .169 machines waiting   .005 L = .169 + (1−.652) = .520 machines in the system Wq = .169 =1.74 hours waiting for repair (20 −.520)(.005) W =1.74 + 1 = 5.33 hours in the system .2778  System seems inadequate. Multiple-Server Waiting Line  Two or more independent servers in parallel serve a single waiting line; first-come, first-served basis  Assumptions:  First-come first-served queue discipline  Poisson arrivals, exponential service times  Infinite calling population.  Parameter definitions:  λ = arrival rate (average number of arrivals per time period)  µ = the service rate (average number served per time (channel) period) per server  c = number of servers  c µ = mean effective service rate for the system (must exceed arrival rate) Multiple-Server Waiting Line: Formulas Po =       n=c−1 1 λ ∑ n! µ n=0           n      1 λ +1 µ c!      c          cµ cµ − λ      = prob. no customers in system n   λ  1 Pn = n−c  µ  Po for n > c   c!c   n   λ  1 Pn = n  µ  Po for n < c = prob. of n customers in system     L= λµ (λ / µ )c Po + λ µ = average customers in the system µ (c −1)!(cµ − λ )2 W = L = average time customer spends in the system λ λ = average number of customers in the queue Lq = L − µ 1 = Lq = average time customer is in the queue Wq =W − µ λ c  λ  cµ Po = probabilit y customer must wait for service Pw = 1  µ c!  cµ − λ Example λ = 10, µ = 4, c = 3 Po =        1 10 0! 4      0      1 1 + 1 10 + 1 10 2! 4 1! 4                     2       3 3(4)   10  1 +   3! 4  3(4) −10 =.045 prob. of no customers 3 L = (10)(4)(10 / 4) (.045) +10 = 6 customers on average in service department 4 (3−1)![3(4) −10]2 W = 6 = 0.60 hour average customer t ime in the service department 10 Lq = 6 −10 = 3.5 customers on the average waiting to be served 4 Wq = 3.5 = 0.35 hour average waiting time in line per customer 10 3 3(4)   10  1 Pw =   (.045) = .703 prob. customer must wait for service 3! 4  3(4) −10 Notation Used for Waiting Line Models • Kendal suggested A/B/k – A: Denotes the prob. Distribution for the arrival – B: Denotes the prob. Distribution for the service time – k: Denotes of channels • Letters commonly used – M: designates a Poisson prob. Dist. For the arrivals or an exp. prob. dist. for the service time – D: designates that arrivals or the service time is deterministic – G: designates that the arrivals or the service time has a general prob. Dist. With a known mean and variance – M/M/1: single-server with Poisson arrivals and exp. service time – M/M/2: two-server with Poisson arrivals and exp. service time – M/G/1: single-server with Poisson arrivals and arbitrary service time

Queuing Systems

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock