Polling on a circle with non-uniform batch arrivals

Technical Summary: Polling on a Circle with Non-Uniform Batch Arrivals

Problem Definition
This paper analyzes a continuous polling system on a circle of circumference 1, where a single server travels cyclically at a fixed speed to serve customers. The system is characterized by two primary features:

1. Batch Arrivals: Customers arrive in batches according to a Poisson process. The batch sizes are independent and identically distributed (i.i.d.).
2. Non-Uniform Arrival Locations: Unlike previous continuous polling models that assume uniform arrival locations, this paper assumes that each customer within a batch is assigned a location on the circle according to a general, known continuous distribution $\pi(x)$. This models real-world scenarios such as warehouse logistics (milkrun order picking) where storage policies dictate item locations.

The study focuses on two performance metrics for a batch:

• Batch Sojourn Time ($S_B$): The time from the arrival of a batch until the service completion of the last customer in that batch.
• Time to Delivery ($D$): The time from the arrival of a batch until the entire batch is delivered back to the central depot.

Two service disciplines are examined:

• Globally Gated: The server serves only customers present at the start of the cycle.
• Exhaustive: The server serves all customers encountered until the queue is empty.

Methodology
The authors employ distinct analytical approaches for the two service disciplines due to the complexity introduced by non-uniform arrival locations.

• Globally Gated Policy: The analysis relies on deriving the Laplace-Stieltjes Transform (LST) of the cycle time. By modeling the cycle time as a functional equation involving the arrival process and service times, the authors derive the LST for the cycle time as an infinite product. Using the joint distribution of the age and residual cycle time, they derive exact LSTs for the time to delivery ($D$) and the batch sojourn time ($S_B$). The derivation for $S_B$ involves conditioning on the location of the furthest customer in a batch relative to the depot.

• Exhaustive Policy: Deriving exact LSTs for the exhaustive policy with non-uniform arrivals is intractable. Instead, the authors propose a Mean-Value Analysis (MVA).

  • They define $f(x, y)$ as the average density of waiting customers at location $x$ given the server is at location $y$.
  • Using a branching process argument with immigration and a variant of Little's Law, they prove that $f(x, y)$ satisfies a specific integral equation.
  • They demonstrate that this integral equation has a unique solution in a specific function class, which can be found via successive substitutions.
  • The authors provide partial analytical solutions for the integral equation (separating terms related to travel time, residual service time, and batch size effects) and derive exact expressions for the mean batch sojourn time and mean time to delivery based on the solution to this integral equation.

• Limiting Behavior: The paper derives exact expressions for system performance in both light-traffic ($\lambda \downarrow 0$) and heavy-traffic ($\rho \uparrow 1$) limits for both service policies.

Key Contributions

1. Exact Expressions for Globally Gated Policy: The paper derives the exact LSTs and mean values for both batch sojourn time and time to delivery under the globally gated discipline, accommodating general arrival location distributions.
2. Integral Equation for Exhaustive Policy: For the exhaustive discipline, the authors prove that the average spread of customers satisfies an integral equation. They provide a method (successive substitution) to solve this equation numerically and derive exact expressions for the mean performance metrics dependent on this solution.
3. Light- and Heavy-Traffic Limits: Exact limiting expressions are derived for both policies. Notably, the heavy-traffic analysis reveals that the influence of the arrival location distribution $\pi(x)$ diminishes as the system approaches saturation, particularly for the batch sojourn time.
4. Application to Milkrun Systems: The theoretical results are applied to a milkrun order picking system in warehouse logistics. The study investigates how different storage policies (e.g., random vs. class-based storage) affect system performance.

Results

• Impact of Storage Policy: A counter-intuitive finding is that the arrival location distribution (storage policy) has a minimal effect on the average system performance, particularly under heavy traffic or for the exhaustive service policy. While the expected batch sojourn time is sensitive to the travel time to the furthest customer in a batch, the overall performance differences between various storage policies (e.g., placing fast movers at the beginning, middle, or end of the route) are negligible in most practical scenarios.
• Policy Comparison:
  • Under light traffic, the exhaustive policy is generally preferred over the globally gated policy because the server does not need to return to the depot before serving new arrivals, reducing idle travel time.
  • Under heavy traffic, the preference depends on the ratio of travel time to service time. If travel times are large relative to service times, the exhaustive policy remains preferred. However, if service times are large and batch sizes are significant, the globally gated policy may perform better as it prevents the server from getting "stuck" serving new arrivals while a batch is still being processed.
• Batch Size Effects: For the globally gated policy, increasing batch size increases the expected sojourn time due to the increased expected distance to the furthest customer. For the exhaustive policy, the effect of the arrival location distribution on performance is more pronounced for small batch sizes and light traffic but diminishes as batch sizes and traffic load increase.

Significance and Claims
The paper claims to extend the existing literature on continuous polling models by relaxing the assumption of uniform arrival locations, which is critical for modeling real-world applications like warehouse logistics where storage policies are non-uniform. The authors emphasize that while the mathematical derivation becomes significantly more complex (moving from one-dimensional to two-dimensional representations), the resulting performance metrics are surprisingly robust to the specific choice of storage policy.

The significance lies in providing a rigorous analytical framework for continuous polling with batch arrivals and non-uniform locations, offering exact solutions for the gated case and a robust algorithmic approach for the exhaustive case. The findings suggest that for milkrun systems, optimizing the storage policy (e.g., class-based storage) yields diminishing returns compared to the choice of service discipline (exhaustive vs. gated), especially in high-load environments. The paper concludes by noting that the current model assumes independent arrival locations within a batch and suggests future work could explore correlated locations (e.g., dependent items stored together) and stochastic walking times.