The M/G/1 Queue The M/G/1 queue has exponentially distributed interarrival times and an arbitrary distribution for service times. The increase in generality compared to the M/M/1 queue comes with a price: the M/G/1 queue does not have a general, closed form distribution for the number of jobs in the queue in steady state. It does, however, admit a general solution for the average number of jobs in the queue, and application of Little's Theorem provides the corresponding result for the average time spent in the queue. Collectively, these results are known as the Pollaczek-Khinchin mean value formulae. The following derivation of the Pollaczek-Khinchin mean value formulae for the M/G/1 queue assumes FCFS scheduling, to simplify the analysis. However, the formulae are valid for any scheduling discipline in which the server is busy if the queue is non-empty, no job departs the queue before completing service, and the order of service is not dependent on knowledge about job service times. We begin by recalling or defining the following notation. Job i refers to the ith job to arrive at the queue. As usual, we assume that a steady state solution exists; i.e., the arrival rate is less than the service rate. X i - r.v. for service time of job i X X i X 2 X i 2 W i - r.v. for time job i spends waiting in queue before beginning service W i W i W i W i N i - r.v. for number of jobs in the queue when job i arrives N i N i N Q i N i R i - r.v. for residual service time seen by job i (the amount of time job i must wait until a job in service when i arrives is completed) R i R i R i R i λ - job arrival rate ρ λ X - server utilization When a job arrives at the queue, it must wait for the job in service (if there is one) to complete. Since we are assuming FCFS scheduling, it must also wait for all of the jobs which arrived before it but which have not begun service to complete. W i R i j i N i i 1 X j R i will be 0 if the job arrives when the queue is empty. Taking expectations, W i R i j i N i i 1 N i X j R i X N i This last step is valid because the number of jobs that are in the queue at an arrival instant must be independent of the service times of jobs that have not been serviced yet. We can take lim i → ∞ of both sides of this equation to obtain W R X N Q From Little's Theorem, N Q λ W Substituting this into the expression for W gives W R X λ W R ρ W R 1 ρ To determine R, we could make use of a well-known result which relates the principal moments R i n R i n of the residual time r.v. to the moments X i n X i n of the service time r.v.: R i n X i n 1 n 1 X i However, we can also find R directly by looking at a plot of the residual service time r.v. as a function of t. Define the following functions: r τ - the residual service time of the customer in service at time τ (this will be 0 if no customer is in service) M t - the number of service completions in the interval 0 t ; we are interested only in t such that r t 0 . The figure below illustrates how the residual service time changes over time. When a job i begins service, its residual service time starts at X i and falls linearly (with slope -1) to 0.

The time average of r τ in the interval 0 t is given by 1 t τ 0 t r τ 1 t i 1 M t X i 2 2 1 2 M t t i 1 M t X i 2 M t t 1 t τ 0 t r τ 1 2 t M t t t i 1 M t X i 2 M t These are time averages; however, the ensemble averages (means of the steady state distributions) and time averages are equal, giving us R λ X 2 2 Consequently, W λ X 2 2 1 ρ

The M/G/1 Queue with Vacations One important variation on the M/G/1 queue is to allow the server to take vacations - i.e., to be idle when there is work to be done. The server goes idle at the end of each busy period (when the queue becomes empty), and remains idle for some random amount of time. If the queue is still empty at the end of a vacation time, the server immediately starts another vacation; otherwise, the server begins a job service time. The analysis proceeds as for the M/G/1 queue, up to the point at which we find an expression for the average waiting time: W R 1 ρ except that we must define R to be the mean residual service or vacation time, since a job might arrive during another job's service time or during a server vacation, and it will be delayed until the completion of either. Define V i - r.v. for the length of vacation i V i V i V i V i L t - the number of vacations completed in the interval 0 t Assume that vacation times are independent and identically distributed, and are independent of job interarrival and service times. We will be interested in looking at the system only at some time t corresponding to the completion of a service or a vacation. In the figure below, darker triangles are service times and lighter ones are vacations.

Proceeding as before: 1 t τ 0 t r τ 1 t i 1 M t X i 2 2 1 t i 1 L t V i 2 2 1 2 M t t i 1 M t X i 2 M t 1 2 L t t i 1 L t V i 2 L t Since t 1 ρ L t V we can take the limit as t approaches of the average residual service time and use the equality of time and ensemble averages to obtain R λ X 2 2 1 ρ V 2 2 V Substituting this into the expression for the average waiting time gives us W λ X 2 2 1 ρ V 2 2 V