On the minimal travel time needed to collect n items on a circle.

DOI10.1214/105051604000000152MaRDI QIDQ1879896zbMATH OpenOpenAlexFDO

Authors Nelly Litvak, Willem van Zwet

Publication date 15 September 2004

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0405294

Mathematics Subject Classification ID

Processes with independent increments; Lévy processes (60G51) Exact distribution theory in statistics (62E15) Central limit and other weak theorems (60F05) Inventory, storage, reservoirs (90B05)

Abstract: Consider n items located randomly on a circle of length 1. The locations of the items are assumed to be independent and uniformly distributed on [0,1). A picker starts at point 0 and has to collect all n items by moving along the circle at unit speed in either direction. In this paper we study the minimal travel time of the picker. We obtain upper bounds and analyze the exact travel time distribution. Further, we derive closed-form limiting results when n tends to infinity. We determine the behavior of the limiting distribution in a positive neighborhood of zero. The limiting random variable is closely related to exponential functionals associated with a Poisson process. These functionals occur in many areas and have been intensively studied in recent literature.

Recommendations

• The travel time in carousel systems under the nearest item heuristic
• A selection-replacement process on the circle
• scientific article; zbMATH DE number 33260
• Random, nonuniform distribution of line segments on a circle
• Limiting distribution of the maximal distance between random points on a circle: a moments approach

Cites work

• scientific article; zbMATH DE number 2127961 (Why is no real title available?)
• scientific article; zbMATH DE number 194092 (Why is no real title available?)
• scientific article; zbMATH DE number 1163909 (Why is no real title available?)
• scientific article; zbMATH DE number 3233336 (Why is no real title available?)
• A Markovian analysis of additive-increase multiplicative-decrease algorithms
• AIMD algorithms and exponential functionals
• Distribution of linear combination of exponential variates
• Exponential functionals of Brownian motion and related processes
• Extremes of moving averages of random variables with finite endpoint
• On a class of order pick strategies in paternosters
• On subordinators, self-similar Markov processes and some factorizations of the exponential variable
• On the entire moments of self-similar Markov processes and exponential functionals of Lévy processes
• Ramanujan's Extensions of the Gamma and Beta Functions
• Some peculiarities of exponential random variables
• The entrance laws of self-similar Markov processes and exponential functionals of Lévy processes
• The travel time in carousel systems under the nearest item heuristic

Cited in

(10)

• FUNCTIONALS OF BROWNIAN BRIDGES ARISING IN THE CURRENT MISMATCH IN D/A CONVERTERS
• Statistical inference for generalized Ornstein-Uhlenbeck processes
• A survey on performance analysis of warehouse carousel systems
• A selection-replacement process on the circle
• Tail asymptotics for exponential functionals of Lévy processes
• An evening spent with Bill van Zwet
• Willem van Zwet's research
• A non-increasing Lindley-type equation
• Exact and inexact solution procedures for the order picking in an automated carousal conveyor
• One-Dimensional Carousel Storage Problems: Applications, Review and Generalizations

This page was built for publication: On the minimal travel time needed to collect \(n\) items on a circle.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879896)