k Workers in a Circular Warehouse: A Random Walk on a Circle, without Passing

DOI10.1137/S0036144503432011zbMATH Open1076.60059arXivmath/0309039OpenAlexW2126062023MaRDI QIDQ5317153FDOQ5317153

Joseph D. Skufca

Publication date: 16 September 2005

Published in: SIAM Review (Search for Journal in Brave)

Abstract: We consider the problem of stochastic flow of multiple particles traveling on a closed loop, with a constraint that particles move without passing. We use a Markov chain description that reduces the problem to a generalized random walk on a hyperplane (with boundaries). By expressing positions via a moving reference frame, the geometry of the no-passing criteria is greatly simplified, with the resultant condition expressible as the coordinate system planes which bound the first orthant. To determine state transition probabilities, we decompose transitions into independent events and construct a digraph representation in which calculating transition probability is reduced to a shortest path determination on the digraph. The resultant decomposition digraph is self-converse, and we exploit that property to establish the necessary symmetries to find the stationary density for the process.

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

zbMATH Keywords

Markov chaingeneralized random walksself-converse

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Graph theory (05C99)

Cited In (2)

• Mixed-width aisle configurations for order picking in distribution centers
• Two-worker blocking congestion model with walk speed \(m\) in a no-passing circular passage system

   Recommendations

• Title not available (Why is that?) 👍 👎
• Two-worker blocking congestion model with walk speed \(m\) in a no-passing circular passage system 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: k Workers in a Circular Warehouse: A Random Walk on a Circle, without Passing

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