Question

Compare the \(M / G / 1\) system for first-come, first-served queue discipline with one of last-come, first-served (for instance, in which units for service are taken from the top of a stack). Would you think that the queue size, waiting time, and busyperiod distribution differ? What about their means? What if the queue discipline was always to choose at random among those waiting? Intuitively, which discipline would result in the smallest variance in the waiting time distribution?

Short answer

In the \(M / G / 1\) queueing system, the queue size and waiting time distributions are generally different for first-come, first-served (FCFS), last-come, first-served (LCFS), and random selection disciplines due to the varying service order. However, all disciplines have the same busy period distribution. The mean waiting time will differ for each discipline: FCFS provides a balance between waiting time and service order, LCFS can have shorter average waiting times but longer times for some customers, and randomly selecting customers may result in unpredictable mean waiting times. Intuitively, the FCFS discipline might result in the smallest variance in the waiting time distribution, as it is more stable in providing a service ordering.

Step-by-step solution

Understand the \(M / G / 1\) Queue System

The \(M / G / 1\) queue system is a model that consists of a single server, general service times, and Poisson arrival times. The system characteristics include the average arrival rate (\(\lambda\)), the service time distribution (G), and a single server.

First-Come, First-Served (FCFS) Discipline

In the FCFS discipline, customers are served in the order they arrive in the queue. The waiting time for a customer depends only on the arrival times and service times of the customers who have arrived before them.

Last-Come, First-Served (LCFS) Discipline

In the LCFS discipline, the server selects the last customer that arrives in the queue to be served first. In this case, the waiting time depends on the future arrivals of customers.

Random Selection Discipline

In this discipline, the server randomly selects a customer from the waiting queue to serve. The waiting time will depend on the probability distribution of the random selection.

Comparing Queue Size, Waiting Time, and Busy Period Distributions

The queue size and waiting time distributions will generally be different for each queue discipline, as the service ordering affects how customers are handled in the queue. However, for the busy period distribution, all disciplines will have the same distribution, because the busy period distribution does not depend on the service order.

Comparing Mean Values

The mean waiting time will differ for each discipline. Intuitively, FCFS has a balance between waiting time and service order that can prevent very long waiting times for any individual customer. LCFS can have shorter waiting times on average, but at the cost of longer waiting times for some customers, and the random selection discipline may result in unpredictable mean waiting times compared to the other two disciplines.

Smallest Variance in Waiting Time Distribution

Intuitively, the FCFS discipline might result in the smallest variance in the waiting time distribution because it provides a more stabilized order of customer service. The LCFS discipline, on the other hand, can lead to larger variance due to customers experiencing long waiting times, while random selection discipline introduces uncertainty which can also lead to larger variance.